ActionPlanningForGTS ICAPS05 VVPS

Action Planning for Graph Transition Systems: 

Action Planning for Graph Transition Systems Stefan Edelkamp Shahid Jabbar Computer Science Department University of Dortmund, Dortmund, Germany Alberto Lluch-Lafuente Department of Informatics, University of Pisa, Pisa, Italy

Graph Transition Systems: 

Graph Transition Systems

Graph Transition Systems: 

Graph Transition Systems A graph transition system (GTS) is a pair <M,g>, where M is a weighted transition system and g is a partial graph morphism. The weights of a transition system is modeled by a generalize cost-algebra based on monoids structure. See “Edelkamp, Jabbar, and Lafuente, Cost-Algebraic Heuristic Search, in Proc. of 20th National Conference on Artificial Intelligence (AAAI’05), July 2005, Pittsburgh, PA. (to appear).” for more details. Applications: Biology – Changing molecular structure, Networks – Clients appearing and disappearing.

Objectives: 

Objectives How to model and check GTS? How to encode the application of partial graph morphism? How to deal with flexible goals? How to guide the search process? Solution: Model the problem of checking graph transition systems in PDDL and use planning heuristics to guide the search process.

Outline: 

Outline Arrow Distributed Directory Protocol – An example of GTS. PDDL Encoding of Arrow Distributed Directory Protocol. Experimental Results Performance: Planner vs. Model Checker Scaling behavior of the model Conclusions

Directory Service Protocol: 

Directory Service Protocol Assume a distributed environment. Clients: The nodes in the distributed network e.g., different computers. Mobile Objects: Could be a file, a process or any other data structure. It can be transmitted over a network from one node to another. It “lives” only on one node at a time. Purpose of a Directory Service: Navigation: To provide the ability to locate a mobile object. Synchronization: To ensure mutual exclusion in the presence of concurrent requests.

Usual Approach: 

Usual Approach “home”-based structure. Each object has its own “home”. “home” keeps track of the object’s location. All requests are send to the “home”. “home” sends a message to the client currently holding the object. That client forwards the object to the requesting client. Bottleneck: Communication costs between “home” and clients.

The Arrow Distributed Directory Protocol (Demmer and Herlihy): 

The Arrow Distributed Directory Protocol (Demmer and Herlihy) Based on the idea of a trail of pointers Distributed Network G = (V,E,w) z u4 u v w u3 u2 u1 o

Properties of the Protocol: 

Properties of the Protocol If link(v) = v (self-loop) => The object either resides at v, or will soon reside at v. Else, the object resides some where in the region of the directory containing link(v). v w link(v) = w o

Messages and Constructs: 

Messages and Constructs link(u,v): Defines the spanning tree. find(v): Request for the object issued by the node v. move(v): The object is free to be moved to v. It travels with the object, following the links in the original graph. pending(u,v): Every link(u,v) has a buffer that keeps the request. Not a FIFO, but reliable. queue(u) = {v, NULL}: A predicate attached with every node. Tells that u has to transfer the object to v when it is finished with the object.

Working of the Protocol: 

Working of the Protocol v issues a request find(v) for the object. find(v) u issues move(v) when it is finished with the object o find(v) inserted in the pending buffer move(v) A queue predicate is declared for v: queue(u) = v The object is moved to v following the shortest path in G (blue edges)

Concurrent Requests: 

Concurrent Requests find(v) stuck in the communication channel. w also issues a request in the meanwhile. find(v) stuck in the com. channel find(w) w’s request would be diverted to v instead queue(v) = w z also issues a request find(z) o queue(u) = z find(v) released find(v) queue(z) = v All future requests will be forwarded to w Object Path: u – z – v - w

Advantages: 

Advantages A distributed queue structure. Object request messages travel the shortest path in the spanning tree and not in the original graph. The queue structure ensures locality: all requests will go directly to the object or to another terminal. Do not have to pass through a “home”.

Properties to Verify / Types of Goals: 

Properties to Verify / Types of Goals Can a particular node u be a terminal? (Subgraph matching) Can a particular node u be a terminal and all arrow paths end at u? (Graph Matching) Can an arbitrary node ui be a terminal? (Subgraph isomorphism) Can an arbitrary node ui be a terminal and all arrow paths end at ui? (Graph isomorphism)

Part IIPDDL Encoding: 

Part II PDDL Encoding

PDDL Encoding: Morphism as PDDL Actions: 

PDDL Encoding: Morphism as PDDL Actions A morphism operation that inverses an edge can easily be defined as a very simple action. (:action morphism-inverse :parameters(?u ?v - node) :precondition (link ?u ?v) :effect (and (not (link ?u ?v)) (link ?v ?u)))

PDDL Encoding of Goals: Graph and Subgraph Matching.: 

PDDL Encoding of Goals: Graph and Subgraph Matching. Subgraph and graph matching are easy to encode. Encode the goal graph with (link u v) and owner with (owner w) predicates.

PDDL Encoding of Goals: Subgraph Isomorphism: 

PDDL Encoding of Goals: Subgraph Isomorphism Goals are strictly more expressive. Need an existential quantification over all the nodes to be described. ADL (Pednault 1989)  (:goal <existential-expression> <goal-condition>) Using ADL, subgraph isomorphism can be encoded as (:goal (exists (?n - node) (owner ?n)))

PDDL Encoding of Goals: Graph Isomorphism: 

PDDL Encoding of Goals: Graph Isomorphism Existential quantifier can again be used .. (:goal (exists ?v0 ?v1 ?v2 ?v3 ?v4 ?v5 - node) (and (link ?v0 ?v0) (link ?v1 ?v0) (link ?v2 ?v0) (link ?v3 ?v1) (link ?v4 ?v0) (link ?v5 ?v4) (owner ?v3)))

Performance: Model Checker(HSF-Spin) vs. Planner (FF) – Subgraph Matching: 

Performance: Model Checker(HSF-Spin) vs. Planner (FF) – Subgraph Matching

Scaling Behavior of the Model: 

Scaling Behavior of the Model 1.9 GB

Conclusions: 

Conclusions First such efforts to model GTS with PDDL. Advantages: Planning heuristics can be employed directly. Successfully modeled Arrow Distributed Directory Protocol. Still some limitations in modeling the full-fledged specification of GTS. Dynamic insertions and deletions of nodes and edges. Can be circumvented to some extent by using a pool of available objects.