Efficient Planning in Large-scale Systems Using Hierarchical Finite State Machines
For robotic and large-scale system planners, this method offers a more efficient and reconfigurable optimal planning approach.
The paper proposes a planning algorithm for hierarchical finite state machines that computes optimal plans with pre-processing scaling with the number of machines and query time reduced by removing irrelevant subtrees. On large systems with millions of states, it outperforms Dijkstra's algorithm, Bidirectional Dijkstra, and Contraction Hierarchies.
We consider optimal planning in a large-scale system formalised as a hierarchical finite state machine (HFSM). A planning algorithm is proposed computing an optimal plan between any two states in the HFSM, consisting of two steps: A pre-processing step that computes optimal exit costs of the machines in the HFSM, with time complexity scaling with the number of machines; and a query step that efficiently computes an optimal plan by removing irrelevant subtrees of the HFSM using the optimal exit costs. The algorithm is reconfigurable in the sense that changes in the HFSM are handled with ease, where the pre-processing step recomputes only the optimal exit costs affected by the change. The algorithm can also exploit compact representations that groups together identical machines in the HFSM, where the algorithm only needs to compute the optimal exit costs for one of the identical machines within each group, thereby avoid unnecessary recomputations. We validate the algorithm on large systems with millions of states and a robotic application. It is shown that our approach outperforms Dijkstra's algorithm, Bidirectional Dijkstra and Contraction Hierarchies.