· · · Institutional Repository

Multi-agent planning and scheduling concerns finding a joint plan to achieve some set of common goals with several independent agents each aiming to find a plan or schedule for their part of the goals. To avoid conflicts in these individual plans or schedules decoupling is used. Such a decoupling entails adding local constraints for the agents such that they can schedule autonomously within those constraints, while they guarantee that a conflict-free global solution can be constructed from the individual agents’ schedules. In this paper we investigate finding an ‘optimal’ decoupling, that maximizes the sum of the agents’ preferences about their scheduling of tasks. We show using a Linear Programming (LP) approach that optimal decouplings can be found efficiently by exploiting the properties of a task scheduling instance.

In multi-agent routing, there is a set of mobile agents each with a start location and destination location on a shared infrastructure. An agent wants to reach its destination as quickly as possible, but conflicts with other agents must be avoided. We have previously developed a single-agent route planning algorithm that can find a shortest-time route that does not conflict with any previously made route plans. In this paper, we want to compare this route planning approach with non-planning approaches, in which intersection agents determine which agent may enter an intersection next, and where the agent will subsequently go (given its destination). When making these decisions, the intersection agents use only locally observed traffic information. Our experiments show that context aware routing produces more efficient results in case no incidents disrupt the execution. However, in the face of unexpected incidents, the performance of the intersection management policies proves very robust, while context-aware routing only produces good results when coupled with effective plan repair mechanisms.

In this demonstration, we show a software tool designed to interact with a scheduling algorithm. The algorithm solves the Resource-Constrained Multi-Project Scheduling Problem [3], which consists of projects with a release and due date, where the projects are composed of tasks, using one or more resources with a limited capacity. The tool serves a dual purpose: it is used to demonstrate the possibilities of using scheduling algorithms as a decision support system to end-users (i.e., schedulers), and it is used to gain insight into how scheduling algorithms solve different problem instances, and how different settings can influence the solutions to a particular instance.

Many different problems are called distributed or multiagent planning problems. Existing approaches each deal with only a subset of these problems. Which properties are essential in determining a solution method for multiagent planning problems? We argue that mainly the facts that communication is limited, agents have private goals, and the frequency of the dependencies between agents have a significant impact on the solution method.

We consider a multi-agent planning problem as a set of activities that has to be planned by several autonomous agents. In general, due to the possible dependencies between the agents’ activities or interactions during execution of those activities, allowing agents to plan individually may lead to a very inefficient or even infeasible solution to the multi-agent planning problem. This is exactly where plan coordination methods come into play. In this paper, we aim at the development of coordination by design techniques that (i) let each agent construct its plan completely independent of the others while (ii) guaranteeing that the joint combination of their plans always is coordinated. The contribution of this paper is twofold. Firstly, instead of focusing only on the feasibility of the resulting plans, we will investigate the additional costs incurred by the coordination by design method, that means, we propose to take into account the price of autonomy: the ratio of the costs of a solution obtained by coordinating selfish agents versus the costs of an optimal solution. Secondly, we will point out that in general there exist at least two ways to achieve coordination by design: one called concurrent decomposition and the other sequential decomposition. We will briefly discuss the applicability of these two methods, and then illustrate them with two specific coordination problems: coordinating tasks and coordinating resource usage.We also investigate some aspects of the price of autonomy of these two coordination methods.

In a multi-agent system, agents are carrying out certain tasks by executing plans. Consequently, the problem of finding a plan, given a certain goal, has been given a lot of attention in the literature. Instead of concentrating on this problem, the focus of this paper is on cooperation between agents which already have constructed plans for their goals. By cooperating, agents might reduce the number of actions they have to perform in order to fulfill their goals. The key idea is that in carrying out a plan an agent possibly produces side products that can be used as resources by other agents. As a result, an other agent can discard some of its planned actions. This process of exchanging products, called plan merging, results in distributed plans in which agents become dependent on each other, but are able to attain their goals more efficiently. In order to model this kind of cooperation, a new formalism is developed in which side products are modeled explicitly. The formalism is a resource logic based on the notions of resource, skill, goal, and service. Starting with some resources, an agent can perform a number of skills in order to produce other resources which suffice to achieve some given goals. Here, a skill is an elementary production process taking as inputs resources satisfying certain constraints. A service is a serial or parallel composition of skills acting as a program. An operational semantics is developed for these services as programs. Using this formalism, an algorithm for plan merging is developed, which is anytime and runs in polynomial time. Furthermore, a variant of this algorithm is proposed that handles the exchange of resources in a more flexible way. The ideas in the paper will be illustrated by an example from public transportation.

In an open Multi-Agent System, the goals of agents acting on behalf of their owners often conflict with each other. Therefore, a personal agent protecting the interest of a single user cannot always rely on them. Consequently, such a personal agent needs to be able to reason about trusting (information or services provided by) other agents. Existing algorithms that perform such reasoning mainly focus on the immediate utility of a trusting decision, but do not provide an explanation of their actions to the user. This may hinder the acceptance of agent-based technologies in sensitive applications where users need to rely on their personal agents. Against this background, we propose a new approach to trust based on argumentation that aims to expose the rationale behind such trusting decisions. Our solution features a separation of opponent modeling and decision making. It uses possibilistic logic to model behavior of opponents, and we propose an extension of the argumentation framework by Amgoud and Prade [1] to use the fuzzy rules within these models for well-supported decisions.

A common model for discrete event systems is a deterministic finite automaton (DFA). An advantage of this model is that it can be interpreted by domain experts. When observing a real-world system, however, there often is more information than just the sequence of discrete events: the time at which these events occur may be very important. In such a case, the DFA model is too limited. A variant of a DFA that includes the notion of time is called a timed automaton (TA). In this model, each symbol of a word occurs at a certain point in time. The execution of a TA depends not only on the type of symbol occurring, but also on the time that has elapsed since some previous symbol occurrence. We are interested in the problem of identifying such a time dependent system from a data sample. Full paper is published in: Proceedings of the Annual Belgian-Dutch Machine Learning Conference (Benelearn), 2007 See: http://resolver.tudelft.nl/uuid:a202b4cf-5153-4ad5-b41d-5d0332bf04f2

In crisis response, hierarchical organizations are being replaced by dynamic assemblies of autonomous agents that promise more agility. However, these autonomous agents might cause a decrease in effectiveness when individually constructed plans for moderately-coupled tasks are not jointly feasible. Existing coordination techniques can be applied in the pre-planning phase to guarantee feasible joint plans for partially-ordered tasks, which allows for human improvisation in the planning phase. Temporal relations in crisis response are often more complex than the simple precedence relations in current work. Therefore, we analyze whether temporal information can be dealt with by a conversion to partially-ordered tasks with only precedence constraints. Time windows and two temporal constraints (overlaps and during) can be rewritten in such a way that the task remains partially-ordered. When other temporal constraints (meets, starts, finishes, and equals) are used, tasks become tightly-coupled, requiring coordination in the execution phase as well. This work shows the applicability of pre-planning coordination as an enabling technology for the effective formation of agile organizations.

In our paper we focus on learning systems of which the execution is determined by a finite set of discrete events. The full version of this paper appeared in: Proceedings of the 15th Annual Machine Learning Conference of Belgium and the Netherlands (Benelearn 2006): http://resolver.tudelft.nl/uuid:faab7982-46bf-4d52-8a2a-324a88542584

We describe an efficient algorithm for learning deterministic real-time automata (DRTA) from positive data. This data can be obtained from observations of the process to be modeled. The DRTA model we learn from such data can be used reason and gain knowledge about realtime systems such as network protocols, business processes, reactive systems, etc.

This paper describes an efficient algorithm for learning a timed model from observations. The algorithm is based on the state merging method for learning a deterministic finite state automaton (DFA). This method and its problem have been the subject of many studies within the grammatical inference field, see e.g. (de la Higuera, 2005). Consequently, it enjoys a sound theoretical basis which can be used to prove properties of our algorithm. For example, while it has long been known that learning DFAs is NP-complete, it has been shown that DFAs can be learned in the limit from polynomial time and data (efficiently in the limit) using a state merging method.

A model for discrete event systems (DES) can be learned from observations. We propose a simple type of timed automaton to model DES where the timing of the events is important. Learning such an automaton is proven to be NP-complete by a reduction from the problem of learning deterministic finite state automata (DFA) without time. Based on this reduction, we show how the currently best learning algorithm for DFAs (state merging) can be adapted to deal with time information.

We describe an algorithm for learning simple timed automata, known as real-time automata. The transitions of real-time automata can have a temporal constraint on the time of occurrence of the current symbol relative to the previous symbol. The learning algorithm is similar to the redblue fringe state-merging algorithm for the problem of learning deterministic finite automata. In addition to state merges, our algorithm can perform state splits by making use of the time values in the input data. We tested our learning algorithm on randomly generated problems. The results are promising and show that learning a real-time automaton directly from timed data outperforms a method that uses sampling in order to deal with the timed data.

We are interested in identifying a model for discrete event systems from observations. A common way to model discrete event systems is by using deterministic finite state automata (DFA). When observing a system, however, there often is information in addition to the system events, namely, their times of occurrence. If this time information is important, a DFA is too limited. For example, it is impossible to distinguish between events that occur quickly after each other, and events that occur after each other with a significant delay between them. Consequently, we would like a model that can also deal with time information.