tBurton: A Divide and Conquer Temporal Planner

Authors

  • David Wang Massachusetts Institute of Technology
  • Brian Williams Massachusetts Institute of Technology

DOI:

https://doi.org/10.1609/aaai.v29i1.9656

Keywords:

planning. temporal planner, automata, timeline, regression, history, episode, temporal network

Abstract

Planning for and controlling a network of interacting devices requires a planner that accounts for the automatic timed transitions of devices, while meeting deadlines and achieving durative goals. Consider a planner for an imaging satellite with a camera that cannot tolerate exhaust. The planner would need to determine that opening a valve causes a chain reaction that ignites the engine, and thus needs to shield the camera. While planners exist that support deadlines and durative goals, currently, no planners can handle automatic timed transitions. We present tBurton, a temporal planner that supports these features, while additionally producing a temporally least-commitment plan. tBurton uses a divide and conquer approach: dividing the problem using causal-graph decomposition and conquering each factor with heuristic forward search. The `sub-plans' from each factor are then unified in a conflict directed search, guided by the causal graph structure. We describe why this approach is fast and efficient, and demonstrate its ability to improve the performance of existing planners on factorable problems through benchmarks from the International Planning Competition.

Downloads

Published

2015-03-04

How to Cite

Wang, D., & Williams, B. (2015). tBurton: A Divide and Conquer Temporal Planner. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9656