LPIS Home Page
Google Search

Title: Parallel Planning via the Distribution of Operators
Author(s): D. Vrakas, I. Refanidis, I. Vlahavas.
Availability: Click here to download the PDF (Acrobat Reader) file (15 pages).
Appeared in: Journal of Experimental and Theoretical Artificial Intelligence, Vol. 13 (3), pp. 211-226, 2001.
Abstract: This paper describes ODMP (Operator Distribution Method for Parallel Planning), a parallelization method for efficient heuristic planning. The method innovates in that it parallelizes the application of the available operators to the current state and the evaluation of the successor states using the heuristic function. In order to achieve better load balancing and a lift in the scalability of the algorithm, the operator set is initially enlarged, by grounding the first argument of each operator. Additional load balancing is achieved through the reordering of the operator set, based on the expected amount of imposed work. ODMP is effective for heuristic planners, but it can be applied to planners that embody other search strategies as well. It has been applied to GRT, a domain–independent heuristic planner, and CL, a heuristic planner for simple Logistics problems, and has been thoroughly tested on a set of Logistics problems adopted from the AIPS-98 planning competition, giving quite promising results.
See also :

        This paper has been cited by the following:

1 T. T. Son, P. H. Tu, E. Pontelli and T. C. Son, Executing Action Languages for Planning Problems on Multi-core Platforms: Some Preliminary Results, Workshop on Declarative Aspects of Multicore Programming, San Francisco CA, pp. 47- 61
2 O. Hatzi, "Web Service Composition through AI Planning", PhD Thesis, Department of Informatics and Telematics, Harokopeio University, 2009
3 P. H. Tu, E. Pontelli, T.C. Son, T. T. Son. "Applications of Parallel Processing Technologies in Heuristic Search Planning: Methodologies and Experiments", Concurrency and Computation: Practice and Experience, 2009
4 Rao Dong-ning, Jiang Zhi-hua, Jiang Yun-fei, "Review on Multi-agent Planning", Application Research of Computers Vol 28(3), pp. 801-804, 2011
5 D. Rao, Z. Jiang, "Auxiliary algorithms in green multi-agent planning framework", 2011 International Conference on Network Computing and Information Security, NCIS 2011, art. no. 5948712, pp. 175-179, 2011
6 R.Nissim, R. Brafman, "Multi-Agent A* for Parallel and Distributed Systems", Proceedings of the Workshop on Heuristics and Search for Domain-Independent Planning, ICAPS 2012, Sao Paolo, Brazil
7 Raz Nissim, Ronen Brafman, "Multi-Agent A* for Parallel and Distributed Systems", 11th International Conference on Autonomous Agents and Multi-Agent Systems, Valencia, 2012
8 R. Nissim, R. Brafman, "Distributed Heuristic Forward Search for Multi-Agent Systems", CoRR 2013
9 Kishimoto Akihiro, Fukunaga Alex, Botea Adi, "Evaluation of a simple, scalable, parallel best-first search strategy", ARTIFICIAL INTELLIGENCE Volume: 195 Pages: 222-248, 2013
10 Raz Nissim, Ronen Brafman, "Distributed Heuristic Forward Search for Multi-agent Planning", Journal of Articial Intelligence Research 51 (2014) 293-332