Coordinating Autonomous Planners Adriaan ter Mors∗,Jeroen Valk∗and Cees Witteveen∗†∗Faculty of Electrical Engineering,Mathematics and Computer Science, Delft University of Technology,P.O.Box5031,2600GA Delft,The Netherlands Email:{valk,c.witteveen}@ewi.tudelft.nl
†Center for Mathematics and Computer Science(CWI),
P.O.Box94079,1090GB Amsterdam,The Netherlands
Email:c.witteveen@cwi.nl
神经衰弱症状
Abstract—We prent a framework for coordinating autonomous planning agents.Together,the agents have to achieve a t of interdependent(elementary)tasks.Each of the agents receives a unique subt of tasks to achieve, but an agent may be dependent on other agents completing (some of)their tasksfirst.
Each of the agents needs to make a plan in order to achieve its t of subtasks.Task dependencies between tasks assigned to different agents,however,prevent them from making plans independently.Therefore,in order to guarantee planning autonomy,we need a pre-planning coordinati
on method.We introduce a coordination method that can be ud to guarantee a solution to the joint planning problem whatever individual plans the agents may have constructed independently.
As a byproduct of our rearch,we show how this method can be applied to(re)u existing planning tools in a multi-agent context,by solving a multi-modal logistic planning problem by coordinating veral autonomous vehicle routing planners.
Keywords:coordination,multi-agent systems,au-tonomous agents,planning,approximation algorithms.
I.I NTRODUCTION
The problem we want to discuss in this paper applies whenever there is a number of autonomous actors ac-cepting a joint task that creates dependencies between the actors.A simple example is a supply chain where goods have to be transported by veral autonomous agents each having their own business policy,planning software and billing systems.Clearly,to manage such dependencies between agents created by the joint task, they need to be coordinated in order to guarantee that a joint plan will be constructed.Coordination,however, could easily result in restricting the planning autonomy of the ,the freedom of the agents to decide how to perform their tasks.In cas where agents try to maximize their planning autonomy such restrictions might simply be unacceptabl
e.For example,if the agents have competitive relationships,they might be reluctant to share details of their plans with other agents and do not want to be interfered during planning their own activities. This motivates the following coordination problem: How to guarantee that the joint task is planned well if we lack information about the details of the plans developed by the participating agents?
企业拓展In this paper we analyze this problem and discuss a coordination method that(i)guarantees the planning autonomy of each agent,(ii)at the same time ensures the existence of a joint plan respecting each of the individual agent plans,and(iii)does not require knowledge on which plans will be developed by each of the agents. In our tup,we assume that there exists a joint task T consisting of a partially ordered t T of elementary tasks t allocated to a number of agents.Each agent has received a(non-overlapping)subt of tasks and has to make a plan satisfying the given partial order. Order dependencies might exist not only between tasks given to the same agent,but also between tasks given to different agents,thereby inducing inter-agent dependencies.The approach we take to solve the coordination problem is to take a pre-planning approach to coordination:prior to planning,we try to minimally constrain the agents’tasks in such a way that agents can subquently plan their part of the joint task without taking into account the plans of the other agents. The result of this approach is the development of algorithms and protocols that ensure coordination while guaranteeing completely autonomous planning to each of the agents.
This t-up differs from common multi-agent-coordination approaches to coordination in planning.For instance,in Ephrati’s rearch[1],planning and coordi-nation steps are interleaved.In the(G)PGP framework
(e.g.[2],[3]),planning and coordination is an iterative process,with plans of various levels of abstraction being exchanged between agents to achieve efficient co-operation.In both approaches,the agents’planning method must be adapted to allow for coordination of the planning process.In our pre-planning coordination approach,however,the coordination takes place at the task level and occurs independently from the planning process.Since we parate the coordination method from the planning process,our approach allows existing single-agent planning software to be reud in a multi-agent planning context.
The structure of this paper is as follows.In Section II, we prent our framework for multi-agent planning and coordination and we identify the coordination problem. In Section III,we briefly discuss the complexity of the coordination problem and show its relation to some problems in graph theory.In Section IV,we prent a distributed coordination protocol that allows agents to achieve coordination while remaining autonomous in the planning process.In Section V,we will show how this coordination protocol can be ud to solve multi-agent planning problems using(existing)single-agent planning sy
stems,and we will prent some results we achieved in solving instances of multi-modal logistic benchmark problems.Section VI concludes the paper by discussing the results and identifying areas for future work.
II.A T ASK-O RIENTED M ULTI-AGENT P LANNING
F RAMEWORK
We consider problems that have to be solved by v-eral autonomous agents,each having their own capabil-ities and using their own(planning)tools.Problems we have in mind consist of a t T of interrelated elementary tasks.Such an elementary task t,or simply task,is a unit of work that can be performed by a single agent.A task t1depends on another task t2if there exists a precedence constraint between them:If a task t2is preceded by task t1,denoted by t1≺t2,the execution of t2may not start until t1hasfinished;for example,achieving t1results in creating resources needed to perform t2.Such a t of interdependent tasks is called a composite task.A composite task T=(T,≺)therefore is a non-empty t of tasks T={t1,...t m},partially ordered by a t of precedence constraints≺⊆T×T.This composite task must be performed by a t A={A1,...A n}of autonomous planning agents.
We assume that the tasks in T have been assigned to the agents in A by some(surjective)task assignment f:T→A thereby inducing a partitioning T={T1,...,T n}of T,where T i={t j∈T|f(t j)=A i} denotes the t of tasks allocated to agent A i.As a result of this task assignment A i also inherits the precedence constraints that apply to T ,the t ≺i=≺∩(T i×T i).Together the ts≺i constitute the t≺intra=
n
i=1
≺i of intra-agent constraints,while the remaining t of constraints≺inter=≺\≺intra con-stitutes the t of inter-agent constraints.Note that each agent A i is responsible for achieving the(composite) subtask(T i,≺i).
A.Tasks,Plans and Refinements
To achieve the composite task(T i,≺i),agent A i has to make a plan using its own favorite planning tool 1.We distinguish between the abstract plan and the concrete plan of an individual agent A i.The concrete plan of A i is the direct output of the agent’s planning system containing detailed information
about actions to be performed and resources needed.The abstract plan is the translation of the concrete plan in terms of the t of tasks t∈T i to be performed and their dependency (precedence)relations.Since every feasible plan has to specify a partial order of actions to be performed, an abstract plan for(T i,≺i)is simply a partial order (T i,≺p
怎么挑选玉手镯i
).Clearly,such an abstract plan satisfies the composite task(T i,≺i)iff≺p
i
refines≺,≺i⊆≺p
i
. Example2.1:Suppo that an agent is instructed to deliver packages p1and p2from a location A to location B and from B to C,respectively.That is,he is allocated the composite task T=({t1,t2},∅),with t1:pickup p1at A and deliver it at B,and t2:pickup p2at B and deliver it at C.Since the agent is assumed to be autonomous,it can decide for itlf the best plan to accomplish the tasks.Suppo the agent makes the following concrete plan:First,it will travel from its current location X to A.Then it
will pickup p1and it will go to location B delivering package p1.Hereafter the agent will pickup p2in B and will take a detour via Y to C in order to have lunch.It will stop in C to deliver p2and thenfinally will return home to X. From a coordination point of view,veral pieces of information are not of interest,namely:the exact location from which the agents starts,going to Y for lunch, and returning home to X.The only relevant information derived from the concrete plan occurs in the abstract plan specifying that the agent will perform t1before t2. 1In general,planning to achieve such a t of elementary tasks constitutes a non-trivial problem.For example,even making an optimal plan for a t of unrelated pickup-delivery orders constitutes an NP-hard problem.
Thus,the agent’s abstract plan is the partial order(T,≺p) with t1≺p t2.Indeed,this plan satisfies(T,∅),becau ≺p clearly refines∅.
To check whether a concrete plan can be coordinated with the plan of another agent,we only need the informa-tion contained in its abstract plan.2Hence,from now on we only u abstract plans of agents and assume that they are ,simple refinements of the composite tasks given to the agents.
B.The Coordination Problem
A coordination algorithm or protocol for autonomous planning agents should ensure that,after receiving its part T i of the joint task T,(i)each autonomous agent A i is allowed to construct its plan independently from the other agents,(ii)there is a simple way to combine their plans into a joint plan,while respecting each individual plan3,and(iii)both the objectives should be achieved irrespective of the choice of the plans constructed by the individual agents.
Clearly,a simple task allocation alone does not always guarantee the existence of such a feasible joint plan: Example2.2:Consider the composite task depicted in Figure1,where the tasks t1and t4are allocated to agent A1and the tasks t2and t3are allocated to agent A2.Precedence relations are reprented by he arc e1between t1and t2reprents the precedence relation t1≺t2.The arcs e1and e2together constitute the t of precedences(so the t of intra-agent precedences is empty).The dotted arc r1reprents a feasible refinement for agent A1:since there is no precedence relation between t1and t4,agent A1might come up with a plan where t4is executed prior to t1.Similarly,agent A2might decide to introduce the refinement r2,by planning to execute t2before t3.Each of the plans is a perfectly feasible plan meeting the intra-agent constraints.However,if both refinements r1 and r2are made,then combining the plans into a joint plan that respects them both results in an infeasible joint plan,due to the existence of a cycle e1−r2−e2−r1. At run-time,such a cyc
le in a joint plan would cau a deadlock,since it 1to be executed before t2,and also t2to be executed before t1.
It can be easily shown that the only possibility4to ensure a solution to the coordination problem is to 2We assume no dependencies between the agents other than the precedence constraints between their tasks.
3That is,there should be no need for additional(re)planning for any agent.
4If we require that planning and coordination be parated.Fig.1.A composite task,augmented two potential refinements r1 and r2and a potential constraint c1.
add,prior to planning,a t∆=
∆i of additional constraints to the t of precedence constraints≺.More precily,each t∆i has to be added to each t of precedence constraints≺i such that the following conditions are satisfied:
1)for all i,(T i,≺i∪∆i)constitutes a composite task,
<,≺i∪∆i is a partial order refining≺i;
2)for every conceivable t p A={p1,...,p n}
of individual plans of agents where each p i=
(T i,≺p
i
)is a plan for(T i,≺i∪∆i),the structure P=(
n
i=1
T i,≺∪≺p
1
∪···∪≺p
n
)
is a partially ordered ,P is a feasible joint plan
that respects the individual plans and refines the
二陈丸的功效
composite task(T,≺).
The coordination problem then is,given a composite task(T,≺)and a partitioning T=T1,...,T n of T,to find a minimum t∆={∆1,...,∆n}of additional precedence constraints to ensure a feasible joint plan whatever feasible abstract plans might be constructed by the individual agents.
Example2.3:Continuing the previous example,in Figure1,the t∆={{c1},∅}constitutes a minimal coordination t in which agent A1receives constraint c1 and agent A2receives no constraints.Note that,due to the constraint c1,no subquent refinements can create a cycle in the precedence relation.That is,after adding constraint c1,every feasible individual plan each of the agents might construct can always be combined into a feasible joint plan.
III.T HE COMPLEXITY OF THE COORDINATION PROBLEM AND RELATIONS TO PROBLEMS IN GRAPH
THEORY
Elwhere[?],we have shown that the problem to decide whether or not a given t∆of coordination arcs is a solution to the coordination problem,is co-NP-complete.As a result,the decision variant of the coordination problem5turns out to beΣp2-complete6.A complexity analysis also showed the following results: (i)if each agent has only two tasks to achieve,the deci-sion variant of the coordination problem is NP-complete; 5This is the problem to decide whether there exists a coordination t of size K or less.
6Both proofs rely on a reduction from the path with forbidden pairs (PWFP)problem.
(ii )if each agent has four tasks to achieve,the problem to decide whether ∆=∅is a solution to the coordination problem (this is the coordination detection problem)is co-NP-complete and the coordination problem itlf is
in Σp 2;(iii )if each agent has at least 8tasks to achieve,
the coordination problem is Σp
2-complete.
Due to its complexity,it is very unlikely that the coordination problem can be solved in reasonable tim
e.In this ction we will u a reduction to the minimum subt feedback arc t (SFAS)problem 7to find an approximate solution to the coordination problem.The minimum subt feedback arc t (SFAS)problem is an extensively studied minimization problem [4],and fast O (log |V |log log |V |)-approximations have been devel-oped [5],[4].By reducing the coordination problem to the SFAS problem we could u the approximation algorithms to solve the coordination problem.
Briefly,this reduction is bad on the following idea:A solution to the coordination problem consists in find-ing additional constraints ∆such that (whatever intra-agent refinement arcs are added)the resulting graph cannot become cyclic.So why not construct a graph that already contains all possible intra-agent refinements and then lect a feedback arc t F consisting of intra-agent arcs.If we invert all arcs in F then adding this t F −1should break every such cycle.To make a coordination t,the inverted feedback arc t only needs to break cycles that involve more than one agent;cycles within an agent are already taken care of by that agent (becau we assume agent plans to be acyclic).So we need to map coordination instances to minimum subt feedback arc t instances.
Specifically,the transformation from the coordination problem to SFAS is as follows:given a coordination instance (T ,(T 1,...,T n )),construct an SFAS instance (V,A,B )such that 1)V =T ;
2)A +=[≺∪ˆ∆
腾组词
1∪···∪ˆ∆n ]+,with ˆ∆i =(T i ×T i )\(≺i ∪≺−1i )the t of possible refinements for agent A i ;
3)B =≺inter ,i.e.,only tho cycles are considered that interct the t of inter-agent dependencies.To obtain a coordination t,we compute a feedback arc t F of the above SFAS instance,and then we invert the arcs in F to obtain a solution ∆=F −1.We can easily show that if a subt-minimal feedback arc t F
7
The problem given a digraph G =(V,A ),and a subt B ⊆A to find a minimum subt F ⊆A that intercts every cycle in G that contains at least one arc of B .
has been found,then the corresponding ∆=F −1is a solution of the original coordination instance [?].8
Unfortunately,although this approach is ,every solution found by this reduction constitutes a solution to the coordination problem,it has two obvious disadvantages:First of all,the reduction may sometimes be too constraining 9.Figure 2shows an instance where an SFAS solution will constrain the agent’s planning freedom more than necessary:one of the dashed (re-finement)arcs will be placed in a feedback arc t,even though the instance is already coordinated:the only way a cyclic jo
泊有几个读音int plan can be created is if agent A 2choos refinements r 1and r 2.But such a refinement cannot occur,becau it would create a cycle in A 2’s plan.As a result,the O (log(|V |)log log(|V |))-ratio for SFAS is not inherited by the coordination problem.Secondly,
the
Fig.2.Despite the prence of an inter-agent cycle,this instance is coordinated.
approximation algorithms applied to solve the coordi-nation problem are centralized algorithms,leaving no opportunity for the agents to influence the coordination process.
IV.A D ISTRIBUTED C OORDINATION A LGORITHM To allow agents to influence the coordination process we will now prent a distributed algorithm to solve the coordination problem in which an agent receives additional precedence constraints (a subt of the coordi-nation t)only if it decides to accept the constraints.The algorithm is bad on the following idea:in constructing a plan for (T
i ,≺i ),each agent A i can safely start to make a plan for a subt of tasks T 1i ⊆T i that are not dependent (via inter-agent constraints ≺inter )upon tasks assigned to other agents.To determine whether a given task in T i depends on a task assigned to another agent,we let the agents u a common blackboard .This blackboard stores the inter-agent dependency relations.
8
Only arcs in {ˆ∆
1,...,ˆ∆n }may be considered for placement in F ,since arcs in ≺may not be inverted.9
This is not surprising,becau,assuming P =NP ,the coordi-nation problem is outside the class NPO .Minimum SFAS,however,is known to belong to NPO .
Once each agent A i has lected such a subt T1i (which may be empty),the agent informs the blackboard that the tasks t in T1i can be removed from the t T i,together with all precedence constraints in≺that involve task t.Then the agents iteratively start a new round where each agent A i again lects a subt T2i of the t of remaining tasks not dependent on tasks assigned to other agents.The rounds continue until after,say,k≤|T|rounds the t of remaining tasks is empty.As a re
sult,the original task T i of agent A i is partitioned into a t of k possibly empty subts T1i,...,T k i.Now the coordination t∆i for agent A i is constructed as follows:first,all empty subts T j i in {T j
i
}k j=1are removed.Next,for every j=1,...,k−1
and for every pair of tasks t,t :if t∈T j i and t ∈T j+1
i ,
the precedence constraint(t,t )is added to∆i.
To obtain the ts T j i,each agent A i executes the following algorithmic scheme:
Algorithm1
Input:a composite task(T i,≺i)assigned to agent A i Output:a linearly ordered partition(T1i,...,T k i)of T i begin周朝历代皇帝列表
1.let k:=0
2.while T i=∅do
2.1.k:=k+1
2.2.ask the blackboard for the subt F i⊆T i of
tasks that are ,tho tasks t in
T i for which there exists no t ∈T j,j=i,such
that t ≺t
2.3.T k i:=Select SubtFrom(F i)
2.4.if T k i=∅then
2.4.1.Let T i=T i−T k i
2.4.2.Send the t T k i to the blackboard
2.5.el
2.5.1.k:=k−1
end
In each round of the algorithm,agent A i splits off a(possibly empty)t of tasks T k i from T i.In Step2.2,agent A i asks the blackoard to compute the t F i of tasks in T i that are free of prerequisites. In Step 2.3,A i makes a decision which subt T k i of F i it will split off in this round.Note that if no deadlock occurs,each agent A i is able to determine its subt of coordination arcs.Obrve that if all agents repeatedly decide to‘split off’the empty , they wait until they can choo a subtask T j i as large as possible,one or more agent process might deadlock.
Recall that tasks in a block T j i must precede all tasks in the block T j+1
i
.In fact,the t∆i of additional constraints for agent A i is specified by:
∆i=
k−1
j=1
T j
i
×T j+1
i
Thus,the more blocks the partitioning contains,the more restrictions are placed on the t of tasks to be per-formed.Since more precedence restrictions also restrict the freedom of planning of an agent,and thereby reduce the possibility tofind cheaper plans,an agent might be reluctant to split its t of tasks too soon.Instead,it might prefer to postpone splitting off a block until F i is sufficiently large.If possible,an agent would thus prefer to adopt a lazy partitioning strategy,that is:an agent would choo T j i=∅in every round of Algorithm1, unless F i=T i,in which ca it choos T j i=T i. Clearly though,if all agents are lazy(and≺inter is non-empty),then the algorithm deadlocks.
To ensure coordination,more cooperative strategies are needed.The opposite of a lazy agent is a diligent agent:in every round of Algorithm1,a diligent agent choos T j i=F i.If all agents are diligent,the algorithm never deadlocks,and a coordination solution is found. Moreover,we can give some guarantee with regard to the worst-ca performance of the partitioning,as it is not hard to e that if all agents are diligent,then the depth of each agent’s partitioning(the value k for T1i,...T k i) is at most the minimum of|T i|and the depth of the partial order of the complete task T.
In some cas,when a subt of the agents are lazy,and the rest of the agents are diligent,we can still guarantee that Algorithm1runs deadlock-free.The dependencies between agents can be visualized in the agent dependency graph.The agent dependency graph is a directed graph G=(V,E),where V=A(the t of agents),and e=(A i,A j)∈E iff there exist tasks t and t such that t∈A i,t ∈A j,and t≺t .If the agent dependency graph restricted to the t of lazy agents is acyclic,then Algorithm1will not deadlock.
The worst-ca performance of the coordination-by-partitioning approach,measured in terms of the cost of the resulting plan,is bounded by the depth of the partitioning each agent creates for his t of tasks.If an agent A i splits his t of tasks T i into k gments T1i,...,T k i,then the cost of the combined plan for all k gments can be at most k times as high as a plan for his unconstrained t
of tasks T i.As an example,consider
the ca where an agent only has two tasks t1and t2.If there exists no precedence constraint between t1and t2, then we might imagine that an agent can execute both tasks in parallel.By introducing the constraint t1≺t2, the tasks can no longer be executed in parallel,so the cost of the plan may increa—but with no more than the cost of the original plan,since at most all work done on t1must be redone for t2.
In ca all agents are diligent,this means that no agent can have a worst-ca plan cost higher than d times his optimal plan,with d the depth of partial order of the composite task T.
V.A PPLICATION TO COORDINATION IN
MULTI-MODAL L OGISTICS
Our approach enables existing stand-alone planners to be ud in solving planning problems that require the joint effort of veral planners that are dependent upon each other.In this ction we will show how our coordination method can be ud to compo such a multi-agent planning system for logistic planning.
The logistics domain compris transportation of packages in an infrastructure consisting of airplanes, trucks,cities and locations.Each city consists of a t of locations,one of which is the city’s airport.Within a city, trucks can transport packages;between cities,airplanes can transport packages.The aim is to make a plan for picking up a t of packages at their source location and to deliver them at their destination location(which may be located in a different city).
Intra-city ,the transportation of packages with source and destination in the same city,can be carried out by a single truck.Inter-city orders,however, may require cooperation among airplanes and trucks.For example,suppo a package must be transported from location A in city C x to location B in city C y:a truck will drive the package from A to the airport of city C x, then a plane willfly the package to the airport of city C y, andfinally a truck will deliver the package to location B.
In the world’s cond planning&scheduling com-petition,hosted by the AIPS’00conference[6],veral planning domains were to test the competitors’planning systems.All AIPS’00competitors u a centralized approach in which one planning system computes the actions for all vehicles in the infrastructure.As a result, solving the larger instances requires a complex compu-tational problem to be solved.Most of the systems gave up on the larger-sized problem instances.Only a few planners were able to solve all instances.
We applied the coordination method specified by Al-gorithm1to the logistic problems.The airplanes were configured as one coalition using a lazy strategy and each truck adopted a diligent strategy.This approach allows single-agent planners to be reud in the multi-agent planning context;we assigned very simple route planners to both the trucks and the plane agents and applied the coordination approach to allow the planners to plan concurrently and independently from each other.The airplanes’lazy strategy guarantees that optimal airplane plans can be found.But surprisingly,in this benchmark t,even though trucks adopt the diligent strategy,they are still allowed to execute their optimal plans.The result is that if the airplane coalition and the trucks u optimal solvers for their local planning problems,then the resulting joint plan will also be optimal.
The local planning problems are of such a small size that the whole coordination approach including all local planning activities runs extremely fast.Figure3 shows the cpu time needed by our coordination approach compared to the top three hand-tailored planning systems of the competition.Our cpu times were obtained using optimal local solvers for the smaller instances;for the larger instances,we ud local approximations for the route planning problems.In spite of using local approx-imations,we still outperformed the AIPS competitors in terms of plan quality,as shown in Figure4.Although TALplanner and SHOP produce plans of comparable quality,System-R produces considerably longer plans, and its results do notfit in the graph of Figure4.格桑花简谱
VI.R ELATED AND F UTURE W ORK
Except for the multi-agent planning methods already mentioned in the introduction,our approach is also cloly related to the work of Shehory and Kraus[7] where they consider a t of tasks with possibly a t of precedence constraints that have to be distributed among (coalitions)of agents capable of performing certain subts of tasks.However,an important difference with our approach is that Shehory and Kraus assume that performing the tasks requires no planning activity.10 Hence,coordination can be achieved simply by assigning tasks to agents.Therefore,their approach is geared towardsfinding the best allocation of tasks to agents. In our approach,however,we assume that a t of interrelated tasks has already been allocated to agents and we concentrate on methods to ensure coordination 10More accurately,they assume no difference between planning for one task and planning for two or more tasks.
