A graph-theoretic optimal control problem for terminating discrete event processes
dc.contributor.author | Sengupta, Raja | en_US |
dc.contributor.author | Lafortune, Stéphane | en_US |
dc.date.accessioned | 2006-09-11T15:41:00Z | |
dc.date.available | 2006-09-11T15:41:00Z | |
dc.date.issued | 1992-11 | en_US |
dc.identifier.citation | Sengupta, Raja; Lafortune, Stéphane; (1992). "A graph-theoretic optimal control problem for terminating discrete event processes." Discrete Event Dynamic Systems 2(2): 139-172. <http://hdl.handle.net/2027.42/45109> | en_US |
dc.identifier.issn | 0924-6703 | en_US |
dc.identifier.issn | 1573-7594 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/45109 | |
dc.description.abstract | Most of the results to date in discrete event supervisory control assume a “zero-or-infinity” structure for the cost of controlling a discrete event system, in the sense that it costs nothing to disable controllable events while uncontrollable events cannot be disabled (i.e., their disablement entails infinite cost). In several applications however, a more refined structure of the control cost becomes necessary in order to quantify the tradeoffs between candidate supervisors. In this paper, we formulate and solve a new optimal control problem for a class of discrete event systems. We assume that the system can be modeled as a finite acylic directed graph, i.e., the system process has a finite set of event trajectories and thus is “terminating.” The optimal control problem explicitly considers the cost of control in the objective function. In general terms, this problem involves a tradeoff between the cost of system evolution, which is quantified in terms of a path cost on the event trajectories generated by the system, and the cost of impacting on the external environment, which is quantified as a dynamic cost on control. We also seek a least restrictive solution. An algorithm based on dynamic programming is developed for the solution of this problem. This algorithm is based on a graph-theoretic formulation of the problem. The use of dynamic programming allows for the efficient construction of an “optimal subgraph” (i.e., optimal supervisor) of the given graph (i.e., discrete event system) with respect to the cost structure imposed. We show that this algorithm is of polynomial complexity in the number of vertices of the graph of the system. | en_US |
dc.format.extent | 1755754 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Kluwer Academic Publishers; Springer Science+Business Media | en_US |
dc.subject.other | Mathematics | en_US |
dc.subject.other | Systems Theory, Control | en_US |
dc.subject.other | Convex and Discrete Geometry | en_US |
dc.subject.other | Manufacturing, Machines, Tools | en_US |
dc.subject.other | Electronic and Computer Engineering | en_US |
dc.subject.other | Operation Research/Decision Theory | en_US |
dc.subject.other | Discrete Event Systems | en_US |
dc.subject.other | Optimal Control | en_US |
dc.subject.other | Graph Theory | en_US |
dc.subject.other | Dynamic Programming | en_US |
dc.title | A graph-theoretic optimal control problem for terminating discrete event processes | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Industrial and Operations Engineering | en_US |
dc.subject.hlbsecondlevel | Mechanical Engineering | en_US |
dc.subject.hlbtoplevel | Engineering | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Department of Electrical Engineering and Computer Science, University of Michigan, 48109-2122, Ann Arbor, MI | en_US |
dc.contributor.affiliationum | Department of Electrical Engineering and Computer Science, University of Michigan, 48109-2122, Ann Arbor, MI | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/45109/1/10626_2005_Article_BF01797725.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1007/BF01797725 | en_US |
dc.identifier.source | Discrete Event Dynamic Systems | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.