research-article

Efficient symbolic search for cost-optimal planning

Authors:

Álvaro Torralba,

Vidal Alcázar,

Peter Kissmann,

Stefan EdelkampAuthors Info & Claims

Artificial Intelligence, Volume 242, Issue C

Pages 52 - 79

https://doi.org/10.1016/j.artint.2016.10.001

Published: 01 January 2017 Publication History

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. On the other hand, we study how to use state-invariant constraints to prune states in symbolic search. This is essential in regression search but it is yet to be exploited in symbolic search planners.Experiments with symbolic bidirectional uniform-cost search and symbolic A * search with PDBs show remarkable performance improvements on most IPC benchmark domains. Overall, with the help of our improvements, symbolic bidirectional search outperforms explicit-state search with state-of-the-art heuristics such as LM-cut across many different domains.

References

[1]

E.W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math., 1 (1959) 269-271.

Digital Library

[2]

A. Felner, Position paper: Dijkstra's algorithm versus uniform cost search or a case against Dijkstra's algorithm, in: Proceedings of the Symposium on Combinatorial Search (SoCS), AAAI Press, 2011, pp. 47-51.

[3]

P.E. Hart, N.J. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybern., 4 (1968) 100-107.

[4]

M. Helmert, P. Haslum, J. Hoffmann, R. Nissim, Merge-and-shrink abstraction: a method for generating lower bounds in factored state spaces, J. ACM, 61 (2014) 16:1-16:63.

Digital Library

[5]

M. Helmert, C. Domshlak, Landmarks, critical paths and abstractions: what's the difference anyway?, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, 2009, pp. 162-169.

[6]

V. Alcázar, D. Borrajo, S. Fernández, R. Fuentetaja, Revisiting regression in planning, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), IJCAI/AAAI, 2013, pp. 2254-2260.

[7]

B. Bonet, H. Geffner, Planning as heuristic search, Artif. Intell., 129 (2001) 5-33.

Digital Library

[8]

R.E. Bryant, Graph-based algorithms for boolean function manipulation, IEEE Trans. Comput., 35 (1986) 677-691.

Digital Library

[9]

S. Edelkamp, F. Reffel, OBDDs in heuristic search, in: Lecture Notes in Computer Science, vol. 1504, Springer, 1998, pp. 81-92.

Digital Library

[10]

K.L. McMillan, Symbolic Model Checking, Kluwer Academic Publishers, 1993.

[11]

A. Cimatti, F. Giunchiglia, E. Giunchiglia, P. Traverso, Planning via model checking: a decision procedure for AR, in: Lecture Notes in Computer Science, vol. 1348, Springer, 1997, pp. 130-142.

[12]

S. Edelkamp, M. Helmert, MIPS: the model-checking integrated planning system, AI Mag., 22 (2001) 67-72.

[13]

R.M. Jensen, M.M. Veloso, R.E. Bryant, State-set branching: leveraging BDDs for heuristic search, Artif. Intell., 172 (2008) 103-139.

Digital Library

[14]

S. Edelkamp, P. Kissmann, Optimal symbolic planning with action costs and preferences, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2009, pp. 1690-1695.

[15]

P. Kissmann, S. Edelkamp, Improving cost-optimal domain-independent symbolic planning, in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2011, pp. 992-997.

[16]

Á. Torralba, S. Edelkamp, P. Kissmann, Transition trees for cost-optimal symbolic planning, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, 2013, pp. 206-214.

[17]

Á. Torralba, V. Alcázar, Constrained symbolic search: on mutexes, BDD minimization and more, in: Proceedings of the Symposium on Combinatorial Search (SoCS), AAAI Press, 2013, pp. 175-183.

[18]

W. Hung, Exploiting Symmetry for Formal Verification, University of Texas at Austin, 1997.

[19]

S. Edelkamp, P. Kissmann, Limits and possibilities of BDDs in state space search, in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2008, pp. 1452-1453.

[20]

S. Edelkamp, P. Kissmann, On the complexity of BDDs for state space search: a case study in connect four, in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2011, pp. 18-23.

[21]

R.E. Bryant, Symbolic boolean manipulation with ordered binary-decision diagrams, ACM Comput. Surv., 24 (1992) 293-318.

Digital Library

[22]

P. Kissmann, J. Hoffmann, What's in it for my BDD? On causal graphs and variable orders in planning, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, 2013, pp. 327-331.

[23]

P. Kissmann, J. Hoffmann, BDD ordering heuristics for classical planning, J. Artif. Intell. Res., 51 (2014) 779-804.

Digital Library

[24]

P. Kissmann, S. Edelkamp, J. Hoffmann, Gamer and dynamic-gamer - symbolic search at IPC 2014, in: Proceedings of the International Planning Competition (IPC), 2014, pp. 77-84.

[25]

R. Yoshinaka, J. Kawahara, S. Denzumi, H. Arimura, S. Minato, Counterexamples to the long-standing conjecture on the complexity of BDD binary operations, Inf. Process. Lett., 112 (2012) 636-640.

Digital Library

[26]

B. Bollig, A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm, Inf. Process. Lett., 114 (2014) 124-129.

Digital Library

[27]

T.A.J. Nicholson, Finding the shortest route between two points in a network, Comput. J., 9 (1966) 275-280.

[28]

A.V. Goldberg, R.F.F. Werneck, Computing point-to-point shortest paths from external memory, in: Proceedings of the Workshop on Algorithm Engineering and Experiments and the Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO), SIAM, 2005, pp. 26-40.

[29]

I. Pohl, Bi-directional and Heuristic Search in Path Problems, Department of Computer Science, Stanford University, 1969.

[30]

E.A. Hansen, R. Zhou, Z. Feng, Symbolic heuristic search using decision diagrams, in: Lecture Notes in Computer Science, vol. 2371, Springer, 2002, pp. 83-98.

[31]

R.M. Jensen, R.E. Bryant, M.M. Veloso, SetA * : an efficient BDD-based heuristic search algorithm, in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press/The MIT Press, 2002, pp. 668-673.

[32]

P. Kissmann, Symbolic Search in Planning and General Game Playing, Universität Bremen, 2012.

[33]

S. Edelkamp, P. Kissmann, Á. Torralba, Symbolic A * search with pattern databases and the merge-and-shrink abstraction, in: Frontiers in Artificial Intelligence and Applications, vol. 242, IOS Press, 2012, pp. 306-311.

[34]

Á. Torralba, Symbolic Search and Abstraction Heuristics for Cost-Optimal Planning, Universidad Carlos III de Madrid, 2015.

[35]

J.C. Culberson, J. Schaeffer, Pattern databases, Comput. Intell., 14 (1998) 318-334.

[36]

S. Edelkamp, S. Schrödl, Heuristic Search - Theory and Applications, Academic Press, 2012.

[37]

S. Edelkamp, Planning with pattern databases, in: Lecture Notes in Computer Science, Springer, 2001, pp. 13-34.

[38]

K. Anderson, R. Holte, J. Schaeffer, Partial pattern databases, in: Lecture Notes in Computer Science, vol. 4612, Springer, 2007, pp. 20-34.

[39]

S. Edelkamp, Symbolic pattern databases in heuristic search planning, in: Proceedings of the Conference on Artificial Intelligence Planning Systems (AIPS), AAAI Press, 2002, pp. 274-283.

[40]

P. Haslum, A. Botea, M. Helmert, B. Bonet, S. Koenig, Domain-independent construction of pattern database heuristics for cost-optimal planning, in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2007, pp. 1007-1012.

[41]

J.R. Burch, E.M. Clarke, D.E. Long, K.L. McMillan, D.L. Dill, Symbolic model checking for sequential circuit verification, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 13 (1994) 401-424.

Digital Library

[42]

J.R. Burch, E.M. Clarke, D.E. Long, Symbolic model checking with partitioned transition relations, in: Proceedings of the International Conference on Very Large Scale Integration (VLSI), 1991, pp. 49-58.

[43]

J.R. Burch, E.M. Clarke, D.E. Long, Representing circuits more efficiently in symbolic model checking, in: Proceedings of the Design Automation Conference (DAC), 1991, pp. 403-407.

[44]

P. Chauhan, E.M. Clarke, S. Jha, J.H. Kukula, T.R. Shiple, H. Veith, D. Wang, Non-linear quantification scheduling in image computation, in: Proceedings of the International Conference on Computer-Aided Design (ICCAD), IEEE Press, 2001, pp. 293-298.

[45]

I.-H. Moon, J.H. Kukula, K. Ravi, F. Somenzi, To split or to conjoin: the question in image computation, in: Proceedings of the Design Automation Conference (DAC), 2000, pp. 23-28.

[46]

R.M. Jensen, E.A. Hansen, S. Richards, R. Zhou, Memory-efficient symbolic heuristic search, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2006, pp. 304-313.

[47]

M. Helmert, The Fast Downward planning system, J. Artif. Intell. Res., 26 (2006) 191-246.

Digital Library

[48]

C. Forgy, RETE: a fast algorithm for the many patterns/many objects match problem, Artif. Intell., 19 (1982) 17-37.

Digital Library

[49]

Á. Torralba, C. Linares López, D. Borrajo, Symbolic merge-and-shrink for cost-optimal planning, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), IJCAI/AAAI, 2013, pp. 2394-2400.

[50]

S. Zilles, R.C. Holte, The computational complexity of avoiding spurious states in state space abstraction, Artif. Intell., 174 (2010) 1072-1092.

Digital Library

[51]

P. Haslum, B. Bonet, H. Geffner, New admissible heuristics for domain-independent planning, in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press/The MIT Press, 2005, pp. 1163-1168.

[52]

V. Alcázar, Generation and Exploitation of Intermediate Goals in Automated Planning, Universidad Carlos III de Madrid, 2014.

[53]

M. Helmert, Concise finite-domain representations for PDDL planning tasks, Artif. Intell., 173 (2009) 503-535.

Digital Library

[54]

P. Haslum, H. Geffner, Admissible heuristics for optimal planning, in: Proceedings of the Conference on Artificial Intelligence Planning Systems (AIPS), AAAI, 2000, pp. 140-149.

[55]

P. Haslum, h m ( p ) = h 1 ( p m ) : alternative characterizations of the generalisation from h max to h m, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, 2009, pp. 354-357.

[56]

P. Haslum, Additive and reversed relaxed reachability heuristics revisited, in: Proceedings of the International Planning Competition (IPC), 2008.

[57]

V. Alcázar, Á. Torralba, A reminder about the importance of computing and exploiting invariants in planning, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, 2015, pp. 2-6.

[58]

O. Coudert, J.C. Madre, A unified framework for the formal verification of sequential circuits, in: Proceedings of the International Conference on Computer-Aided Design (ICCAD), 1990, pp. 126-129.

[59]

K.L. McMillan, A conjunctively decomposed boolean representation for symbolic model checking, in: Lecture Notes in Computer Science, vol. 1102, Springer, 1996, pp. 13-25.

[60]

Y. Hong, P.A. Beerel, J.R. Burch, K.L. McMillan, Safe BDD minimization using don't cares, in: Proceedings of the Design Automation Conference (DAC), 1997, pp. 208-213.

[61]

V. Vidal, H. Geffner, Solving simple planning problems with more inference and no search, in: Lecture Notes in Computer Science, vol. 3709, Springer, 2005, pp. 682-696.

[62]

F. Somenzi, CUDD: CU decision diagram package release 2.5.0, University of Colorado at Boulder, 2012.

[63]

M. Helmert, G. Röger, J. Seipp, E. Karpas, J. Hoffmann, E. Keyder, R. Nissim, S. Richter, M. Westphal, Fast downward stone soup, in: Proceedings of the International Planning Competition (IPC), 2011.

[64]

C. Linares López, S.J. Celorrio, A.G. Olaya, The deterministic part of the seventh international planning competition, Artif. Intell., 223 (2015) 82-119.

Digital Library

[65]

Á. Torralba, V. Alcázar, D. Borrajo, P. Kissmann, S. Edelkamp, SymBA * : a symbolic bidirectional A * planner, in: Proceedings of the International Planning Competition (IPC), 2014, pp. 105-109.

[66]

Á. Torralba, C. Linares López, D. Borrajo, Abstraction heuristics for symbolic bidirectional search, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), AAAI Press, 2016, pp. 3272-3278.

[67]

S. Edelkamp, P. Kissmann, Á. Torralba, BDDs strike back (in AI planning), in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2015, pp. 4320-4321.

[68]

M. Steinmetz, J. Hoffmann, Towards clause-learning state space search: learning to recognize dead-ends, in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2016, pp. 760-768.

[69]

B. Massey, Directions in Planning: Understanding the Flow of Time in Planning, Computational Intelligence Research Laboratory, University of Oregon, 1999.

[70]

M.N. Rice, V.J. Tsotras, Bidirectional A * search with additive approximation bounds, in: Proceedings of the Symposium on Combinatorial Search (SoCS), AAAI Press, 2012.

[71]

J.K. Barker, R.E. Korf, Limitations of front-to-end bidirectional heuristic search, in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2015, pp. 1086-1092.

[72]

R.C. Holte, A. Felner, G. Sharon, N.R. Sturtevant, Bidirectional search that is guaranteed to meet in the middle, in: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2016, pp. 3411-3417.

[73]

G. Sharon, R.C. Holte, A. Felner, N.R. Sturtevant, Extended abstract: an improved priority function for bidirectional heuristic search, in: Proceedings of the Ninth Annual Symposium on Combinatorial Search, AAAI Press, 2016, pp. 139-140.

[74]

N.R. Sturtevant, J. Chen, External memory bidirectional search, in: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI/AAAI Press, 2016, pp. 676-682.

Digital Library

Cited By

Pham FTorralba ÁElkind E(2023)Can i really do that? verification of meta-operators via stackelberg planningProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/602(5420-5428)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/602
Hou MLin TZhou HZhang WEdwards CZhang F(2021)Belief Space Partitioning for Symbolic Motion Planning2021 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA48506.2021.9561121(8245-8251)Online publication date: 30-May-2021
https://dl.acm.org/doi/10.1109/ICRA48506.2021.9561121
Gnad DHoffmann JWehrle M(2019)Strong stubborn set pruning for star-topology decoupled state space searchJournal of Artificial Intelligence Research10.1613/jair.1.1157665:1(343-392)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1613/jair.1.11576
Show More Cited By

Recommendations

Boosting optimal symbolic planning: Operator-potential heuristics
Abstract
Heuristic search guides the exploration of states via heuristic functions h estimating remaining cost. Symbolic search instead replaces the exploration of individual states with that of state sets, compactly represented using binary decision ...
Heuristic search + symbolic model checking = efficient conformant planning
IJCAI'01: Proceedings of the 17th international joint conference on Artificial intelligence - Volume 1

Planning in nondeterministic domains has gained more and more importance. Conformant planning is the problem of finding a sequential plan that guarantees the achievement of a goal regardless of the initial uncertainty and of nondeterministic action ...
Improving cost-optimal domain-independent symbolic planning
AAAI'11: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence

Symbolic search with BDDs has shown remarkable performance for cost-optimal deterministic planning by exploiting a succinct representation and exploration of state sets. In this paper we enhance BDD-based planning by applying a combination of domain-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 242, Issue C

January 2017

172 pages

ISSN:0004-3702

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 January 2017

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pham FTorralba ÁElkind E(2023)Can i really do that? verification of meta-operators via stackelberg planningProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/602(5420-5428)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/602
Hou MLin TZhou HZhang WEdwards CZhang F(2021)Belief Space Partitioning for Symbolic Motion Planning2021 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA48506.2021.9561121(8245-8251)Online publication date: 30-May-2021
https://dl.acm.org/doi/10.1109/ICRA48506.2021.9561121
Gnad DHoffmann JWehrle M(2019)Strong stubborn set pruning for star-topology decoupled state space searchJournal of Artificial Intelligence Research10.1613/jair.1.1157665:1(343-392)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1613/jair.1.11576
Gnad DTorralba ÁDomínguez MAreces CBustos F(2019)Learning how to ground a plan – partial grounding in classical planningProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v33i01.33017602(7602-7609)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1609/aaai.v33i01.33017602
Franco STorralba ÁLelis LBarley M(2017)On creating complementary pattern databasesProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3171888(4302-4309)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3171888

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents