Computing All-Pairs Shortest Paths by Leveraging Low Treewidth (extended abstract)

Of Mechanism Design and Multiagent Planning (extended abstract)

P³C: A New Algorithm for the Simple Temporal Problem

The Simple Temporal Problem (STP) is a sub-problem of almost any planning or scheduling problem involving time constraints. An existing efficient method to solve the STP, called ?STP, is based on partial path consistency and starts from a chordal constraint graph. In this paper, we analyse this algorithm and show that there exist instances for...

Of Mechanism Design and Multiagent Planning

Multiagent planning methods are concerned with planning by and for a group of agents. If the agents are selfinterested, they may be tempted to lie in order to obtain an outcome that is more rewarding for them. We therefore study the multiagent planning problem from a mechanism design perspective, showing how to incentivise agents to be truthful....

Inefficiencies in Task Allocation for Multiagent Planning with Bilateral Deals

Distributed planning in a multiagent environment may give rise to inefficiencies. We study this effect focussing on the task allocation problem. We show that in the worst case, the result of a multiagent approach can be arbitrarily bad in theory when recontracting and multilateral deals are not allowed. This is a more precise result than was...

Plan Repair using a Plan Library

Plan library's have proven their added value to the efficiency of planning. In this paper, we present results on the use of a plan library to plan repair. We show that using a relatively simple library, we can already obtain significant improvements in efficiency compared to plan repair without a library.

Plan Repair as an Extension of Planning

In dynamic environments, agents have to deal with changing situations. In these cases, repairing a plan is often more efficient than planning from scratch, but existing planning techniques are more advanced than existing plan repair techniques. Therefore, we propose a straightforward method to extend planning techniques such that they are able...

Self-interested Planning Agents using Plan Repair

We present a novel approach to multiagent planning for selfinterested agents. The main idea behind our approach is that multiagent planning systems should be built upon (singleagent) plan repair systems. In our system agents can exchange goals and subgoals through an auction, using their own heuristics or utility functions to determine when to...

The two faces of plan repair

Plan repair has two faces. Alternately, a plan repair method looks like a planning method, or looks like a method that does exactly the opposite, i.e., removing actions from a plan. We propose a general framework for plan repair that shows the relation between these two alternating steps. Any plan repair method has this property. This claim is...

Resource Based Multi Agent Plan Merging: Framework and application

We discuss a resource-based planning framework where agents are able to merge plans by exchanging resources. In this framework, plans are specified as structured objects composed of resource consuming and resource producing processes (actions). A plan itself can also be conceived as a process consuming input resources and producing output...

Exploiting Opportunities Using Planning Graphs

Opportunities arise in planning when changes in the environment make new propositions available to the planner. Replanning methods often focus only on the negative effects that changes in the environment have and therefore do not apply well. This paper introduces a method that is specifically focused on the opportunity problem. This method is...

Plan Merging: Experimental results

In this paper we discuss the results of a plan merging algorithm. This algorithm coordinates the plans of multiple, autonomous agents, each able to independently find a plan. This algorithm is evaluated using realistic data from a taxi company. We show that when we allow passengers to be a few minutes later at their destination and share rides,...

A Resource Based Framework for Planning and Replanning

We discuss a rigorous unifying framework for both planning and replanning, extending an existing logic-based approach to resource-based planning. The primitive concepts in this Action Resource Framework (ARF) are actions and resources. Actions consume and produce resources. Plans are structures composed of actions, resource facts and an explicit...

A Method to Integrate Planning and Coordination

An algorithm for replanning