MAS Publications
|
Multi- |
| Agent | |
| Systems |
MAS Publications |
|
In this paper, we set up a unifying perspective of the individual control layers of the architecture \I\ for autonomous interacting agents. \I\ is a pragmatic approach to designing complex dynamic agent societies, e.g.~for robotics \cite{MuellerPischel94a} and cooperative scheduling applications \cite{Fischer+94}. It is based on three general functions describing how the actions an agent commits to are derived from its perception and from its mental model: {\em belief revision and abstraction}, {\em situation recognition and goal activation}, and {\em planning and scheduling}.
It is argued that each \I\ control layer --- the behaviour-based layer, the local planning layer, and the cooperative planning layer --- can be described by a combination of different instantiations of these control functions. The basic structure of a control layer is defined. The individual functions and their implementation in the different layers are outlined.
We demonstrate various options for the design of interacting agents within this framework by means of an interacting robots application. The performance of different agent types in a multiagent environment is empirically evaluated by a series of experiments.
A multiagent approach to designing the transportation domain is presented. The \MARS\ system is described which models cooperative order scheduling within a society of shipping companies. We argue why Distributed Artificial Intelligence (DAI) offers suitable tools to deal with the hard problems in this domain. We present three important instances for DAI techniques that proved useful in the transportation application: cooperation among the agents, task decomposition and task allocation, and decentralised planning.
An extension of the contract net protocol for task decomposition and task allocation is presented; we show that it can be used to obtain good initial solutions for complex resource allocation problems. By introducing global information based upon auction protocols, this initial solution can be improved significantly. We demonstrate that the auction mechanism used for schedule optimisation can also be used for implementing dynamic replanning. Experimental results are provided evaluating the performance of different scheduling strategies.
An der DFKI GmbH wird seit 1991 Forschung im Bereich der Multiagentensysteme betrieben. Aspekte dieser Forschungsarbeit umfassen Fragestellungen, wie sich Probleme auf verschiedene Komponenten (Agenten) aufteilen lassen (Organisation), wie diese Agenten zusammen an der Lösung mitwirken können (Interaktion/Kommunikation) und mit welchen Fähigkeiten und Wissen einzelne Agenten ausgestattet sein müssen, um die Lösungsfindung vorantreiben zu können (interne Strukturen).
Der vorliegende Bericht untersucht vor allem den zweiten Punkt näher: wie lassen sich Kooperationsstrukturen zwischen Agenten modellieren und welche Vorteile bietet die Verteiltheit gegenüber konventionellen Architekturen. Als Anwendung wurde die Domäne der \emph{Fleet-Scheduling-Probleme} gewählt. Das \emph{Vehicle-Routing-Problem (VRP)} als Standardvertreter einer fast unüberschaubaren Klasse von Fleet-Scheduling-Problemen ist einfach zu formulieren, jedoch schwierig zu lösen. Gegeben ist eine Liste von Kunden mit festen Forderungen, die von einer Fahrzeugflotte mit Kapazitätsbeschränkungen in möglichst optimaler Reihenfolge zu bedienen sind. An der Lösung des Problems sind eine Reihe von unterschiedlichen Sparten interessiert: Operations Research, Mathematik, Informatik und nicht zuletzt unter dem Gesichtspunkt der Wirtschaftlichkeit der 'Verursacher' selbst: die Logistik. Die Aufarbeitung der in der Literatur bekannten Verfahrensweisen zur Lösung von Fleet-Scheduling-Problemen war ein weiterer Schwerpunkt der Arbeit.
Die Reaktionsfähigkeit auf eine sich ständig ändernde Umwelt ist eine Anforderung, für die in dieser Form bisher in der Literatur kaum Lösungen zu finden sind. Die Modellierung als Multiagentensystem, in dem autonom agierende und reagierende Agenten (Fuhrunternehmen, Fahrzeuge) durch Kooperation (Verteilen und Austauschen von Aufträgen) versuchen, ein gemeinsames Ziel (möglichst optimale Lösung des Problems) zu verwirklichen, eröffnet hier neue Perspektiven.
Temporal reasoning within distributed Artificial Intelligence Systems is faced with the problem of concurrent streams of action. Well known, logic-based systems using the Situation Calculus solve the frame problem in a purely linear manner. Recent research, however, has revealed that the Event Calculus under the abduction principle is capable of nonlinear planning. In this report, we present a planning service module which incorporates this approach into a constraint logic framework and even allows a notion of strong nonlinearity. The work includes the axiomatisation of appropriate versions of the Event Calculus, the development of a suitably sound and complete proof procedure that supports abduction and the implementation of both of these layers on the constraint platform Oz. We demonstrate prototypically how this module, EVE, can be integrated into an existing multi-agent architecture and evaluate the behaviour of such agents within an application domain, the loading dock scenario.
![[DFKI]](http://www.dfki.de/icon/navigation/dfkib.gif){kind=icon}
![[lab]](http://www.dfki.de/icon/navigation/lab.gif){kind=icon}
![[up]](http://www.dfki.de/icon/navigation/nur_up.gif){kind=icon}
![[search]](http://www.dfki.de/icon/navigation/find.gif){kind=icon}
![[server info]](http://www.dfki.de/icon/navigation/server_info.gif){kind=icon}