This paper introduces the Time-Optimal Planning and Execution (TOPE) problem, in which the aim is to minimise the total planning and execution time required to achieve a goal. The TOPE process is derived and shown to be capable of solving this problem in dynamic state spaces, by continuously calculating the optimum value of any system parameters that can affect this total time. Procedures are presented to apply this process to an existing replanning system, and to determine its required accuracy and timeliness. It is shown that the TOPE process can yield lower total times than other planning systems if these requirements are met.

The design of a hierarchical planning system in which each level operates in parallel and communicates asynchronously is presented. It is shown that this parallel hierarchical replanner is both reactive, and as close to optimal over all information in the state space as is possible given finite computational power. A comparison with three other hierarchical methods is presented, which demonstrates that for scenarios in which the time taken to achieve a mission goal is of greater importance than the cost incurred, this approach has better performance than related methods in the literature.