Abstract
In this paper, we present the MARS multi-agent system. MARS models a society of cooperating transportation companies. Emphasis is placed on how the functionality of the system as a whole — the solution of the global scheduling problem — emerges from local decision-making and problem-solving strategies, and on how variations of these strategies influence the performance of the system. We address three techniques of Distributed Artificial Intelligence (DAI) which are used for tackling the hard problems that occur in this domain, and which together give rise to the emergence of a solution to the global scheduling problem: (1) cooperation among the agents, (2) task decomposition and task allocation, and (3) decentralised planning. Finally, we briefly describe the implementation of the system and provide experimental results which show how different strategies for task decomposition and cooperation influence the behaviour of the system.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
L. Bodin, B. Golden, A. Assad, and M. Ball. Routing and scheduling of vehicles and crews. Computers and Operations Research, 10(2):63–211, 1983.
M. Buchheit, N. Kuhn, J. P. Müller, and M. Pischel. MARS: Modelling a Multiagent Scenario for Shipping Companies. In Proceedings of the European Simulation Symposium (ESS-92), Dresden, 1992. Society for Computer Simulation (SCS).
S. Bussmann and H. J. Müller. A Negotiation Framework for Cooperating Agents. In Proc. of the 2nd Workshop on Cooperating Knowledge Based Systems. Keele, GB, September 1992.
P. Bagchi and B. Nag. Dynamic Vehicle Scheduling: An Expert System Approach. Journal of Physical Distribution and Logistics Management, 21(2), 1991.
M. Desrochers, J. Desrosiers, and M. Solomon. A new optimisation algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 1992.
E. H. Durfee and V. R. Lesser. Negotiating task decomposition and allocation using partial global planning. In Distributed Artificial Intelligence, Volume II, pages 229–244, San Mateo, CA, 1989. Morgan Kaufmann Publishers, Inc.
W. Domschke. Logistik (Bd.2): Rundreisen und Touren. Oldenbourg-Verlag, München — Wien, 3rd edition, 1990.
R. Davis and R.G. Smith. Negotiation as a methaphor for distributed problem solving. Artificail Intelligence, 20:63–109, 1983.
K. Fischer and N. Kuhn. A DAI Approach to Modelling the Transportation Domain. Technical Report RR-93-25, DFKI, 1993.
K. Fischer, N. Kuhn, and J. P. Müller. Distributed, knowledge-based, reactive scheduling in the transportation domain. In Proc. of the Tenth IEEE Conference on Artificial Intelligence and Applications, San Antonio, Texas, March 1994.
K. Fischer and H. M. Windisch. MAGSY-Ein regelbasiertes Multi-Agentensystem. In H. J. Müller, editor, KI1/92, Themenheft Verteilte KI. FBO-Verlag, 1992.
M. R. Garey and D. S. Johnson. Computers and Intractability — A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
C. Hewitt. Open information systems semantics for distributed artificial intelligence. Artificial Intelligence, 47:79–106, 1991.
N. R. Jennings. Joint Intentions as a Model of Multi-Agent Cooperation. PhD thesis, Queen Mary and Westfield College, London, August 1992.
N. Kuhn, H. J. Müller, and J. P. Müller. Simulating cooperative transportation companies. In Proceedings of the European Simulation Multiconference (ESM-93), Lyon, France, June 1993. Society for Computer Simulation.
N. Kuhn, H. J. Müller, and J. P. Müller. Task decomposition in dynamic agent societies. In Proceedings of the International Symposium on Autonomous Decentralised Systems (ISADS-93), Tokyo, Japan, 1993. IEEE Computer Society Press.
S. E. Lander and V. R. Lesser. Understanding the role of negotiation in distributed search among heterogeneous agents. In Proc. of the 12th International Workshop on Distributed Artificial Intelligence, pages 249–262, Hidden Valley, Pennsylvania, May 1993.
H. Müller-Merbach. Operations Research. Verlag Franz Vahlen, München, 3rd edition, 1973.
J. P. Müller and M. Pischel. The Agent Architecture InteRRaP: Concept and Application. Technical Report RR-93-26, German Artificial Intelligence Research Center (DFKI), Saarbrücken, June 1993.
J. P. Müller and M. Pischel. Integrating agent interaction into a planner-reactor architecture. In Proc. of the 13th International Workshop on Distributed Artificial Intelligence, Seattle, WA, USA, July 1994.
J. P. Müller and M. Pischel. Modelling interacting agents in dynamic environments. In Proc. of the European Conference on Artificial Intelligence (ECAI94), pages 709–713. John Wiley and Sons, August 1994.
H. Van Dyke Parunak. Industrial applications of multi-agent systems. In Proc. of INFAUTOM-93, Toulouse, February 1993. Association Colloque SUP'AERO.
R. Rittmann. Die Macht der Trucks. Bild der Wissenschaft, 9:112–114, 1991.
L. Steels. Cooperation between distributed agents through self-organisation. In Y. Demazeau and J.-P. Müller, editors, Decentralised A.I., pages 175–196. North-Holland, 1990.
K. P. Sycara. Multiagent compromise via negotiation. In L. Gasser and M. N. Huhns, editors, Distributed Artificial Intelligence, Volume II, pages 119–137. Morgan Kaufmann, San Mateo, California, 1989.
H.-J. Zimmermann. Methoden und Modelle des Operations Research. Vieweg-Verlag, Braunschweig — Wiesbaden, 2nd edition, 1992.
G. Zlotkin and J. S. Rosenschein. Negotiation and task sharing among autonomous agents in cooperative domains. In Proc. of the Eleventh IJCAI, pages 912–917. Detroit, Michigan, August 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fischer, K., Kuhn, N., Müller, H.J., Müller, J.P., Pischel, M. (1995). Sophisticated and distributed: The transportation domain. In: Castelfranchi, C., Müller, JP. (eds) From Reaction to Cognition. MAAMAW 1993. Lecture Notes in Computer Science, vol 957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0027060
Download citation
DOI: https://doi.org/10.1007/BFb0027060
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60155-5
Online ISBN: 978-3-540-49532-1
eBook Packages: Springer Book Archive