A very interesting speech about how autonomous agents can coordinate plans, balancing the plan construction and its coordinate execution. A good introduction to the topic.
1. plan coordination methods
He begins with an easy example in which two agents fall in a deadlock if they have to coordinate their tasks but they have their own preferences about the order in which the agents want its actions to be executed (I’ve seen this problem yesterday in a session). So the problem is that we have a set of autonomous agents, a partially ordered set of tasks, own preferences and dependences among the agents. How can we solve this coordination problem?
- after planning: conflict resolution by merging or revising the plan
- during planning: preventing or solving conflicts
- before planning: prevent conflicts by examining the constraints. This is the most interesting part
2. minimun coordination methods
The before planning problem you have a set T of independent tasks distributed into a set of autonomous agents A where the agents plans automously. We enforce the agents to eliminate those constraints that create cycles in the coordinate plan. But this problem is complex to solve.
First, how we can verify that a plan is coordinated? Two techniques: fixed coordination verif. and free coordination verif. both at least are co-NP complete problems :-(
3. efficient methods for approximating minimum coord
They are hard problems: EFixC is still NP-complete for agents with 2 tasks, but there are heuristics,as label setting algorithm, to reduce the cost.
The label setting alg. adds the tasks in «layers», beginning with tasks without precedents agent by agent. All arcs (dependences) among tasks always will be from lower layers to higher ones, so we can ensure that we are avoiding inter-agent cycles. It works particularlly well with certain structures. (i) if the agents form a chain with length k, the (ii) if agents form an star, with a central «server».
4. the price of autonomy
Individual agents pay a price for their autonomy in order to get plans coordinated. as the division between the sum cost of an optimal local plan / the cost of the optimal global, joint plan. If this value is too high it is not worthy.
5. two applications:
multimodal transportation
We have to order a sequence of simple transportation tasks between to locations in two cities. The cost of the plan is measured by #moves + #(un)load actions. They’ve compared the coordination approach over benchmark set with planners that treat the whole problem and with planners that use local planners (for each agent) plus coordination (STAN, TAL and HSP among others). The conclusion is that if they combine HSP with their min. coord. method, the efficiency of the planner is increased dramatically.
context aware routing
We’re running out of time, so he’s not going to explain with detail the second example. They’ve compared fixed path scheduling with time windows path routing. The last one has better results.
To conclude…
The pre-planning coordination is suitable for coordinate autonomous planning agents. This approach decompose complex problems in minimal changing instances. The price of the autonomy determines the quality of the decomposition.
It’s been a good talk. I’ve remembered past times… and it’s given be some goods ideas to be used in the discovering and composition of semantic web services using hypergraphs and HSP-based planning algorithms.
Blogged with Flock