  In this paper, we consider a planning problem for a large-scale system
modelled as a hierarchical finite state machine (HFSM) and develop a control
algorithm for computing optimal plans between any two states. The control
algorithm consists of two steps: a preprocessing step computing optimal exit
costs for each machine in the HFSM, with time complexity scaling linearly with
the number of machines, and a query step that rapidly computes optimal plans,
truncating irrelevant parts of the HFSM using the optimal exit costs, with time
complexity scaling near-linearly with the depth of the HFSM. The control
algorithm is reconfigurable in the sense that a change in the HFSM is
efficiently handled, updating only needed parts in the preprocessing step to
account for the change, with time complexity linear in the depth of the HFSM.
We validate our algorithm on a robotic application, comparing it with
Dijkstra's algorithm and Contraction Hierarchies. Our algorithm outperforms
both.
