{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,4]],"date-time":"2026-08-04T14:21:36Z","timestamp":1785853296167,"version":"3.56.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,9,14]],"date-time":"2021-09-14T00:00:00Z","timestamp":1631577600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,14]],"date-time":"2021-09-14T00:00:00Z","timestamp":1631577600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Event Dyn Syst"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Hierarchy is a tool that has been applied to improve the scalability of solving planning problems modeled using Supervisory Control Theory. In the work of Hill and Lafortune (2016), the notion of <jats:italic>cost equivalence<\/jats:italic> was employed to generate an abstraction of the supervisor that, with additional conditions, guarantees that an optimal plan generated on the abstraction is also optimal when applied to the full supervisor. Their work is able to improve their abstraction by artificially giving transitions zero cost based on the sequentially-dependent ordering of events. Here, we relax the requirement on a specific ordering of the dependent events, while maintaining the optimal relationship between upper and lower levels of the hierarchy. This present paper also extends the authors\u2019 work (Vilela and Hill 2020) where we developed a new notion of equivalence based on cost equivalence and weak bisimulation that we term <jats:italic>priced-observation equivalence<\/jats:italic>. This equivalence allows the supervisor abstraction to be generated compositionally. This helps to avoid the explosion of the state space that arises from having to first synthesize the full supervisor before the abstraction can be applied. Here, we also show that models with artificial zero-cost transitions can be created compositionally employing the new relaxed sequential dependence definition. An example cooperative robot control application is used to demonstrate the improvements achieved by the compositional approach to abstraction proposed by this paper.<\/jats:p>","DOI":"10.1007\/s10626-021-00349-x","type":"journal-article","created":{"date-parts":[[2021,9,14]],"date-time":"2021-09-14T03:32:35Z","timestamp":1631590355000},"page":"89-113","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Hierarchical planning in a supervisory control context with compositional abstraction"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7882-0696","authenticated-orcid":false,"given":"Juliana","family":"Vilela","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Hill","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,9,14]]},"reference":[{"key":"349_CR1","doi-asserted-by":"crossref","unstructured":"Asarin E, Maler O (1999) As soon as possible: Time optimal control for timed automata. In: Vaandrager FW, van Schuppen JH (eds) Hybrid Systems: Computation and Control. Springer, Berlin, pp 19\u201330","DOI":"10.1007\/3-540-48983-5_6"},{"issue":"2","key":"349_CR2","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1109\/9.272327","volume":"39","author":"BA Brandin","year":"1994","unstructured":"Brandin BA, Wonham WM (1994) Supervisory control of timed discrete-event systems. IEEE Trans Autom Control 39(2):329\u2013342","journal-title":"IEEE Trans Autom Control"},{"issue":"7","key":"349_CR3","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ifacol.2018.06.273","volume":"51","author":"HJ Bravo","year":"2018","unstructured":"Bravo HJ, Pena PN, Alves LV, Takahashi RH (2018) Factorization-based approach for computing a minimum makespan controllable sublanguage. IFAC-PapersOnLine 51(7):19\u201324. 14th IFAC Workshop on Discrete Event Systems WODES 2018","journal-title":"IFAC-PapersOnLine"},{"key":"349_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68612-7","volume-title":"Introduction to discrete event systems","author":"C Cassandras","year":"2008","unstructured":"Cassandras C, Lafortune S (2008) Introduction to discrete event systems, 2nd edn. Springer, New York","edition":"2nd edn."},{"key":"349_CR5","doi-asserted-by":"crossref","unstructured":"Dulce-Galindo JA, Santos MA, Raffo GV, Pena PN (2019) Autonomous navigation of multiple robots using supervisory control theory. In: 2019 18th European Control Conference (ECC), pp 3198\u20133203","DOI":"10.23919\/ECC.2019.8796261"},{"key":"349_CR6","doi-asserted-by":"crossref","unstructured":"Fabre E, Jezequel L (2009) Distributed Optimal Planning: An Approach by Weighted Automata Calculus. 2009 IEEE Conference on Decision and Control and 28th Chinese Control Conference (section III)","DOI":"10.1109\/CDC.2009.5400084"},{"key":"349_CR7","volume-title":"Automated Plannig: theory and practice","author":"M Ghallab","year":"2004","unstructured":"Ghallab M, Nau D, Traverso P (2004) Automated Plannig: theory and practice, 1st edn. Elsevier, San Francisco","edition":"1st edn."},{"key":"349_CR8","doi-asserted-by":"crossref","unstructured":"Hagebring F, Lennartson B (2018) Compositional optimization of discrete event systems. In: 2018 IEEE 14th International Conference on Automation Science and Engineering - CASE, pp 849\u2013856","DOI":"10.1109\/COASE.2018.8560511"},{"key":"349_CR9","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1080\/00207170701799365","volume":"81","author":"R Hill","year":"2008","unstructured":"Hill R, Tilbury D (2008) Incremental hierarchical construction of modular supervisors for discrete-event systems. Int J Control 81:1364\u20131381","journal-title":"Int J Control"},{"key":"349_CR10","doi-asserted-by":"crossref","unstructured":"Hill RC, Lafortune S (2016) Planning under abstraction within a supervisory control context. In: 2016 IEEE 55th Conference on Decision and Control (CDC), pp 4770\u20134777","DOI":"10.1109\/CDC.2016.7798997"},{"key":"349_CR11","doi-asserted-by":"crossref","unstructured":"Hill RC, Lafortune S (2017) Scaling the formal synthesis of supervisory control software for multiple robot systems. In: 2017 American Control Conference (ACC), pp 3840\u20133847","DOI":"10.23919\/ACC.2017.7963543"},{"key":"349_CR12","doi-asserted-by":"crossref","unstructured":"Huang J, Kumar R (2007) Optimal nonblocking directed control of discrete event systems. In: 2007 American Control Conference, pp 4285\u20134290","DOI":"10.1109\/ACC.2007.4282559"},{"key":"349_CR13","doi-asserted-by":"publisher","unstructured":"Hyun-Wook J, Jae-Ho A, Jun-Sang P, Jun-Han O, Lim J (2010) Task planning for service robots with optimal supervisory control. In: 2010 IEEE Conference on Robotics, Automation and Mechatronics. https:\/\/doi.org\/10.1109\/RAMECH.2010.5513172, pp 303\u2013308","DOI":"10.1109\/RAMECH.2010.5513172"},{"key":"349_CR14","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/j.ins.2015.08.056","volume":"329","author":"PN Pena","year":"2016","unstructured":"Pena PN, Costa TA, Silva RS, Takahashi RHC (2016) Control of Flexible Manufacturing Systems under model uncertainty using Supervisory Control Theory and evolutionary computation schedule synthesis. Inf Sci 329:491\u2013502","journal-title":"Inf Sci"},{"key":"349_CR15","volume-title":"Intelligent Planning: A Decomposition and Abstraction Based Approach","author":"Y Qiang","year":"2012","unstructured":"Qiang Y (2012) Intelligent Planning: A Decomposition and Abstraction Based Approach, 1st edn. Springer Publishing Company, Berlin","edition":"1st edn."},{"key":"349_CR16","doi-asserted-by":"crossref","unstructured":"Sengupta R, Lafortune S (1993) A deterministic optimal control theory for discrete event systems. In: Proceedings of 32nd IEEE Conference on Decision and Control, vol 2, pp 1182\u20131187","DOI":"10.1109\/CDC.1993.325369"},{"key":"349_CR17","doi-asserted-by":"crossref","unstructured":"Su R (2012) Abstraction-based Synthesis of Timed Supervisors for Time-Weighted Systems. In: Proceedings of the 11th International Workshop on Discrete Event Systems (WODES 2012), pp 128\u2013134","DOI":"10.3182\/20121003-3-MX-4033.00024"},{"key":"349_CR18","unstructured":"Su R (2013) Coordinated distributed time optimal supervisory control. In: 2013 American Control Conference, pp 905\u2013910"},{"issue":"1","key":"349_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1109\/TAC.2011.2157391","volume":"57","author":"R Su","year":"2012","unstructured":"Su R, van Schuppen JH, Rooda JE (2012) The synthesis of time optimal supervisors by using heaps-of-pieces. IEEE Trans Autom Control 57(1):105\u2013118","journal-title":"IEEE Trans Autom Control"},{"key":"349_CR20","doi-asserted-by":"crossref","unstructured":"van Putten BJC, van der Sadden B, Reniers M, Voeten J, Schiffelers R (2020) Supervisor synthesis and throughput optimization of partially-controllable manufacturing systems. Discrete Event Dynamic Systems","DOI":"10.1007\/s10626-020-00325-x"},{"key":"349_CR21","doi-asserted-by":"crossref","unstructured":"Vilela J, Hill R (2020) A compositional approach to abstraction for planning problems. In: 2020 Workshop on Discrete Event Systems (WODES)","DOI":"10.1016\/j.ifacol.2021.04.050"},{"issue":"2","key":"349_CR22","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1109\/TASE.2016.2613911","volume":"14","author":"S Ware","year":"2017","unstructured":"Ware S, Su R (2017) Time optimal synthesis based upon sequential abstraction and its application to cluster tools. IEEE Trans Autom Sci Eng 14(2):772\u2013784","journal-title":"IEEE Trans Autom Sci Eng"}],"container-title":["Discrete Event Dynamic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-021-00349-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10626-021-00349-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-021-00349-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,14]],"date-time":"2022-03-14T09:10:25Z","timestamp":1647249025000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10626-021-00349-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,14]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["349"],"URL":"https:\/\/doi.org\/10.1007\/s10626-021-00349-x","relation":{},"ISSN":["0924-6703","1573-7594"],"issn-type":[{"value":"0924-6703","type":"print"},{"value":"1573-7594","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,14]]},"assertion":[{"value":"8 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}