A DAI approach to modeling the transportation domain

Abstract

A central problem in the study of autonomous cooperating systems is that of how to establish mechanisms for controlling the interactions between different parts (which are called agents) of the system. One way to integrate such mechanisms into a multi-agent system is to exploit the technique of cooperation or negotiation protocols. In a protocol we distinguish to essential layers: the communication layer specifying the possible flow of messages between different agents, and the decision layer, which controls the selection of a message (speech-act) that the agent sends in a specific situation. In this report we first give a short introduction of our agent model InteRRap which provides the basis for the modeling of the different scenarios considered in the AKA-Mod project at the DFKI. The techniques we will discuss in the following are located in the plan based component and in the cooperation component of this model. The domain of application is the MARS scenario (Modeling a Multi-Agent Scenario for Shipping Companies) which implements a group of shipping companies whose goal it is to deliver a set of dynamically given orders, satisfying a set of given time and/or cost constraints. The complexity of the orders may exceed the capacities of a single company. Therefore, cooperation between companies is required in order to achieve the goal in a satisfactory way. This domain is of considerable interest for studies with economical background as well as for research projects. We give a short summary of results from economical studies that are concerned with the real-world situation in Germany in the transportation domain. They show the need for the development of new techniques from the field of computer science to tackle the problems therein. Then, an overview on related research is presented. Two approaches are discussed in more detail: the first one being based on OR-techniques and a second one being based on the concept of partial intelligent agents attempting to integrate techniques from OR and DAI. Both approaches are concerned with the situation in a single company. However, our purpose to handle the case of distributed shipping companies requires additional mechanisms, e.g. to cope with the problems of task allocation and task decomposition in multi-agent systems. Mechanisms for distributed task decomposition and task allocation processes in multi-agent systems belong to the core of our studies. Therefore, we will first discuss techniques for these problems in a general setting and then describe their implementations in the MARS system. In this description, particular emphasis is placed on the cooperation within a shipping company. Here, one company agent has to allocate a set of orders its truck agents. The truck agents support the company agents by giving cost estimations based on their route planning facility. Thus, this procedure provides the basis for the decisions of the company agents and is discussed in very detail. Finally, we present results from a series of benchmark tests. The test sets have also been run with OR-implementations and thus, give us the opportunity to compare our implementation against these approaches.