Resource Based Multi Agent Plan Merging: Framework and application

Resource Based Multi Agent Plan Merging: Framework and application

De Weerdt, M.M.
Van der Krogt, R.P.J.
Witteveen, C.

Electrical Engineering, Mathematics and Computer Science

Software Computer Technology

2003-12-19

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 resources. A plan can be improved if we can remove actions from it while maintaining goal realizability.We describe a reduction property that specifies how one agent can improve its plan by using (free) resources from another agent in such a way that goal realizability is preserved. The plan-merging algorithm we use to specify plan merging in a multi-agent context is an iterative, distributed, any-time application of this reduction property. The performance of this algorithm has been evaluated using a planning data set obtained from a taxi company. The quality of the algorithm is measured by the decrease of the total distance driven by all taxis. By allowing passengers to share rides, we create a trade-off between the additional travel time of passengers and the total drive distance. Allowing passengers to be a few minutes later at their destination and share rides, a significant improvement of the plans can be obtained (from 5% up to 30% reduction of the taxi driving distance).

http://resolver.tudelft.nl/uuid:246a1660-2c7e-499f-aa86-4ecbd2361ee6

PlanSIG 2003: 22nd Annual Workshop of the UK Planning and Scheduling Special Interest Group, Glasgow, UK, 9-10 December 2003

Institutional Repository

conference paper

(c) 2003 The Author(s)