Distributed Heuristic Forward Search for Multi-agent Planning

作     者：Nissim, Raz Brafman, Ronen 

作者机构：Ben Gurion Univ Negev IL-84105 Beer Sheva Israel 

出 版 物：《JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH》 (人工智能研究杂志)

年 卷 期：2014年第51卷第1期

页      面：293-332页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：ISF [1101/07] Lynn and William Frankel Center for Computer Science 

主　　题：constraint satisfaction problems A* Algorithm Heuristics algorithms Forward search SEARCHING ALGORITHM Planning Techniques Distribute 

摘      要：This paper deals with the problem of classical planning for multiple cooperative agents who have private information about their local state and capabilities they do not want to reveal. Two main approaches have recently been proposed to solve this type of problem - one is based on reduction to distributed constraint satisfaction, and the other on partial-order planning techniques. In classical single-agent planning, constraint-based and partial-order planning techniques are currently dominated by heuristic forward search. The question arises whether it is possible to formulate a distributed heuristic forward search algorithm for privacy-preserving classical multi-agent planning. Our work provides a positive answer to this question in the form of a general approach to distributed state-space search in which each agent performs only the part of the state expansion relevant to it. The resulting algorithms are simple and efficient - outperforming previous algorithms by orders of magnitude - while offering similar flexibility to that of forward-search algorithms for single-agent planning. Furthermore, one particular variant of our general approach yields a distributed version of the A* algorithm that is the first cost-optimal distributed algorithm for privacy-preserving planning.