Information Technology Reference
In-Depth Information
Because of the lack of considering coordination
、
cooperation among agents
in Multi-Agent System, generally planning algorithms, as UCPOP, GraphPlan,
SNLP, can not be applied directly. In Multi-Agent environment, the actions
among agents are concurrent, which is not controlled by a single agent. A agent
can make system more coordinate by communication and protocol to try to
change the actions of other agents, and to complete the work which can not be
complicated itself by requesting the cooperation of other agents. Classical
planning algorithms assure that a agent is the only one who can change the
environment, therefore the planning result can not ensure that there is no conflict
with other agents, and the solution capability of agent is limited. The distributed
planning in dynamic environment hypothesizes that the paroxysm in environment
is not foreseeable, and the planning and executing are handled alternately. This
method can not ensure the reliability and completeness of planning.
A planning, especially partial order planning can be assured by the constraints
in planning steps as follows: Using temporal constrains to designate the time
sequence of executing steps; using codesignation constraints to designate the
executing steps. Planning solving is a process which adds and refines constraints
gradually. The conflict of coordination and cooperation among agents can be
accomplished by designating the temporal constraints and codesignation
constraints. The resource confliction of agent actions and the services which are
offered by one agent for other agents can be presented by causal link, and can be
solved by adding temporal constraints to agent actions. At the same time, the
cooperation actions among agents, as two agents cooperating to take up a desk,
must be described by single action description. The correctness of a agent
planning is assured by truth criterion in multi-agent System. We propose a multi-
agent concurrent partial order planning algorithm(Shi et al, 2002). Each agent is
planning for the target to be accomplished parallel. When an agent decides to add
a new action, it accomplishes the coordination of multi-agent System by the
constraint propagation with other agents.
1
.
Planning representation
To describe the planning action, there are too many constraints in the
accomplishment of practical scheduler using STRIPS, and it is too difficult to use
situated checking computations.
In 1989 Pednault proposed a kind of action described language ADL
(Pednault, 1989). We expand ADL to describe the planning actions in Multi-
Agent System(Shi et al, 2002). The represent capability of it is more powerful
than STRIPS, but less powerful than First-order logic.
