Information Technology Reference
In-Depth Information
Hybrid Multi-agent Planning
Mohamed Elkawkagy and Susanne Biundo
Dept. of Artificial Intelligence
Ulm University, D-89069 Ulm, Germany
firstname.lastname@uni-ulm.de
Abstract. Although several approaches have been constructed for multi-agent
planning, solving large planning problems is still quite difficult. In this paper,
we present a new approach that integrates landmark preprocessing technique in
the context of hierarchical planning with multi-agent planning. Our approach uses
Dependent and Independent clustering techniques to break up the planning
problem into smaller clusters. These clusters are solved individually according to
landmark information, then the obtained individual plans are merged according
to the notion of fragments to generate a final solution plan. In hierarchical plan-
ning, landmarks are those tasks that occur in the decomposition refinements on
every plan development path. Hierarchical landmark technique shows how a pre-
processing step that extracts landmarks from a hierarchical planning domain and
problem description can be used to prune the search space that is to be explored
before actual search is performed. The methodologies in this paper have been im-
plemented successfully, and we will present some experimental results that give
evidence for the considerable performance increase gained through our system.
1
Introduction
Multi-agent planning (MAP) has been used to solve large planning problems. It works
by splitting the given planning problem into subproblems. Each subproblem is solved
individually to produce a solution so-called subplan . Then, these subplans have to be
combined to construct the solution plan [14]. Furthermore, MAP has been used to in-
terpret the plan coordination process of a set of independent agents. There are three
different approaches which discuss the plan coordination process. The first one focuses
on the coordination between completed plans such as the work of Tonino et al. [12] that
achieves a less costly merging plan by exploiting positive interactions and resolving the
conflicts between the generated subplans. In the second one, the processes of coordina-
tion and planning are interleaved i.e. the conflicts between subplans are resolved before
each agent generates its subplan [13]. The third one is divided into two categories: im-
plicit coordination that propagates general rules to manage agent behavior [15], and
explicit coordination that allows for the exchange of information between agents before
planning is started and provides additional constraints to the original planning problem
to ensure that the generated solution plan is feasible [10].
Many researchers have used hierarchical structure in the MAP approach to improve
planning efficiency. NOAH [3] is the first system which was built to interleave the hi-
erarchical planning and merging process by exchanging shared resources. It was devel-
oped by focusing on the efficient communication among planner agents [4]. Afterwards,
 
Search WWH ::




Custom Search