On the Synthesis of Optimal Schedulers in Discrete Event Control Problems with Multiple Goals

Abstract : This paper deals with a new type of optimal control for Discrete Event Systems. Our control problem extends the theory of [sengupta98], that is characterized by the presence of uncontrollable events, the notion of occurrence and control costs for events, and a worst-case objective function. A significant difference with [sengupta98] is that our aim is to make the system evolve through a set of multiple goals, one by one, with no order necessarily pre-specified, whereas the previous theory only deals with a single goal. Our solution approach is divided into two steps. In the first step, we use the optimal control theory in [sengupta98] to synthesize individual controllers for each goal. In the second step, we develop the solution of another optimal control problem, namely, how to modify if necessary and piece together, or schedule, all of the controllers built in the first step in order to visit each of the goals with least total cost. We solve this problem by defining the notion of a scheduler and then by mapping the problem of finding an optimal scheduler to an instance of the well-known Traveling Salesman Problem (TSP). We finally suggest various strategies to reduce the complexity of the TSP resolution while still preserving global optimality
Type de document :
Article dans une revue
SIAM Journal on Control and Optimization, Society for Industrial and Applied Mathematics, 2000, 39 (2), pp.512-532. 〈10.1137/S0363012998341964〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00584875
Contributeur : Hervé Marchand <>
Soumis le : lundi 11 avril 2011 - 10:41:50
Dernière modification le : mercredi 16 mai 2018 - 11:23:02
Document(s) archivé(s) le : mardi 12 juillet 2011 - 02:39:44

Fichier

2000-SICON.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Hervé Marchand, Olivier Boivineau, Stéphane Lafortune. On the Synthesis of Optimal Schedulers in Discrete Event Control Problems with Multiple Goals. SIAM Journal on Control and Optimization, Society for Industrial and Applied Mathematics, 2000, 39 (2), pp.512-532. 〈10.1137/S0363012998341964〉. 〈inria-00584875〉

Partager

Métriques

Consultations de la notice

207

Téléchargements de fichiers

129