Search

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.

At airports, the turnaround process of aircraft is crucial for a timely and efficient handling of air traffic. During this process, a number of services need to be provided during the time the aircraft is at the gate: e.g., de-boarding, cleaning, catering, fuelling, and boarding. These services are provided by different service providers (agents), who have to coordinate their activities in order to respect the turnaround timeslot, the required service times and existing regulations. These temporal dependencies between services can be planned, but if disruptions occur re-planning is complex and often impossible. For this reason, in previous research a methodology and prototype have been devised to simplify the planning process by decoupling the overall plan into local plans for each agent. This paper builds on this research and introduces an important extension to the existing methodology and prototype: a new algorithm is introduced to take into account the minimal number of resources each service provider will need to accomplish its task.

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 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

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.

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.

We address the problem of coordinating autonomous agents that have to come up with a joint plan and schedule for a set of tasks. These tasks are interdependent and temporally constrained and are distributed over the agents. We start with investigating the scheduling part of the problem: How to achieve, given the constraints, a joint solution to the distributed scheduling problem where each of the agents is allowed to determine its own schedule for the set of tasks assigned to it. Here, the problem is to ensure that whatever individual schedule each agent comes up with, these schedules always can be combined into a global schedule satisfying all constraints. Next, we investigate a more complex problem where, before scheduling, the agents are allowed to make their own plan to achieve the tasks assigned to them. That is, they are allowed to choose autonomously some additional precedence constraints to their assigned tasks. We have to provide the necessary coordination mechanisms to ensure that no conflicts will arise between the resulting plans. The solution we provide is to reduce the temporal constraints of the individual tasks to a set of precedence constraints between tasks and virtual tasks and we solve the resulting coordination problem for tasks with precedence constraints. The solution thus obtained enables us to solve the plan coordination problem with temporal constraints.

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

The planning and scheduling of the deicing and anti-icing activities is an important and challenging part of airport departure planning. Deicing planning has to be done in a highly dynamic environment involving several autonomous and self-interested parties. Traditional centralized scheduling approaches do not acknowledge the autonomy of parties involved. We therefore propose an agent-based scheduling approach for solving the aircraft deicing problem where stakeholders are modelled as autonomous agents. Based on our view that multi-agent scheduling is scheduling combined with agent coordination, we propose a simple first come, first served heuristic combined with the concept of decommitment penalties. We demonstrate the feasibility of the approach through a series of experiments.

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.

We discuss a resource-based planning framework where agents are able to merge plans by exchanging resources. In this framework, plans are specified as structured objects composed of resource consuming and resource producing processes (actions). A plan itself can also be conceived as a process consuming input resources and producing output resources. A plan can be improved if we can remove actions from it while maintaining goal realizability.We describe a reduction property that specifies how one agent can improve its plan by using (free) resources from another agent in such a way that goal realizability is preserved. The plan-merging algorithm we use to specify plan merging in a multi-agent context is an iterative, distributed, any-time application of this reduction property. The performance of this algorithm has been evaluated using a planning data set obtained from a taxi company. The quality of the algorithm is measured by the decrease of the total distance driven by all taxis. By allowing passengers to share rides, we create a trade-off between the additional travel time of passengers and the total drive distance. Allowing passengers to be a few minutes later at their destination and share rides, a significant improvement of the plans can be obtained (from 5% up to 30% reduction of the taxi driving distance).

Opportunities arise in planning when changes in the environment make new propositions available to the planner. Replanning methods often focus only on the negative effects that changes in the environment have and therefore do not apply well. This paper introduces a method that is specifically focused on the opportunity problem. This method is based on the potential graph structure. This potential graph is basically an annotated version of the planning graph as used in many contemporary planners. We show how this potential graph can be used to discover the positive impact of opportunities. This information can then be used to improve upon the plan by exploiting such opportunities. The benefit of this method over standard planning techniques is two-fold: firstly, it can be used in an any-time algorithm. That is, when only little time is available, little improvements are quickly found. With more time available, greater improvements may be found. Secondly, this technique helps us focus on those parts of the plan that might be improved. Other parts are not changed, which greatly adds to the efficiency of the method. The applicability of the method is demonstrated by some initial experiments.

Lit.opg.

ill

ill

Lit.opg.

Lit.opg.

In this paper we will use the framework to study cooperative heuristic multi-agent planning. During the construction of their plans, the agents use a heuristic function inspired by the FF planner (l3l). At any time in the process of planning the agents may exchange available resources, or they may request an agent to produce a missing resource. The latter feature is anabled by an advertising mechanism: Any agent communicates to the other agents which resources it can, in principle, produce using a plan scheme stored in its knowledge base. The planning algorithm presented in this paper is sound but not complete: It might fail to find a plan in cases a valid plan does exist.

The paper analyzes the use of a Multi Agent System for Model Based Diagnosis. In a large dynamical system, it is often infeasible or even impossible to maintain a model of the whole system. Instead, several incomplete models of the system have to be used to detect possible faults. These models may also be physically be distributed. A Multi Agent System of diagnostic agents may offer solutions for establishing a global diagnosis. If we use a separate agent for each incomplete model of the system, establishing a global diagnosis becomes a problem cooperation and negotiation between the diagnostic agents. This raises the question whether `a set of diagnostic agents, each having an incomplete model of the system, can (efficiently) determine the same global diagnosis as an ideal single diagnostic agent having the combined knowledge of the diagnostic agents?''

ƒ†Œˆœ

The promise of multi-agent systems is that multiple agents can solve problems more efficiently than single agents can. In this paper we propose a method to implement cooperation between agents in the planning phase, in order to achieve more cost-effective solutions than without cooperation. Two results are presented: First of all, we introduce a flexible framework to describe cooperation in a planning process. This framework allows us to specify the basic tasks that have to be performed in order to satisfy a set of goals, and to specify constraints to model deadlines, capacity constraints, speed limits, conficting situations, et cetera. Furthermore, we present a polynomial fusion algorithm to implement cooperation between multiple agents.

The promise of multi-agent systems is that multiple agents can solve problems more efficiently than single agents can. In this paper we propose a method to implement cooperation between agents in the planning phase, in order to achive more cost-effective solutions than without cooperation. Two results are presented: First of all, we introduce a flexible framework to describe cooperation in a planning process. This framework allows us to specify the basic tasks that have to be performed in order to satisfy the basic tasks that have performed in order to satisfy a set of goals, and to specify constraint to model deadlines, capacity constraints, speed limits, conflicting situations, et cetera. Furthermore, we present a polynomial fusion algorithm to implement cooperation between multiple agents.

We introduce a computational framework, consisting of resources, skills, goals and services to represent the plans of individual agents and to develop models and algorithms for cooperation processes between a collection of agents.

We introduce an algorithm for cooperative planning in multi-agent systems. The algorithm enables the agents to combine (fuse) their plans in order to increase their joint profits. A computational resources and skills framework is developed for representing the planned activities of an agent under time constraints. Using this resource-skill framework, we present an efficient (polynomial time) algorithm that fuses the plans of a group of agents in such a way that their joint profits improve. The framework and the algorithm are illustrated using a simplified example from the freight transport domain.