A Compositional Approach to Abstraction for Planning Problems
Juliana Nogueira Vilela, Richard Hill · IFAC-PapersOnLine · 2020
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.