planning archivos - Miguel Rebollo

Service Directory (Alberto Fernández)

Un directorio de servicios «tradicional» para el registro y búsqueda de servicios en la plataforma. Se aporta

independiente del lenguaje para la descripción de los servicios (OWL-S, WSMO, WSDL, SAWSDL, tags, keywords…) -> las descripciones se convierten a n lenguaje común (AT-GCM)
pensado como respositorio de los bundles desarrollados por el AT

=> pending: incluir el manifesto de los bundles como un lenguaje más en la descripción de los servicios para qe se pueda integrar en AT-GCM

Planning Bundles (Alejandro Torreño)

Servicio de planificación centralizada para poder construir agentes que sepan planificar. Formado por 3 bundles:

parser: procesa descripciones en PDDL (2.1) y las transforma en objetos Java
grounding: grounds el dominio de planning (elimina variables instanciándolas a todos los valores posibles). Construye un grafo relajado
planning: proporciona el servicio de planificación propiamente dicho.

Estos bundles pueden servirnos para la composición de los servicios. Ya tenemos nuestra descripción en PDDL (creo que es la 3.0). SI el planificador «por defecto» no sirve bastaría con integrar dentro de otro bundle un nuevo servicio de planificación acorde con las características de nuestro dominio (abierto, dinámico, descentralizado)

¿Podría hacerse otro bundle que transforme de Drools a PDDL o directamente a los objetos Java? De esa forma podía usarse también en la parte de BDI con Jason.

Otra cosa interesante sería ver cómo envolver un planificador «normal» en un bundle. Podríamos hacer la prueba con el que está incluido en el servicio web. En ese caso se puede trabajar directamente con las descripciones en PDDL (sin traducir)

Negotiation Probabilística (Antonio Bella)

Permite modelar procesos de negociación dando una serie de parámetros para que un agente sea capaz de determinar el precio óptimo para una transacción en concreto. Es un proceso completamente informado

Técnicas incluídas en el bundle:

Best Local Expected Profit (BLEP)
Maximun Global Optimisation (MGO)

MMUCA (Jesús Cerquides)

Mixed multi-unit combinatory auction: Resolver subastas sobre procesos complejos de forma colaborativa (ej: células de fabricación flexible). Se incluyen materiales, herramienta y procesos. Las subasta se emplea para construir la mejor estructura posible -ej: demo eProcurement con milling machines-

Funcionamiento del bundle: los participantes le envian sus pujas y el bundle determina la combinación ganadora, con la que crea el workflow correspondiente en una institución electrónica.

Sería interesante comparar esto (y el trabajo de Jar y Merichel sobre CSP distribuidos) con las redes de consenso. Pero para eso antes necesitamos que las redes sean capaces de tener en cuenta varios atributos simultáneamente (de momento MMUCA está en el mismo caso y sólo optimiza precio). Debemos abordar eso cuanto antes para que sean usables. Si las dimensiones son independientes o si están correlacionadas positivamente creo que la convergencia estará también garantizada, pero ya con dos variables incompatibles el sistema ya no tiene solución para nosotros (oscilante) -> es necesario el tener un criterio de parada que se propague en toda la red (¿agentes monitores cuya presencia garantice el cumplimiento de ciertas propiedades o impida comportamientos no deseados?).

Sugerencia: el trabajo de Martí con los commitment managers pueden servir para la gestión del tiempo en MMUCA en una ronda independiente (en principio, es más sencillo para probar).

Combinational Auction (Matteo Vasirani)

Local search algorithm to determine winner in combinatorial auctions. Algoritmo estocástico

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

Etiqueta: planning

[ATmeeting] Mapa de las tecnologías AT/bundles

EUMAS07. Invited Talk Cees Witteveen