A Compositional Approach to Abstraction for Planning Problems. Issue 4 (2020)
- Record Type:
- Journal Article
- Title:
- A Compositional Approach to Abstraction for Planning Problems. Issue 4 (2020)
- Main Title:
- A Compositional Approach to Abstraction for Planning Problems
- Authors:
- Vilela, Juliana
Hill, Richard - Abstract:
- Abstract: Supervisory Control Theory (SCT) has been applied as a tool to solve planning problems. However, SCT and planning techniques, in general, suffer an explosion in computational complexity when the systems reach a size commonly of interest. Efforts have been directed to improve the scalability of the application of SCT. For example, modular and compositional algorithms have been developed where a system can be decomposed into sub-systems. Hierarchical methods which employ abstraction are also known in literature. In prior work, the notion of cost equivalence 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 underlying full supervisor. Here we go a step further and develop a new notion of equivalence based on cost equivalence and weak bisimulation that we term priced-observation equivalence . This class of equivalence aggregates states with futures that share the same event labels and costs. This equivalence, along with other requirements, 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.
- Is Part Of:
- IFAC-PapersOnLine. Volume 53:Issue 4(2020)
- Journal:
- IFAC-PapersOnLine
- Issue:
- Volume 53:Issue 4(2020)
- Issue Display:
- Volume 53, Issue 4 (2020)
- Year:
- 2020
- Volume:
- 53
- Issue:
- 4
- Issue Sort Value:
- 2020-0053-0004-0000
- Page Start:
- 109
- Page End:
- 116
- Publication Date:
- 2020
- Subjects:
- Planning -- Supervisory Control -- Abstraction -- Decomposition -- Hierarchy
Automatic control -- Periodicals
629.805 - Journal URLs:
- https://www.journals.elsevier.com/ifac-papersonline/ ↗
http://www.sciencedirect.com/ ↗ - DOI:
- 10.1016/j.ifacol.2021.04.050 ↗
- Languages:
- English
- ISSNs:
- 2405-8963
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 16763.xml