Plan Merging in Multi-Agent Systems. Mathijs de Weerdt

Plan Merging in Multi-Agent Systems

Mathijs de Weerdt

Illustrations: Welmoed Kreb Cover illustration: Welmoed Kreb Cover design: Joke Herstel, Wenk


Proefschrift

ter verkrijging van de graad van doctor aan de Technische Universiteit Delft, op gezag van de Rector Magnificus prof.dr.ir. J.T. Fokkema, voorzitter van het College van Promoties, in het openbaar te verdedigen op maandag 15 december 2003 om 15:30 uur door Mathijs Michiel DE WEERDT doctorandus in de Informatica geboren te Alkmaar

Dit proefschrift is goedgekeurd door de promotoren: Prof.dr.ir. H.J. Sips Prof.dr. J-J.Ch. Meyer Samenstelling promotiecommissie: Rector Magnificus Prof.dr.ir. H.J. Sips Prof.dr. J-J.Ch. Meyer Dr. C. Witteveen Prof.dr.ir. P.H.L. Bovy Prof.dr.ir. R.E.C.M. van der Heijden Prof.dr. C. Roos Dr. K.S. Decker Dr.ir. N. Roos

voorzitter Technische Universiteit Delft, promotor Universiteit Utrecht, promotor Technische Universiteit Delft, toegevoegd promotor Technische Universiteit Delft Katholieke Universiteit Nijmegen Technische Universiteit Delft, reservelid University of Delaware, VS Universiteit Maastricht

TRAIL-Thesis Series T2003/8, The Netherlands TRAIL Research School Published and distributed by: Mathijs M. de Weerdt E-mail: [email protected] ISBN: 90-5584-052-1 Keywords: multi-agent systems, AI planning, coordination, resource allocation c 2003 by Mathijs M. de Weerdt Copyright All rights reserved. No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission of the author. Printed in The Netherlands

Preface The research presented in this thesis was performed at the Faculty of Electrical Engineering, Mathematics and Computer Science (EEMCS), formerly called Information Technology and Systems (ITS) of the Delft University of Technology. Within the Parallel and Distributed Systems (PDS) group, a project on Collective Agent-Based Systems (CABS) was started in 1998. The CABS program aims at developing specification methods, algorithmic techniques, and implementations of large-scale agent-based systems and organizations of agent-based systems. Since these formalizations and algorithms can contribute to “the solution of scientific, business and societal problems in the field of transport, infrastructure and logistics”, this research is carried out within the research school on Transport, Infrastructure and Logistics (TRAIL, 1994–), more specifically within the Delft interdisciplinary research center (DIOC) research program Seamless Multi-Modal Mobility (SMM).

The ‘Collective Agent-Based Systems’ (CABS) projects The research projects within the CABS project concern two different themes. On the one hand, a theory and methods are being developed to realize inter-organizational coordination. On the other hand, incident management methods are studied to guarantee the execution of coordinated plans in dynamic situations. This work on incident management is carried out by two colleagues. Jonne Zutt (2000) concentrates on the recognition of unexpected events (diagnosis) and the reactions on an operational level, whereas Roman van der Krogt (2000; 2003) is more interested in how a whole plan should be modified on a tactical level to deal with more serious events that affect the applicability of such a plan. The research on inter-organizational coordination in the CABS project focuses around the coordination of the planning of actions. Initially, a distinction is made between preand post-planning coordination processes. Jeroen Valk (2001) studies multi-agent task allocation protocols to guarantee that each agent is able to construct its own plans autonomously (pre-planning), while the work in this thesis shows how to coordinate such separately constructed plans afterwards (post-planning). Eventually, the planning and the coordination processes should be integrated into a single coordinated planning process. i

ii


Finally, the theme on inter-organizational coordination is supported by the development of a specification language for coordination processes in multi-agent systems. This work uses a combination of game theory and (modal) logic, and is carried out in cooperation with the Intelligent Systems group at Utrecht University (Harrenstein et al., 2001). The first main contribution of this thesis is a formal framework to express multi-agent planning problems and multi-agent plans in an object oriented way. This framework can also be used on the operational level to formulate the replanning of actions. A second contribution is a method to improve multi-agent plans. This method is formally introduced and analyzed as well as subjected to an empirical investigation using a data set from a taxi company. These techniques for solving multi-agent or multi-organizational planning and coordination problems in general will help to solve specific coordination problems in many domains, and not in the least, in transportation domains.

Acknowledgments I would like to thank everyone who supported me while I was writing this thesis. First, and foremost, I thank Cees Witteveen, who was and is always available to guide and encourage me. Second, I thank John-Jules Meyer for his enthusiasm, and Henk Sips for trying to speed up my finishing this thesis. All of them always combined their constructive comments with stimulating statements. Furthermore, I thank Nomi Olsthoorn, who not only helped me with her favorite statistical tool, but also supported me upon drawbacks and made me aware of my luck (especially compared to hers). I am grateful to Roman van der Krogt, because he almost always offered useful critique and a cup of tea whenever I was stuck. I thank Andr Bos and Hans Tonino for their ideas and support in the first couple of years of my research, and Jonne Zutt, Jeroen Valk, and Paul Harrenstein for their easy company at every CABS occasion. I am also very grateful to all my other colleagues in the Parallel and Distributed Systems group (Arjan, Dick, Frits, Jan, Johan, Kees, Koen, Leo, Linda, Marcel, to name the most important ones) for creating a friendly and healthy (well, maybe except for the cake on Friday) working environment, and especially Leon Aronson for proof-reading most of my thesis. Besides, I am quite happy that Ard Biesheuvel and Lon Planken finished the CABS-planner before I finished my thesis. I appreciated all the (social) events, courses and all kinds of forms industriously provided by TRAIL, and I thank Piet Bovy and Ruud Sommerhalder for making this research school, the SMM project, and more specifically my own research within CABS possible. I thank Wiebe van der Hoek for pointing out the CABS research program and driving me to Delft for my application visit. More concrete results of people helping and supporting me are the data set used, which

Preface

iii

is provided by Pim van der Stoel from Tens B.V. and Ron Kooi from Taxi Zeevang, the help I received from Mirjam Nieman to improve my style of writing, and the illustrations about the planners Pete, Monica and Ralph transforming to a (merged) taxi made by Welmoed Kreb. I would also like to thank Robbert Kok for his warm welcome in Delft and together with Victor van Rijn and Hiske Wegman for their friendship and inspiring discussions. I thank my parents for their stimulating interest and encouragement, my brother Maarten for his very good friendship ever since I left home and Barbra for her support when Maarten had a heart operation and my parents were in Ecuador. Finally, I am very happy with the sea scouts from Marco Polo Alkmaar and all my friends there, because whenever I am among them I completely forget all about this research and its unsolved problems.

iv


Contents 1

Introduction 1.1 Inter-organizational coordination . . . . . . . . . . . . . . . . . . . . . .

1 1

2

Research body

3

3

Conclusions and perspectives 3.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Extensions of the formalism . . . . . . . . . . . 3.2.2 Extensions of the plan merging algorithm . . . . 3.2.3 Further experiments . . . . . . . . . . . . . . . 3.2.4 More advanced multi-agent planning algorithms

5 6 7 7 8 9 9

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

A Mathematical notations and definitions

11

Bibliography

13

Index

15

Summary

17

Samenvatting

21

Curriculum Vitae

25

v

vi


Chapter 1 Introduction 1.1

Inter-organizational coordination

Somewhere in a medium to large city, Pete is working in the office of a moderately small taxi company, called P-Tax. Pete is the planner of this company. His job is to assign transportation tasks to the taxi-cabs. First, he enters transportation requests from customers into a database in his computer. Then a planning algorithm composes a possible schedule. Pete is glad to have such help, because especially planning the shared transportation in vans, also offered by this company, can become quite complicated. During the day new requests come in, and the schedule is updated regularly. Sometimes, when the number of requests is extraordinarily high, Pete contacts Monica, a befriended planner at another taxi company (M-Cabs) by phone, and asks for help. Usually, M-Cabs is able to take over some of the requests. Once or twice a day a customer requests an unusually long trip. If the cab concerned has to return empty, this is a very inefficient use of resources. Therefore, whenever he can, Pete checks with Monica to see if they have a trip in that direction as well, or even better, a trip on the way back. If possible, the planners agree on combining their requests. A similar agreement is sometimes made when passengers need to be picked up in a region or suburb where one company has some cars available nearby, while the cabs of the other are at the other side of town. Both taxi companies P-Tax and M-Cabs profit from such cooperation.

1

2


Chapter 2 Research body See Example 2.1 for an interesting example. Example 2.1. An example of a resource fact where terms are variables or functions on terms is the resource fact taxi2 (p : plate, l : loc, 3 − c : capacity) that specifies a taxi at an unspecified location l with capacity (3 − c). Such resource facts are very useful to define goals and conditions for actions. Note that this resource fact has identity value 2. To formally define terms and such resource facts, we first introduce all symbols that can be used in our language. As said before, a formula in RL is typically used to describe a state of the world by a conjunction of resource facts. Each resource fact can have several attributes of different sorts. So we need symbols for conjunctions, sorts, variables, constants, and the resource predicates. Theorem 2.2. (Haslum and Jonsson, 1999) Complexity of conformant planning. Deciding the existence of a conformant plan (sequence) for a problem Π with an unobservable propositional domain and actions is EXPSPACE-complete.1 In a multi-agent system, agents often perform actions unexpectedly and independently of each other. When each agent is planning on its own without communicating and coordinating with the other agents, each agent has to solve some sort of non-deterministic planning problem. Theorem 2.2 and the complexity analysis of contingent planning show that non-determinism in planning is EXPTIME-hard. So we can conclude that such an individual approach 1 The

class EXPSPACE is the class of decision problems that can be solved using an amount of space bounded by 2 p(n) , where p is a polynomial and n is the input length. It is known that the class EXPTIME⊆EXPSPACE contains problems that are intractable (Garey and Johnson, 1979, Theorem 7.16 in), even if P=NP.

3

4


G

unload(passgr) move(B,C) load(passgr) Legend move(A,B) a()

I

I G

action set of initial states set of goal states

Figure 2.1: A sequence of actions (plan) leading from each of the initial states in I to one of the goal states in G.

Chapter 3 Conclusions and perspectives The aim of this thesis was to provide a problem definition, a framework, and methods for multi-agent planning. These three contributions should help to improve techniques for inter-organizational coordination. For example, the taxi companies P-Tax and MCabs like to have a coordinated planning system to take advantage of situations where coordination can lead to a significant reduction in the operational costs. It is the year 2010. Both taxi companies P-Tax and M-Cabs have been running the new version of the taxi planning and scheduling software (TPSS) with integrated coordination modules for more than a year now. Recently, the (now) managers Pete and Monica have signed a coordination agreement to formally define how to split the revenues of sharing and exchanging rides. The new planning personnel at the office is reviewing the automatically generated schedules. Their main task is to keep in touch with the taxi drivers executing orders to deal with unexpected events and to explicitly approve (or disallow) the execution of a coordinated ride. Furthermore, they provide the TPSS with up-to-date information on the availability of taxi drivers, road blocks, queues, the weather, special events, etc., and they tune the parameters of the TPSS such as the slack on the drive times, and the time margins for picking up passengers. Multi-agent planning techniques are especially useful to coordinate plans and processes between organizations. However, further research on the multi-agent planning problem and development of distributed planning heuristics will also enable the use of these techniques in situations where the autonomy and privacy of the agents is a less important factor, and where currently centralistic planning and scheduling techniques are used. For example, the plans of subdivisions of a company, of departments of a hospital, or of divisions of an army may be more efficiently approached by multi-agent planning techniques. 5

6


In general, whenever a problem can naturally be decomposed into related subproblems, it can be modeled and solved as a multi-agent problem. See Algorithm 3.1 for more info. Algorithm 3.1. S OMETHING

SMART

1. do this 2. and do that 3. for my sake do (a) do a lot of this 4. print results

3.1

Conclusions

Most multi-agent planning research focuses on a specific practical instance of the multiagent planning problem. In this thesis, multi-agent planning was formally defined as the combination of the planning problems of a set of agents in the same environment. The formal problem turned out to be strong and flexible enough to model a realistic multiagent planning problem in the taxi scheduling domain. Multi-agent planning was proved to be an extremely difficult problem, i.e., PSPACE-complete. This problem definition can be used to give more structure to the process of comparing different approaches to multi-agent planning. In existing frameworks to describe planning algorithms, a state of the world is described by an unstructured set of properties of all objects relevant for the planning problem. Especially for multi-agent planning problems, properties of objects should be modeled in a more object-oriented way. The framework introduced in this thesis consists of a subset of linear logic on so-called resource facts and an operational semantics. The resource facts represent resources or products and describe all the properties (attributes) of such an object at a specific time. Actions are rules to transform a set of resource facts. To model more complicated domains, the formalism supports the use of constraints on the attributes of a resource fact to impose restrictions on the execution of an action. Using resources as the atomic objects of a planning problem and actions as resource-consuming and resource-producing processes appeared to work very well in a practical multi-agent planning problem. The resource language was used to derive that an action can be removed from a (multiagent) plan while maintaining the realizability of all goals (of all agents) if for each used output resource a replacement can be found. Moreover, this condition was used to design

Chapter 3. Conclusions and perspectives

7

a polynomial any-time approximation algorithm for the plan merging problem. The plan merging problem was defined to be a search problem of finding available resource facts to satisfy a given set of requests for removing one or more actions. This problem was proved to be NP-complete, which is plausibly less difficult than the multi-agent planning problem.1 A ground version and a more flexible version of the plan merging algorithm were proved to have a time complexity of O(n2 ) and O(n1+c ), respectively, where c denoted the maximal size of an action. The properties of the ground plan merging algorithm were analyzed by doing experiments using real data from a taxi company. A schedule for 35 taxis was used to create a hypothetical experiment. In this experiment we divided the taxis randomly over a set of artificial taxi companies (i.e., the agents). The plans of these agents were then merged using the plan merging algorithm. Evidence was gathered showing that the ground plan merging algorithm had a very good any-time behavior and a quadratic time complexity with a very low constant. Further experiments showed that when the taxi company would allow passengers to share a taxi, the reduction of the costs of a plan were strongly related to the additional travel time of passengers. For example, for large plans and a pick-up and drop-off margin of at most 6 minutes, an increase of 11% in travel time was shown to result in a distance reduction of about 13%. To round off, we conclude that both the formalism and the algorithm work quite well on realistic data and we believe that the proposed problem definition and the formalism are useful for further research on coordinated planning.

3.2

Future work

This thesis attempted to find general methods to solve instances of the multi-agent planning problem. The solid foundation defined here will help to formulate subsequent research aims, and hopefully also to describe new research approaches. Further study includes extending the formalism, improving the plan merging algorithm, doing more experiments, and, last but not least, developing more advanced coordinated planning methods. Each of these issues is detailed in the following subsections.

3.2.1

Extensions of the formalism

The action resource formalism (ARF) is quite powerful, but some planning problems and algorithms have aspects that cannot be modeled explicitly in the ARF. For example, sometimes the duration of an action is relevant. This may be modeled by including time 1 It

is assumed that NP6=PSPACE (Garey and Johnson, 1979).

8


attributes in all consumed and produced resources, and by parameterizing the state of the world (during the execution of the action) by a time variable t. The attributes of some (produced) resource can then be described by a function of t. In some applications the non-existence of resources is required, e.g., a goal could be “I do not want any passengers”. The semantics of this goal is that for the resulting plan P for any attributes x1 , . . . , xn the resource passgr(x1 , . . . , xn ) 6∈ Out(P). Such a requirement may be translated to constraints on the goals and the actions, or it should be defined in the operational semantics. Furthermore, sometimes it is necessary to define that a resource should not occur in any state during the execution of a plan. This is an invariant over a plan about a resource that should not be produced anywhere in the plan. A third example of a possible required extension of the ARF is when we need to be able to specify in the problem description that we would like to have as much of something as possible. This may be modeled either by specifying that we need as much of the resource (e.g., money) as possible, or that the attribute amount of this resource should be as large as possible. In some multi-agent situations, agents may need to include a joint action, such as joining a meeting or handing over a valuable package. In the ARF we have no method to describe actions that require the direct involvement of multiple agents, other than defining an action in one of the agents’ plans that needs resources from the other agents. If an application domain requires one of the above issues, we need to thoroughly investigate the best way to extend the formalism.

3.2.2

Extensions of the plan merging algorithm

The plan merging algorithm may also need a couple of extensions. In many domains, agents can only benefit from the exchange of a set of resources. A combinatorial auction (Sandholm, 2002, e.g., ) is required to deal with these kind of exchanges. This extension also requires a formal analysis of plan reduction with more than one action. Another interesting extension is to auction resources to private individuals as well, e.g., via eBay (2003), or in the transportation domain via specialized websites. And then, especially when private individuals are involved, the algorithm should be able to deal with unfair and selfish agents (Ronen, 2000). To use the plan merging algorithm in a somewhat more dynamic environment, we need the functionality of adding requests during execution. Such an extension is a step towards more advanced multi-agent planning algorithms. However, first, the plan merging algorithm should be tested on other data sets and in more domains.

Chapter 3. Conclusions and perspectives

3.2.3

9

Further experiments

The experiments presented were based on a couple of strong assumptions. We need to check the validity of these assumptions by doing plan merging on this data while taking into account (i) breaks of taxi drivers, (ii) the long-term effects of picking up passengers on the rest of the plan, and (iii) an estimation of the travel time that includes the distance on the road map, the number of traffic lights, and queuing time based on the time of the day. We also need to check that there is no communication overhead. Furthermore, the assumption has been made that the artificial set-up of the experiment is realistic (the centralistic planning from one company was used to derive plans for a whole set of much smaller taxi companies). If information from several companies in the same region and from the same days is available, this assumption can be verified. Such information can also help to test different award models for companies that help others. The conclusions on the plan merging algorithm can be made even stronger if the algorithm is run on other data sets, including those from other taxi companies, but preferably also data sets from other domains, such as transportation scheduling, pizza delivery, hospital scheduling, computer games, robot rescue teams, army mission planning, or controlling cooperating satellites. It is also useful if simulation data for these domains can be generated, because then they may be used as benchmarks. Benchmarks help to compare different plan merging algorithms, or even other multi-agent planning methods.

3.2.4

More advanced multi-agent planning algorithms

The most important further study should be on the integration of the coordination in the planning process itself. If agents can communicate and adjust their plans while these are under construction, conflicts can be solved more elegantly, and agents that do not have enough resources themselves might still be able to construct a plan. An initial proposal for such a coordinated planning system has already been made (De Weerdt and van der Krogt, 2002), based on a forward heuristic. In this thesis the basis for such an extension was laid out by the introduction of a formalism and algorithms to coordinate plans after they have been formed. Several existing planning techniques such as task reduction planning and partial order planning can, in principle, also be used in a coordinated planning system. Each technique requires different modifications of the multi-agent planning system. For example, for partial order planning we need to describe some additional conditions on the existence of resources (for example during an interval (IPC). For other domains, task reduction planning methods seem more appropriate. In that case we need at least subplans, an abstraction of plans, such that they look just like actions, and a plan library (Van der Krogt et al., 2003).

10


Specialized, domain-specific optimization algorithms for subproblems usually perform better than a general (planning) problem solver, for example a shortest path algorithm is much faster than using a planner to determine a shortest route in a graph. It is therefore valuable that such algorithms can easily be incorporated in a multi-agent planning system, for example as lower and upper bounds. This way one sometimes can still have the ease of having a method that can be applied in many domains, while also being able to take advantage of long lines of specialized problem-solving research. Probably, however, this is not always possible. Finally, for many real applications, the execution of a plan needs to start even before the plan has been completed. Consequently, also for multi-agent planning we need to look into methods to do planning and execution simultaneously.

Appendix A Mathematical notations and definitions Some other relevant information. . .

11

12


Bibliography de Weerdt, M. M. and van der Krogt, R. P. (2002). A method to integrate planning and coordination. In Brenner, M. and desJardins, M., editors, Planning with and for Multiagent Systems, number WS-02-12 in AAAI Technical Report, pages 83–88. AAAI Press, Menlo Park, CA. eBay (2003). eBay - The World’s Online Marketplace. http://www.ebay.com/. Garey, M. and Johnson, D. (1979). Computers and intractability – a guide to the theory of NP-completeness. W.H. Freeman and company, New York, NY. Harrenstein, P., van der Hoek, W., Meyer, J.-J., and Witteveen, C. (2001). Boolean games. In Proceedings of the Eighth Conference on Theoretical Aspects of Rationality and Knowledge, pages 287–298. Morgan Kaufmann Publishers, San Mateo, CA. Haslum, P. and Jonsson, P. (1999). Some results on the complexity of planning with incomplete information. In Proceedings of the Fifth European Conference on Planning (ECP-99), volume 1809 of Lecture Notes on Artificial Intelligence, pages 308–318. Springer Verlag, Berlin. Ronen, A. (2000). Solving Optimization Problems among Selfish Agents. Ph.D. thesis, Hebrew University of Jerusalem. Sandholm, T. W. (2002). Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135(1–2):1–54. TRAIL (1994–). TRAIL mission statement: Research school for transport, infrastructure, and logistics. http://www.rstrail.nl. Valk, J. M., Witteveen, C., and Zutt, J. (2001). Approximation results for multi-agent planning systems. In Proceedings of the fourth Pacific Rim International Workshop on Multi-Agents (PRIMA), pages 387–398. ACM Press, New York, NY. van der Krogt, R. P., Bos, A., de Weerdt, M. M., and Witteveen, C. (2000). An algorithm for replanning. In Proceedings of the Twelfth Belgium-Netherlands Artificial Intelligence Conference (BNAIC-00), pages 21–28. 13

14


van der Krogt, R. P., de Weerdt, M. M., and Witteveen, C. (2003). A resource based framework for planning and replanning. In Proceedings of the 2003 IEE/WIC International Conference on Intelligent Agent Technology (IAT-03). Zutt, J. (2000). Transport Control in a Multi-Agent Setting. Master’s thesis, Delft University of Technology.

Index CABS, i complexity of conformant planning, 3 EXPSPACE-complete, 3 symbols, 3

15

16


Summary Plan Merging in Multi-Agent Systems

By coordinating their plans extra carefully, organizations may be able to come up with activities that do not conflict and whose resources are used more efficiently. This is very important when coordinating logistic processes, such as the planning of routes for taxi companies and the efficient allocation of transportation orders to trucks for transport companies. However, also outside the transportation sector, operational costs can be significantly reduced by better cooperation. Think for example of the coordination of several armies during a UN peace mission or of the coordination of different departments within a hospital. The coordination of activities planned by several autonomous companies is a very important aspect of inter-organizational coordination. Most organizations, however, do not want to relinquish all information concerning their private plans, as they are afraid of losing their autonomy. Hence, in general, organizational coordination problems cannot be solved centrally. Therefore, we have to search for coordination methods that are able to coordinate individual plans in a distributed way, while respecting the privacy of the individual planning agents (companies, people). This is exactly the topic of multi-agent planning, where methods are developed to solve a set of related (single-agent) planning problems. In this thesis we develop a resource-based framework to model and solve such multiagent planning problems. In this Action Resource Framework (ARF), resource facts are taken as the central concepts for both planning and coordination of actions. They are used to give an exact description of the primitive objects and their properties in a planning domain. In the taxi domain, these resource facts are for example the taxis, the drivers, and the passengers. Actions in this framework are processes that consume and produce such resource facts, e.g., the movement of a taxi, or passengers getting in or out. In general, an action has a precondition to denote the required input resource facts, and a description of the output resource facts produced by the action. Goals are specified by a formula that describes the set of resource facts that has to be obtained in order to satisfy the goal. A description of a goal for a taxi company is, for example, a description of a passenger at a certain location at a certain time. To attain 17

18


such a goal, actions can be combined into plans. Plans specify the dependencies between actions, but they do not necessarily specify a linearly ordered set of actions. This means that concurrency can be represented explicitly in a plan, and one plan may represent many possible execution sequences. Just like actions, plans can be considered as processes that consume (input) resources and produce (output) resources. One important operation on plans is plan reduction: sometimes it is possible to remove one or more actions from a plan if this still leaves enough resources to reach all goals. More precisely, an action can be removed if each resource fact produced by this specific action is either irrelevant for goal production, or another equivalent resource fact (either an input resource or a resource produced) is available to the agent. Using the ARF it is possible to specify a plan reduction algorithm that, given a plan, iteratively produces a usually smaller irreducible plan, i.e., a plan from which no (single) action can be removed without affecting its goal realizability. Such a plan reduction algorithm can be used by a single agent to develop more efficient and less costly plans. The central idea in this thesis is to use this plan reduction technique in a multi-agent context: if other planning agents are available, equivalent resources needed in order to remove an action from a plan may be requested and obtained from other agents. Since such exchanges of resources result in the merging of two or more plans, this process is called a plan merging process. It turns out that the problem of finding such resources that plan merging is optimal is intractable. However, by repeatedly reducing plans as described above, one can find locally optimal solutions to this problem (irreducible plans) in polynomial time. In our research we developed a polynomial, any-time algorithm for locally optimal plan merging. Moreover, by a carefully designed distributed protocol for plan merging, the privacy of the individual planners can be respected. This plan merging algorithm has been tested on a data set from a Dutch taxi company (taxi Zeevang from Purmerend). We assume that the merging of multiple taxi companies can be emulated by splitting the data of this single taxi company. Moreover, we make passengers share rides, creating more opportunities for cooperation. The results of these experiments illustrate the properties of plan merging, such as the computation time and the acquired improvement of the efficiency. For picking up an additional passenger, we have two constraints: the pick-up time should not differ too much from the time requested by the passenger, and the additional distance the taxi needs to drive should not be too large. It turns out that the more relaxed these constraints are, the more the distance driven by the taxis is reduced (varies from 5 to 25 per cent), but the more time passengers spend in a taxi (increases approximately with 5 to 22 per cent). Furthermore, the run time is quadratic with the number of actions, but it also slightly depends (about 10%) on the number of exchanges that are done. It takes less than a minute to merge the plans of all 35 taxis for one whole day.

Summary

19

We conclude that both the framework and the algorithm work quite well on realistic data and we believe that the proposed framework and merging algorithm are useful for further research on coordinated planning. Apart from some extensions of the framework and the algorithm to cover more diverse problems and domains, we distinguish two very important issues for future work. Firstly, we would like to do more realistic tests by retrieving more information on the data and by examining all assumptions, and, secondly, we would like to devise algorithms that integrate coordination in the planning process. If agents can communicate and adjust their plans while these are under construction, conflicts can be solved more elegantly, and agents that do not have enough resources themselves might still be able to construct a plan. We laid the basis for such an extension by the introduction of the Action Resource Framework and the algorithm to coordinate plans after they have been formed.

20


Samenvatting Het afstemmen van plannen in multi-agent systemen

Door extra aandacht te besteden aan het cordineren van hun plannen, kunnen organisaties hun activiteiten zonder conflicten uitvoeren en zijn ze in staat om hun resources (hun middelen) efficinter te gebruiken. Dit speelt bijvoorbeeld een belangrijke rol bij het cordineren van logistieke processen, zoals de routeplanning van taxibedrijven en bij het efficint toewijzen van vervoersopdrachten aan vrachtwagens bij goederenvervoersorganisaties. Maar ook buiten de transportsector valt er veel op de kosten te besparen door betere samenwerking. Denk bijvoorbeeld aan de cordinatie van verschillende legermachten bij een VN-vredesmissie of de verschillende afdelingen van een ziekenhuis. Het cordineren van activiteiten die gepland zijn door verschillende autonome organisaties is een zeer belangrijk aspect van inter-organisationele cordinatie. De meeste organisaties, echter, willen niet alle informatie vrijgeven met betrekking tot hun eigen plannen, omdat ze bang zijn om hun autonomie (zelfstandigheid) te verliezen. Daardoor kunnen, in het algemeen, inter-organisationele cordinatieproblemen niet centraal opgelost worden. We moeten daarom zoeken naar cordinatiemethoden die het mogelijk maken om individuele plannen op een gedistribueerde manier te cordineren, waarbij de privacy van de individuele plannen-makende agenten (bedrijven, mensen) gerespecteerd wordt. Dit onderzoek naar methoden om een verzameling van gerelateerde (n agent-) problemen op te lossen is het onderwerp van multi-agent planning. In dit proefschrift beschrijven we een op resources gebaseerd raamwerk om zulke multi-agent planningsproblemen te modeleren en op te lossen. In dit actie-resource raamwerk (ARF) worden resource-feiten als de centrale concepten genomen voor zowel de planning als de cordinatie van acties. Deze resourcefeiten worden gebruikt om een exacte beschrijving te geven van de primitieve middelen en objecten en hun eigenschappen in een planningsdomein. Bij een taxibedrijf zijn dit bijvoorbeeld de taxi’s, de chauffeurs en de passagiers. De acties in dit raamwerk zijn processen die zulke resourcefeiten consumeren en produceren. Dit kan dan bijvoorbeeld de verplaatsing van een taxi zijn of het laten in- of uitstappen van een passagier. In het algemeen bestaat een actie uit een preconditie om de voor de actie noodzakelijke (invoer) resources te specificeren, en een beschrijving 21

22


van de (uitvoer) resources die geproduceerd worden door de actie. Doelen worden gespecificeerd door een formule die de verzameling gewenste resourcefeiten en de gewenste eigenschappen beschrijft. Een beschrijving van een doel bij een taxibedrijf is bijvoorbeeld een beschrijving van de passagier op zijn of haar bestemming op een bepaalde tijd. Om een doel te bereiken kunnen acties gecombineerd worden tot plannen. Plannen specificeren de afhankelijkheden tussen acties, maar dit hoeft niet noodzakelijk een lineaire ordening van de acties te zijn. Dit betekent dat parallelle activiteiten in een plan expliciet gerepresenteerd kunnen worden, en dat n plan op meerdere mogelijke manieren (volgordes van acties) uitgevoerd kan worden. Net zoals acties, kunnen plannen beschouwd worden als (invoer) resource consumerende en (uitvoer) resource producerende processen. Een belangrijke operatie op plannen is planreductie: soms is het mogelijk om een of meerdere acties uit een plan te verwijderen als er nog steeds genoeg resources over zijn om alle doelen te bereiken. Precieser nog, een actie kan uit een plan weggelaten worden als elk resourcefeit dat geproduceerd wordt door deze specifieke actie ofwel irrelevant is voor het behalen van de doelen, ofwel dat er een ander, equivalent, resourcefeit beschikbaar is (een initieel beschikbare resource of een geproduceerde resource). Bijvoorbeeld, als er in het plan van een taxibedrijf een actie zit om een lege taxi naar het station te rijden, maar daar staat al een andere taxi (leeg) te wachten, dan kan deze actie uit het plan verwijderd worden. Met het ARF is het mogelijk om een planreductie-algoritme te specificeren dat, gegeven een plan, in een aantal stappen een kleiner plan produceert dat niet meer gereduceerd kan worden. Een agent kan zo’n planreductie-algoritme gebruiken om effcintere en goedkopere plannen te ontwikkelen. Het centrale idee in dit proefschrift is om deze plan-reductietechiek in een multiagent omgeving te gebruiken: als andere planningsagenten beschikbaar zijn, kunnen de genoemde equivalente resources die nodig zijn om een actie uit een plan te kunnen verwijderen, aangevraagd en verkregen worden bij andere agenten. Omdat zo’n uitwisseling van resources resulteert in het combineren van hun plannen, wordt dit process “plan merging” genoemd. Het blijkt dat het probleem om de juiste verzameling resources te vinden om uit te wisselen, zodat de verkregen verzameling plannen optimaal is (plan-merging-probleem), ondoenlijk is. Maar door herhaald het planreductieproces zoals boven beschreven toe te passen, kunnen lokaal-optimale oplossingen voor dit probleem (niet-reduceerbare plannen) redelijk snel (in polynomiale tijd) gevonden worden. In dit onderzoek is een polynomiaal, any-time algoritme ontwikkeld voor het lokaal optimaal oplossen van het planmerging-probleem. Bovendien, door een gedistribueerd protocol voor plan-merging, kan aangetoond worden dat de privacy van de individuele planners gerespecteerd blijft. Dit plan-merging-algoritme is getest met behulp van gegevens over de planning van een Nederlands taxibedrijf (taxi Zeevang uit Purmerend). We nemen aan dat het combine-

Samenvatting

23

ren van de plannen van verschillende bedrijven nagebootst kan worden door het opsplitsen van de gegevens van dit ene bedrijf. Bovendien nemen we vervolgens aan dat passagiers hun taxi’s mogen delen, waardoor er meer mogelijkheden tot samenwerking ontstaan. De resultaten van deze experimenten illustreren de verschillende eigenschappen van het plan-merging-algoritme, zoals de benodigde rekenkracht en de behaalde efficintieverbetering. Voor het ophalen en wegbrengen van een extra passagier gebruiken we twee beperkingen: de ophaaltijd moet niet te ver af wijken van de door de passagier gewenste tijd en de afstand die de taxi extra moet afleggen om deze passagier op te halen moet niet te groot zijn. Het blijkt dat, als deze beperkingen ruimer worden genomen, de reductie van de totale afstand die de taxi’s afleggen groter is (5 tot 25 procent), maar ook dat passagiers gemiddeld meer tijd in een taxi doorbrengen (dit neemt toe met 5 tot 22 procent). Verder is de benodigde rekentijd van het algoritme kwadratisch in het aantal acties, maar hangt ook voor een klein deel (ongeveer 10%) af van het aantal uitwisselingen. Het duurt in totaal minder dan een minuut om de plannen van een hele dag van 35 taxis te combineren. We concluderen dat zowel het raamwerk als het algoritme redelijk goed werken met realistische data en we zijn ervan overtuigd dat het voorgestelde ARF-raamwerk en het plan-merging-algoritme bruikbaar zijn voor verder onderzoek naar het cordineren van plannen. Naast een aantal uitbreidingen van het raamwerk en het algoritme om meer verschillende soorten problemen aan te kunnen, onderscheiden we twee zeer belangrijke uitbreidingen om verder aan te werken. Ten eerste willen we graag meer realistische tests doen door meer informatie te vragen met betrekking tot de verkregen data set en door alle gedane aannames nogmaals onder de loep te nemen. Ten tweede willen we graag algoritmen ontwerpen die het cordinatieproces integreren met het planningsproces. Als agenten kunnen communiceren en hun plannen aanpassen terwijl deze nog gemaakt worden, kunnen conflicten eleganter opgelost worden. Bovendien zijn agenten die zelf niet genoeg resources hebben, dan toch in staat om een plan te maken. De basis voor zo’n uitbreiding is nu gelegd door de introductie van het actie-resource raamwerk en het plan-mergingalgoritme om plannen te cordineren nadat ze zijn gemaakt.

24


Curriculum Vitae Mathijs de Weerdt was born in Alkmaar, the Netherlands on May 15th 1976. He completed his secondary education at the Petrus Canisius College in Alkmaar in 1994. After some difficult time choosing the right subject, he decided to take a combined degree in computer science and mathematics at the Utrecht University. Mathijs completed the first year of both programmes in 1995. After this year, he decided to concentrate on computer science, because designing algorithms is more fun than producing proofs. During his study he enjoyed assisted many other students, both as a student-assistant, and in the last two years as a scientific programmer for the newly started robotics laboratory. In 1998 he completed his Master’s thesis about dealing with uncertainty using a modal logic at the Intelligent Systems Group in Utrecht. Upon completion of his Master’s degree (cum laude), Mathijs moved to Delft to do a PhD on multi-agent systems and inter-organizational coordination at the Delft University of Technology. He worked on the Collective Agent-Based Systems project for the last five years. Since September 2003 he works two days a week at the research company Almende in Rotterdam. The rest of the week he continues his work on multi-agent planning at the Delft University of Technology.

25

TRAIL Thesis Series A series of The Netherlands TRAIL Research School for theses on transport, infrastructure and logistics. Nat, C.G.J.M., van der, A Knowledge-based Concept Exploration Model for Submarine Design, T99/1, March 1999, TRAIL Thesis Series, Delft University Press, The Netherlands Westrenen, F.C., van, The Maritime Pilot at Work: Evaluation and Use of a Time-toboundary Model of Mental Workload in Human-machine Systems, T99/2, May 1999, TRAIL Thesis Series, Eburon, The Netherlands Veenstra, A.W., Quantitative Analysis of Shipping Markets, T99/3, April 1999, TRAIL Thesis Series, Delft University Press, The Netherlands Minderhoud, M.M., Supported Driving: Impacts on Motorway Traffic Flow, T99/4, July 1999, TRAIL Thesis Series, Delft University Press, The Netherlands Hoogendoorn, S.P., Multiclass Continuum Modelling of Multilane Traffic Flow, T99/5, September 1999, TRAIL Thesis Series, Delft University Press, The Netherlands Hoedemaeker, M., Driving with Intelligent Vehicles: Driving Behaviour with Adaptive Cruise Control and the Acceptance by Individual Drivers, T99/6, November 1999, TRAIL Thesis Series, Delft University Press, The Netherlands Marchau, V.A.W.J., Technology Assessment of Automated Vehicle Guidance - Prospects for Automated Driving Implementation, T2000/1, January 2000, TRAIL Thesis Series, Delft University Press, The Netherlands Subiono, On Classes of Min-max-plus Systems and their Applications, T2000/2, June 2000, TRAIL Thesis Series, Delft University Press, The Netherlands Meer, J.R., van, Operational Control of Internal Transport, T2000/5, September 2000, TRAIL Thesis Series, Delft University Press, The Netherlands Bliemer, M.C.J., Analytical Dynamic Traffic Assignment with Interacting User-Classes: Theoretical Advances and Applications using a Variational Inequality Approach, T2001/1, January 2001, TRAIL Thesis Series, Delft University Press, The Netherlands Muilerman, G.J., Time-based logistics: An analysis of the relevance, causes and impacts, T2001/2, April 2001, TRAIL Thesis Series, Delft University Press, The Netherlands Roodbergen, K.J., Layout and Routing Methods for Warehouses, T2001/3, May 2001, TRAIL Thesis Series, The Netherlands

Willems, J.K.C.A.S., Bundeling van infrastructuur, theoretische en praktische waarde van een ruimtelijk inrichtingsconcept, T2001/4, June 2001, TRAIL Thesis Series, Delft University Press, The Netherlands Binsbergen, A.J., van, J.G.S.N. Visser, Innovation Steps towards Efficient Goods Distribution Systems for Urban Areas, T2001/5, May 2001, TRAIL Thesis Series, Delft University Press, The Netherlands Rosmuller, N., Safety analysis of Transport Corridors, T2001/6, June 2001, TRAIL Thesis Series, Delft University Press, The Netherlands Schaafsma, A., Dynamisch Railverkeersmanagement, besturingsconcept voor railverkeer op basis van het Lagenmodel Verkeer en Vervoer, T2001/7, October 2001, TRAIL Thesis Series, Delft University Press, The Netherlands Bockstael-Blok, W., Chains and Networks in Multimodal Passenger Transport. Exploring a design approach, T2001/8, December 2001, TRAIL Thesis Series, Delft University Press, The Netherlands Wolters, M.J.J., The Business of Modularity and the Modularity of Business, T2002/1, February 2002, TRAIL Thesis Series, The Netherlands Vis, F.A., Planning and Control Concepts for Material Handling Systems, T2002/2, May 2002, TRAIL Thesis Series, The Netherlands Koppius, O.R., Information Architecture and Electronic Market Performance, T2002/3, May 2002, TRAIL Thesis Series, The Netherlands Veeneman, W.W., Mind the Gap; Bridging Theories and Practice for the Organisation of Metropolitan Public Transport, T2002/4, June 2002, TRAIL Thesis Series, Delft University Press, The Netherlands Van Nes, R., Design of multimodal transport networks, a hierarchical approach, T2002/5, September 2002, TRAIL Thesis Series, Delft University Press, The Netherlands Pol, P.M.J., A Renaissance of Stations, Railways and Cities, Economic Effects, Development Strategies and Organisational Issues of European High-Speed-Train Stations, T2002/6, October 2002, TRAIL Thesis Series, Delft University Press, The Netherlands Runhaar, H., Freight transport: at any price? Effects of transport costs on book and newspaper supply chains in the Netherlands, T2002/7, December 2002, TRAIL Thesis Series, Delft University Press, The Netherlands Spek, S.C., van der, Connectors. The Way beyond Transferring, T2003/1, February 2003, TRAIL Thesis Series, Delft University Press, The Netherlands Lindeijer, D.G., Controlling Automated Traffic Agents, T2003/2, February 2003, TRAIL Thesis Series, Eburon, The Netherlands

Riet, O.A.W.T., van de, Policy Analysis in Multi-Actor Policy Settings. Navigating Between Negotiated Nonsense and Useless Knowledge, T2003/3, March 2003, TRAIL Thesis Series, Eburon, The Netherlands Reeven, P.A., van, Competition in Scheduled Transport, T2003/4, April 2003, TRAIL Thesis Series, Eburon, The Netherlands Peeters, L.W.P., Cyclic Railway Timetable Optimization, T2003/5, June 2003, TRAIL Thesis Series, The Netherlands Soto Y Koelemeijer, G., On the behaviour of classes of min-max-plus systems, T2003/6, September 2003, TRAIL Thesis Series, The Netherlands Lindveld, Ch..D.R., Dynamic O-D matrix estimation: a behavioural approach, T2003/7, September 2003, TRAIL Thesis Series, Eburon, The Netherlands Weerdt, M.M., de, Plan Merging in Multi-Agent Systems, T2003/8, December 2003, TRAIL Thesis Series, The Netherlands

Plan Merging in Multi-Agent Systems. Mathijs de Weerdt

Recommend Documents