Automatic Problem Decomposition for Distributed Planning

摘要

Distributed planning is highly useful in planning in complex real-world domains. Several advances have recently occurred in centralized plan synthesis under classical assumptions. In this paper, we show how the planning graph constructed by the influential planner Graphplan can be used to automatically and effectively decompose a problem so that the resulting subproblems can be allocated to multiple planners. We introduce interaction graphs which can be used to automatically decompose a planning problem into entirely independent subproblems under certain con-. ditions. The resulting subproblems can be passed to efficient classical planners and their plans can be combined. We present an empirical evaluation of three two agent planners (D-FP, D-HSP and D-GP) which solve.subproblems generated by the interaction graph-based decomposition. Each of the three two agent planners synthesizes plans faster than the corresponding single agent planner (PF, HSP and Graphplan) on several problems. Most of the work in distributed planning has hitherto focused on important issues like cooperation, coordination, communication and negotiation among various planning agents. Our work shows how recent advances in classical planning can be used to improve the computational efficiency of distributed planners.