Abstract
In this report, we describe the search algorithm of the GEMPLAN multiagent planning system. The search algorithm is based upon the GEMPLAN domain description and its localized constraint representation. The problem domain is structured into regions of activity, and each region has its own set of local constraints. The search is a constraint-satisfaction process; it tries to find a plan in each region by satisfying the region’s constraints. Therefore, the search space is subdivided into regional search trees. Unfortunately, these search trees cannot be searched independently. However, the situation is much better than global search because GEMPLAN’s constraint localization, together with the domain structure, precisely define when the search in one region can affect another region, and hence how control must shift from one search tree to another. To avoid any confusion, this report does not describe GEMPLAN, but only its generic localized search algorithm. We only explain and abstract features of GEMPLAN on which this search algorithm is based. As a result, this algorithm is applicable to any other constraint-satisfaction problem with characteristics similar to GEMPLAN.
