AAAI Publications, Twenty-Third International Conference on Automated Planning and Scheduling

Font Size: 
Transition Trees for Cost-Optimal Symbolic Planning
Álvaro Torralba, Stefan Edelkamp, Peter Kissmann

Last modified: 2013-06-02


Symbolic search with binary decision diagrams (BDDs) often saves huge amounts of memory and computation time. In this paper we propose two general techniques based on transition relation trees to advance BDD search by refining the image operator to compute the set of successors. First, the conjunction tree selects the set of applicable actions through filtering their precondition. Then, the disjunction tree combines each transition result. Transition trees are used to combine several transition relations, speeding up BDD search. Experiments with bidirectional symbolic blind and symbolic A* search on planning benchmarks are reported showing good performance on most IPC 2011 domains.


Symbolic Search; Binary Decision Diagrams; Automated Planning

Full Text: PDF