Efficient symbolic search for cost-optimal planning Articles uri icon

authors

  • TORRALBA ARIAS DE REYNA, ALVARO
  • ALCAZAR SAIZ, VIDAL
  • KISSMAN, PETER
  • EDELKAMP, STEFAN

publication date

  • January 2017

start page

  • 52

end page

  • 79

volume

  • 242

International Standard Serial Number (ISSN)

  • 0004-3702

Electronic International Standard Serial Number (EISSN)

  • 1872-7921

abstract

  • In cost-optimal planning we aim to find a sequence of operators that achieve a set of goals with minimum cost. Symbolic search with Binary Decision Diagrams (BDDs) performs efficient state space exploration in terms of time and memory. This is crucial in optimal settings, in which large parts of the state space must be explored in order to prove optimality. However, the development of accurate heuristics for explicit-state search in recent years have left symbolic search techniques in a secondary place. In this article we propose two orthogonal improvements for symbolic search planning. On the one hand, we analyze and compare different methods for image computation in order to efficiently perform the successor generation on symbolic search. Image computation is the main bottleneck of symbolic search algorithms so an efficient computation is paramount for efficient symbolic search planning.

subjects

  • Computer Science

keywords

  • cost-optimal planning; symbolic search; image computation; state invariants; long-standing conjecture; pattern databases; heuristic-search; model-checking; complexity; abstraction; algorithm; system