EUMAS07. Invited Talk Cees Witteveen

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

EUMAS07. Sessions 3 and 4

This afternoon I’m going to attend the session about web services and another one about coordination and negotiation.

Session 3. Agents and Web Services

The room is quite empty, only 10 people. The session begins with our paper Service Discovery an Composition in Multiagent Systems. It’s a review about the most common techniques and algorithms used for standard web services and agent-based solutions. A future works point had to be added, and that has been the first question: ok, a good revision, and now… what are you planning to do? :-) Well, to integrate in a model of service-oriented, agent-based, organisation-focused architecture for open systems. It sounds good but we have to begin working. Current solutions that use gateways, as WSIG or Agent2WS aren’t useful. We need a common language for agents and services to live together in the same platform. Both can provide services (agent services may be more complex) and agents will be responsible of dynamic service composition.

The room is getting crowd, we’re 25 people now and the second talk begins. There’s a problem with his computer, so the chair exchanges 2nd and 3rd talks: Towards a Modular Architecture of Argumentative Agents to Compose Services. A good approach that refers to services in general: not web services, but services provided by agents that form a virtual organisation. The classify the demands according to different dialog types (information-seek, negotiate…). I have to check it with the dialog classification that I used in the AIWS course. They propose three models

  1. individual decision making
  2. social decision making (reasoning about the negotiation process)
  3. social interaction (controls the execution of the agreements)

(I like it) An interesting idea: to use priorities among goals and decisions. A good paper but, at the end, the negotiation of the QoS parameters is done when they have a list of winners, that is, when they have identified the service. Can be this idea be used during the discovery of the service? That would allow to discard those services that never meet the user QoS parameters.

And, finally the last one: Agent-based Framework for Web Service Composition. Agggg! his using comic font… I’m not sure that could take it seriously ;-) Well, a CBR-based solution to compose web services is proposed, so they can use semantic information to match the services (syntactic distance).I can’t see the relationship with agents. Wait a moment, I have it. It’s because they use a distributed solution.

And that’s the end of the session, with 30 people in the room. An active session, with a lot of questions. If this is the rhythm of the EUMAS, it is going to be an interesting workshop.

Session 4. Coordination and Negotiation

After the coffee-break, the last session of the day. The first paper, Plan Coordination for Durative Tasks, is very similar to some things that I’ve written in my PhD. thesis. I have to read it carefully. Furthermore, Cees Witteveen is the coauthor and he has an invited talk tomorrow. I can’t miss it.

The second talk, Bilateral Agent Negotiation With Information-Seeking, defines a framework to argumentative negotiation to an specific resource allocation case. The agents have (i) beliefs, (ii) desires, (iii) actions, that can be external communications or internal–message processing–, (iv) messages, (v) commitments to beliefs, desires and dialogs, (vi) action rules–actions, preconditions, constraints and consequences–, (vii) an evaluation mechanism to determine agent’s intentions and (viii) preferences as priorities over actions. They use protocols for 2 types of dialogs: for information-seeking (query and response) and negotiation( offer, accept and reject). And the permissible messages, the turn taking and the order in the messages are defined for both. After the model is exposed, he shows how they can solve the resource allocation problem with this technique, but there’re some cases without a soloution (cycles or agents that not need anything) because the negotiation process is blocked by self-interested behaviours of the agent.

The third paper is Teamwork Coordination for Vehicle Routing Problem and tries to find the simplest global decision that produces the max. global utility. They solve it using statistical methods from IR (maximum entropy). Sometimes, the utility is obtained not by one action, but by a sequence of actions. Furthermore, some immediate good actions for an agent can be bad for the global final utility, so they have to be punished asap.

Another article about traffic conditions is Anticipatory Vehicle Routing Using Delegate Multiagent Systems, which tries to anticipate and avoid congestions. the road is modelled as a graph where the nodes are the road junctions. Each node has one infrastructure agent and each car a vehicle agent. Before the car arrives a node, the vehicle sends exploratory ants, which ask infrastructure agents for the estimated time for their part of the route. Hundreds of ants can be sent by different vehicles. Intention ants are sent to tentative book a route. The booking have to be refreshed continuously (booking decay). Interesting solution, but with a lot of problems. The most important one is the fairness: I can book every possible route, so the estimate traffic can be faked.

Blogged with Flock

Tags: , , , , ,

EUMAS07. Sessions 1 and 2

Well, I’ll summarise some interesting talks that I’ve seen this morning. In general, all participants seems to be interested in the presentations: a lot of questions that the chair has to interrupt to maintain the session on time. I like it, more that the one in CAEPIA, in Salamanca, some weeks ago (I talked about that).

I’ve attended two sessions: one about trust and reputation and the other about organisations and institutions. As I twittered, the first speaker in the trust session hasn’t appeared, so I had the opportunity of see an interesting speech about agents with hair. You’ll understand that when you see the pictures :-).

A Common Basis for Agents Organisations in BDI Language.
(Also knows as hairy agents :-) Defines a basic agent as a tuple <S, SP> where S is the state and SP the behavioural specifications. And now they extends the state S with the content (Ct) and the context (Cx) of the agent. With this approach, is interesting to see how two agents intersect or how agents can be embedded into others, allowing us to define organisations.

After this paper, we continue in the trust session with the following two talks.

Supporting Experimentation for Trust Models in Virtual Organisations: TOAST

Blogged with Flock