Factored Cost-Optimal Planning Using Message Passing Algorithms

• Autorzy: Jezequel L. , Fabre E.

Identyfikatory

DOI

10.3233/FI-2015-1239

• Języki publikacji: EN

Abstrakty

EN

This paper proposes an approach to solve cost-optimal factored planning problems. Planning consists in organizing actions in order to reach some predefined goal. In factored planning one considers several interacting planning problems and has to design an action plan for each of them. But one must also guarantee that all these local plans are compatible: actions shared among several problems must be jointly performed or jointly rejected. We enrich the problem with the extra requirement that the global plan computed in this modular manner must also minimize the sum of all action costs. A solution is provided to this problem, based on classical message passing algorithms, known as belief propagation in the setting of Bayesian networks. Here, messages carry complex information under the form of weighted (or (min; +)) automata, and all computations are performed with these objects. At the time our first paper on this topic was published, this method was the only one to solve cost-optimal factored planning problems in a modular way. Since then, new approaches were proposed. Experiments on classical benchmarks show that it is a valuable alternative to existing methods.

Słowa kluczowe

EN

factored planning; weighted automata; networks of automata; concurrency

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 139, nr 4
• Strony: 369--401
• Opis fizyczny: Bibliogr. 42 poz., rys., wykr.

Twórcy

autor

Jezequel L.

• Universit´e de Nantes, IRCCyN, UMR CNRS 6597 Nantes, France

autor

Fabre E.

• INRIA Rennes Bretagne Atlantique Rennes, France

Bibliografia

• [1] Allauzen, C., Mohri, M.: Efficient Algorithms for Testing the Twins Property, Journal of Automata, Languages and Combinatorics, 8(2), 2003, 117–144.
• [2] Amir, E., Engelhardt, B.: Factored Planning, Proceedings of the 18th International Joint Conference on Artificial Intelligence, 2003.
• [3] Blum, A., Furst, M.: Fast Planning Through Planning Graph Analysis, Artificial Intelligence, 90(1-2), 1995, 281–300.
• [4] Bonet, B., Geffner, H.: Planning as Heuristic Search, Artificial Intelligence, 129(1-2), 2001, 5–33.
• [5] Bonet, B., Haslum, P., Hickmott, S., Thiébaux, S.: Directed Unfolding of Petri Nets, Transactions on Petri Nets and other Models of Concurrency, 1(1), 2008, 172–198.
• [6] Brafman, R., Domshlak, C.: Factored Planning: How, When, and When Not, Proceedings of the 21st AAAI Conference on Artificial Intelligence, 2006.
• [7] Brafman, R., Domshlak, C.: From One to Many: Planning for Loosely Coupled Multi-Agent Systems, Proceedings of the 18th International Conference on Automated Planning and Scheduling, 2008.
• [8] Buchsbaum, A., Giancarlo, R., Westbrook, J.: On the Determinization of Weighted Finite Automata, SIAM Journal on Computing, 30(5), 2000, 1502–1531.
• [9] Cassandras, C., Lafortune, S.: Introduction to Discrete Event Systems, Kluwer Academic, 1999.
• [10] Dechter, R.: Constraint Processing, Morgan Kaufmann, 2003.
• [11] Edelkamp, S.: Planning with Pattern Databases, Proceedings of the 12th International Conference on Automated Planning and Scheduling, 2001.
• [12] Fabre, E.: Bayesian Networks of Dynamic Systems, Habilitation `aà diriger des recherches, Université de Rennes1, 2007.
• [13] Fabre, E., Jezequel, L.: Distributed Optimal Planning: an Approach by Weighted Automata Calculus, Proceedings of the 48th IEEE Conference on Decision and Control, 2009.
• [14] Fabre, E., Jezequel, L., Haslum, P., Thiébaux, S.: Cost-Optimal Factored Planning: Promises and Pitfalls, Proceedings of the 20th International Conference on Automated Planning and Scheduling, 2010.
• [15] Ghallab, M., Isi, C., Penberthy, S., Smith, D., Sun, Y., Weld, D.: PDDL - The Planning Domain Definition Language, Technical report, Yale Center for Computational Vision and Control, 1998.
• [16] Hart, P., Nilsson, N., Raphael, B.: A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics, 4(2), 1968, 100–107.
• [17] Haslum, P.: Tp4’04 and HSP*-a, 4th International Planning Competition Booklet, 2004.
• [18] Haslum, P., Geffner, H.: Admissible Heuristics for Optimal Planning, Proceedings of the 5th International Conference on Automated Planning and Scheduling, 2000.
• [19] Haslum, P., Helmert, M., Hoffmann, J.: Explicit-State Abstraction: A New Method for Generating Heuristic Functions, proceedings of the 23rd AAAI Conference on Artificial Intelligence, 2008.
• [20] Helmert, M.: The Fast Downward Planning System, Journal of Artificial Intelligence Research, 26(1), 2006, 191–246.
• [21] Helmert, M., Domshlak, C.: Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway?, Proceedings of the 19th International Conference on Automated Planning and Scheduling, 2009.
• [22] Helmert, M., Haslum, P., Hoffmann, J.: Fexible Abstraction Heuristics for Optimal Sequential Planning, Proceedings of the 17th International Conference on Automated Planning and Scheduling, 2007.
• [23] Hickmott, S., Rintanen, J., Thiébaux, S., White, L.: Planning via Petri Net Unfolding, Proceedings of the 19th International Joint Conference on Artificial Intelligence, 2007.
• [24] Hoffmann, J., Edelkamp, S., Thiébaux, S., Englert, R., dos Santos Liorace, F., Trüg, S.: Engineering Benchmarks for Planning: the Domains Used in the Deterministic Part of IPC-4, Journal of Artificial Intelligence Research, 26(1), 2006, 453–541.
• [25] Jezequel, L., Fabre, E.: Networks of Automata with Read Arcs: A Tool for Distributed Planning, Proceedings of the 18th IFAC World Congress, 2011.
• [26] Jezequel, L., Fabre, E.: A#: A Distributed Version of A* for Factored Planning, Proceedings of the 51th IEEE Conference on Decision and Control, 2012.
• [27] Jezequel, L., Fabre, E.: Turbo Planning, Proceedings of the 11th International Workshop on Discrete Event Systems, 2012.
• [28] Jezequel, L., Fabre, E., Khomenko, V.: Factored Planning: From Automata to Petri Nets, Proceedings of the 13th International Conference on Application of Concurrency to System Design, 2013.
• [29] Karpas, E., Domshlak, C.: Cost-Optimal Planning With Landmarks, Proceedings of the 21st International Joint Conference on Artificial Intelligence, 2009.
• [30] Kautz, H., Selman, B., Hoffmann, J.: SATPLAN: Planning as Satisfiability, 5th International Planning Competition Booklet, 2006.
• [31] Kirsten, D., Maürer, I.: On the Determinization ofWeighted Automata, Journal of Automata, Languages and combinatorics, 10(2), 2005, 287–312.
• [32] Klimann, I., Lombardy, S., Mairesse, J., Prieur, C.: Deciding Unambiguity and Sequentiality From a Finitely Ambiguous Max-Plus Automaton, Theoretical Computer Science, 327(3), 2004, 349–373.
• [33] Knoblock, C.: Generating Parallel Execution Plans With a Partial-Order Planner, Proceedings of the 2nd International Conference on Artificial Intelligence Planning Systems, 1994.
• [34] Mohri, M.: Finite-State Transducers in Language and Speech Processing, Computational Linguistics, 23(2), 1997, 269–311.
• [35] Mohri, M.: Handbook of Weighted Automata, chapter 6, Springer, 2009.
• [36] Nissim, R., Brafman, R. I.: Multi-agent A* for parallel and distributed systems, Proceedings of the 11th International Conference on Autonomous Agents on Multi-Agent Systems, 2012.
• [37] Nissim, R., Brafman, R. I.: Cost-Optimal Planning by Self-Interested Agents, Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013.
• [38] Pearl, J.: Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach, Proceedings of the 2nd National Conference on Artificial Intelligence, 1982.
• [39] Sakarovitch, J.: E´le´ments de the´orie des automates, Vuibert, 2003.
• [40] Su, R., Wonham, W. M.: Global and Local Consistencies in Distributed Fault Diagnosis for Discrete-Event Systems, IEEE Transactions on Automatic Control, 50(12), 2005, 1923–1935.
• [41] Thorsley, D., Teneketzis, D.: Diagnosability of Stochastic Discrete-Event systems, IEEE Transactions on Automatic Control, 50(4), 2005, 476–492.
• [42] Zielonka, W.: The Book of Traces, chapter 7, World Scientific, 1995.