Abstract: Future processing, storage and communication services will be highly pervasive: people, smart objects, machines and the surrounding space (all embedding devices such as with sensors, RFID tags etc.) will define a highly decentralized cyber environment of resources interconnected by dynamic networks of networks. As communications will extend to cover any combination of â冪eople, machines and thingsâ, future networks will be increasingly complex and heterogeneous, yet always endorsed with the challenging task of ensuring end-to-end QoS. This paper proposes the groundwork for an advanced cognitive networking paradigm exploitable in future wired and wireless infrastructures: a decentralized cognitive plane to allow for cross-layer, cross-node and cross-network domain self-management, self-control and self-optimization, while being compatible with legacy management and control systems.
Abstract: We consider planning problems where a number of non-cooperative agents have to work on a joint problem. Such problems consist in completing a set of interdependent, hierarchically ordered tasks. Each agent is assigned a subset of tasks to perform for which it has to construct a plan. Since the agents are non-cooperative, they insist on planning independently and do not want to revise their individual plans when the joint plan has to be assembled from the individual plans. We present a general formal framework to study some computational aspects of this non-cooperative coordination problem and we establish some complexity results to identify some of the factors that contribute to the complexity of this problem. Finally, we illustrate our approach with an application to coordination in multi-modal logistic planning.
Abstract: Measuring the performance of a decision support system implemented within a networked organization is neither a simple nor straightforward activity. Besides the traditional objectives that can be measured quite precisely, in a networked enterprise it is also of utmost importance that short and long-term customer and supplier relations are considered. These factors are, however, much harder to measure and to compare. We show how expert domain knowledge can be modeled with fuzzy logic, and used to find a balance between multiple quantitative system metrics and less tangible satisfaction measures. This approach is illustrated within freight logistics for the evaluation of different planning support systems.
Abstract: We present the research vision in an EU-FP7 project, SEAM4US (Sustainable Energy mAnageMent 4 Underground Systems). We first formulate the SEAM4US project problem as a constrained optimization problem and then present a modified Newtonâ冱 method as the solution for sustainable energy management. Preliminary simulation results within the model-in-the-loop framework are delivered.
Abstract: We study the planning of maintenance activities on public infrastructural networks â road networks, Internet, power grids, etc. â in contingent environments such that the negative impact on the network user is minimised. Traditional eï¬orts hereto are mainly of a regulatory nature, whereas we propose charging the service-providers (agents) proportional to the harm they cause, thus representing the road user implicitly. Additionally, we seek to exploit the additional opportunities of implicit coordination between agents that arise as a consequence of user cost charging.
In this paper we discuss several existing methods for eï¬ツient maintenance planning in contingent environments with interdependent agents and we propose a ï¬〉st attempt at a general dynamic mechanism that is to be reï¬］ed in future work. By experimental analysis we show the validity of our mechanism.
Abstract: Credo oers tools and techniques to model and analyze highly recon gurable distributed systems. In this paper, we present an integrated methodology to use the Credo tool suite. In this methodology, we advertise the use of top-down design, component-based modeling and compositional analysis to address the complexity of highly recon gurable distributed systems. As a running example, we model a peer-to-peer le-sharing system and show how and when to apply the dierent modeling and analysis techniques of Credo.
Abstract: In the recent past, modular robot assembly and metamorphosis has been evolved using gene regulatory networks. However, until now, no methodology exists to engineer such a regulatory network. Three existing representations will be employed to describe robot metamorphosis. A graph rewriting grammar describes state and connectivity transitions between robot organisms at the most abstract level. A communicating ï¬］ite state machine introduces messages at an intermediate level. A regulatory network presents the process of metamorphosis at its least abstract level. In short, we present a design methodology for metamorphosis for which, as yet, only evolutionary methods did exist.
Abstract: Protecting the environment by saving energy and thus reducing carbon dioxide emissions is one of todayâ冱 hottest
and most challenging topics and is of a rapidly growing importance in the computing domain. The motivation and reasons for optimizing energy consumption from ecological and business perspectives are clear. However, the technical realization still is way behind expectations. One reason might be that technical problems range from pure hardware issues (e.g., low-power devices, energy harvesting, etc.) to software to cooling issues. This paper discusses recent findings and first ideas regarding policies and strategies for energy optimization and the development of a generic plug-in for managing data centers, accompanied by the introduction of the concept of â廨reen Service Level Agreements (GSLA)â. We discuss the general structure (generic architecture) of the plug-in and sketch some of the embedded policies. It is also to be noted that all results are part of the recently started FIT4Green project, funded by the European Union.
Abstract: This paper is an extended version of the Credo Methodology. Credo offers tools and techniques to model and analyze highly reconfigurable distributed systems. In a previous version we presented an integrated methodology to use the Credo tool suite. Following a compositional, componentâ澱ased approach to model and analyze distributed systems, we presented a separation of the system into components and the network. A highâ斗evel, abstract representation of the dataflow level on the network was given in terms of behavioral interface automata and a detailed model of the components in terms of Creol models. Here we extend the methodology with a detailed model of the network connecting these components. The Vereofy tool set is used to model and analyze the dataflow of the network in detail. The behavioral automata connect the detailed model of the network and the detailed model of the components. We apply the extended methodology to our running example, a peer-to-peer file-sharing system.
Abstract: Thread pools are often used as a pattern to increase the throughput and responsiveness of software systems. Implementations of thread pools may differ considerably from each other, which urges the need to analyze these differences in a formal manner. We use an object-oriented paradigm to model different thread pools in the context of the ASK system, an industrial communication platform. We use behavioral interfaces, high-level behavioral specifications for the objects, as a starting-point for analysis. Based on these behavioral interfaces, functional aspects are modeled in Creol, a high-level modeling language for concurrent objects. We use Uppaal to create real-time models and to perform schedulability analysis with respect to the behavioral interfaces. We finally check conformance between the real-time and Creol models using test-cases generated from the behavioral interfaces.
Abstract: . This paper presents an ontology and a filtering algorithm used in an agent-based system to support communication in case of incidents in the mobile human surveillance domain. In that domain reaching the right people as soon as possible is of the essence when incidents occur. The main goal of our efforts is to significantly reduce the response time in case of incidents by proposing and setting up the communication to the right people. Experimental results show that this can reduce the response time by more than 50%, e.g., from 40 to 20 minutes. To continuously improve the accuracy of the proposed communications, the agent-based system uses feedback mechanisms. An implementation of this system, ASK-ASSIST, has been deployed at a mobile human surveillance company.
Abstract: This paper addresses decentralized multi-project scheduling under uncertainty. The problem instance we study is the scheduling of airport ground handling services, where aircraft turnarounds can be seen as multiple projects, ground handling services as activities, and service providers as resources. In this environment aircraft requiring ground handling services and the corresponding service providers are self-interested autonomous parties. Moreover, the environment is well-known for its large number of disturbances.
We employ a heterogeneous multiagent scheduling framework with two types of autonomous agents representing aircraft and ground service providers respectively. We use online scheduling to cope with uncertainty in the release time of project: the uncertainty in aircraft arrival time at an airport. To balance the interests of the two types of agents in this heterogeneous multiagent system, we propose a marketbased mechanism to assign time slots to aircraft turnaround activities. We study the use of this mechanism in a cooperative and a non-cooperative setting.
In a dynamic environment such as airport ground handling, the execution of project schedules may be invalidated by various disruptions. As a result project agents may incur high costs if they have to reschedule some of their activities. The insertion of slack time between activities is a well known solution. The delay cost incurred by inserting slack should balance the expected costs of rescheduling some activities. Since in a dynamic multiagent system it is hard to analytically calculate optimal slack time between activities, we propose that agents determine these slack time using a co-evolutionary learning approach.
Experiment show that our decentralized scheduling approach scores on average as high as well-established ORbased heuristics, and that slack times to keep a schedule stable can be learned.
Abstract: This paper introduces the Windmill method for constructing situation sensitive communication support systems for organizations consisting of a network of autonomous professionals involved in standard duties encountering occasional incidents of a time-critical nature for which they have to call for help. The Windmill method is based on statistical data filtering techniques for ranking available resources to handle incident according to their availability, location, skills and experience. It is especially useful for domains in which the human workforce changes over time and incidents are relatively sparse with respect to location and frequency of occurrence.
Abstract: In context-aware route planning, a set of agents has to plan routes on a common infrastructure and each agent has to plan a conï¬Ｊct-free route from a source to a destination without invalidating plans made by other agents. The existence of such a conï¬Ｊct-free set of plans can be ensured if each agent is allowed to reserve time slots on the infrastructure resources it intends to use.
In the multi-stage variant of the context-aware routing problem, each agent has a sequence of destination locations
it must visit. A naive approach to solve the multi-stage variant is to make context-aware route plans between every two subsequent locations in the sequence, and then to concatenate these plans together. It can easily be shown,
however, that this concatenation approach cannot guarantee that a multi-stage plan (if it exists) can always be found, and even if it is found, then it need not be optimal. Therefore, we present a new polynomial-time algorithm for the multi-stage routing problem that always returns the optimal (shortest-time) route for a single agent, given a set of reservations made by previous agents, thus providing a set of Pareto-optimal route plans.
Obviously, the need for such a dedicated multi-stage routing algorithm depends on the frequency with which the concatenation approach fails to ï¬］d a plan, or ï¬］ds a rather ineï¬ツient one. Our experiments show that, given a set of reservations from 200 agents, the concatenation approach fails to ï¬］d a solution in more than 50% of the cases, for random visiting sequences of six locations or more. However, if the concatenation approach does ï¬］d a solution, its plan quality is often close to that of an optimal solution.
Abstract: Business activity monitoring (BAM) is software that supports the monitoring of those activities that are implemented in computer systems. It is intended to provide real-time summaries of business activities to operations managers and upper management, and to detect and warn of impending problems. This technology is a competitive differentiator for companies. Since the emphasis is on analysis, analysis tools are of the utmost importance [6]. The need for more complex forms of analysis on the huge relational data sets companies collect is growing along with the technology to support the analytical process. These more complex forms of analysis can be eloquently represented in constraints, and extended forms of first order logic. However, in current practice, solutions to the problem are implemented in ad-hoc and difficult to maintain procedural code that accesses the data through embedded SQL programming. Lohfert et al., [5] propose to use more elegant solutions that involve the use of declarative languages that integrate constraint modeling with database access in transparent ways.
Abstract: While intermodal transport has the potential to introduce eï¬ツiency to the transport network, this transport environment also suï¬ers from a lot of uncertainty at the interface of modes. For example, trucks moving containers to and from a port terminal are often uncertain as to when exactly their container will be released from the ship, from the stack, or from customs. This leads to much diï¬ツulty and ineï¬ツiency in planning a proï¬》able routing for multiple containers in one day.
In this paper, we examine agent-based solutions as a mechanism to handle job arrival uncertainty in the context of a drayage case at the Port of Rotterdam. We compare our agent-based solution approach to a well known on-line optimization approach and study the comparative performance of both systems across four scenarios of varying job arrival uncertainty. We conclude that when less than 50% of all jobs are known at the start of the day then an agent-based approach performs competitively with an on-line optimization approach.
Abstract: This paper presents an ontology and a filtering algorithm used in an agent-based system to support communication in case of incidents in the mobile human surveillance domain. In that domain reaching the right people as soon as possible is of the essence when incidents occur. The main goal of our efforts is to significantly reduce the response time in case of incidents by proposing and setting up the communication to the right people. Experimental results show that this can reduce the response time by more than 50%, e.g., from 40 to 20 minutes. To continuously improve the accuracy of the proposed communications, the agent-based system uses feedback mechanisms. An implementation of this system, ASK-ASSIST, has been deployed at a mobile human surveillance company.
Abstract: This paper presents a unified approach to test case generation and conformance test execution in a distributed setting. A model in the object-oriented, concurrent modeling language Creol is used both for generating test inputs and as a test oracle. For test case generation, we extend Dynamic Symbolic Execution (also called Concolic Execution) to work with multi-threaded models and use this to generate test inputs that maximize model coverage. For test case execution, we establish a conformance relation based on trace inclusion by recording traces of events in the system under test and replaying them in the model. User input is handled by generating a test driver that supplies the needed stimuli to the model. An industrial case study of the Credo project serves to demonstrate the approach.
Abstract: The distributed project scheduling problem is a distributed resource allocation problem extended with temporal constraints. Herein a project consists of a series of activities, the scarce resources are assigned to those activities at certain time windows such that all the activities are performed and certain objectives are optimized. In the past, methods from Operations Research (OR) and Artiſtial Intelligence (AI) were proposed to tackle this problem in a centralized manner. However, such centralized methods appear to
be for many real-world applications impractical and infeasible due to the distribution of information, changes in willingness to cooperate and the decision autonomy of individual actors. Furthermore, long term schedules are likely to be invalidated by the dynamic changes in the environment. In this paper, we investigate this more dynamic problem in the context of Airport Ground Handling (AGH), where airlines and ground handlers are working together to deliver ground services during aircraft turnaround times. Although parties involved in AGH process cooperate, they may have their own selï¬《h ambitions. For instance, in the scheduling process, airlines and ground service providers do not share a uni﬑d objective. In this paper, a multiagent online heuristic approach is proposed. We employ in this approach a market mechanism that balances the interests of airlines and ground service providers for scheduling the AGH services. The experimental results show that this multiagent approach provides a schedule that is of comparable quality as a centralized heuristic approach, and that by letting self-interested agents behave cooperatively, the overall schedule is signiſtantly improved.
Abstract: Business Activity Monitoring (BAM) and Business Intelligence (BI) solutions are both intended to provide insight into the activities and performance of the enterprise. Deployment of such systems requires extensive tailoring to the enterprise, best left to experts. The dynamics of the enterprise demands a solution to the maintenance of BAM/BI solutions. This paper presents an Ontology-based BAM-Agent, called OBAMA that supports the maintenance of the system in light of changing business processes. Furthermore, for the formulation of aspects and properties to be monitored, it combines the expressive power of SQL, and TTL (a temporal trace language of first order logic). OBAMA helps in the preparation of regular assessment reports on the enterprise, taking into account key performance indicators as set by its operation manager. The paper describes the architecture, the combination of SQL, and TTL techniques for monitoring, and provides description of its kernel processes. OBAMAâ冱 performance in a surveillance company is presented.
Abstract: ICT service providers face increasing demands on dynamic, flexible and scalable composition of their evolving software services. These demands complicate the validation and verification of such compositions as--a--whole. Within the European Credo research project, we develop techniques for the modeling, validation and verification of compositional distributed services. Our approach is based on two principles: a clear formal separation between the service components and the logical network that binds them together, and support for light--weight, preferably automated verification and model checking for all modeling techniques. In this paper, we apply the Credo techniques to ASK, a context--aware response system with intelligent matching functionality for connecting people to other people via existing communication technologies.
Abstract: Modeling concurrent systems and testing multi-threaded implementations against the model is an exciting field of study. This paper presents work done on constructing and executing test cases for an industrialsize multi-threaded application against a model written in the Creol modeling language. Models written in Creol, an object-oriented, concurrent modeling language, can be structurally similar to the finished implementation; we show how to keep this desirable property when re-using Creol models as test oracles. Also, a conformance relation between model and system under test that needs less controllability than other relations that are based on automata is presented.
Abstract: ASK is an industrial software system for connecting people to each other. The system uses intelligent matching functionality and learning mechanisms in order to nd eective connections between requesters and responders in a community. Currently, Almende investigates ways to connect multiple distributed con gurations of ASK to each other
and to dierent existing systems. Thereby, we face the issue of how to derive knowledge about connections between people in such distributed heterogeneous settings. In this paper, we introduce ASK, indicate its future development and discuss the imposed challenges.
Abstract: Failures in plan execution can be attributed to errors in the execution of plan steps or violations of the plan structure. While in previous work we have concentrated on the first type of failures, in this paper we introduce the idea of diagnosing violations in the plan structure. The structure of a plan prescribes which actions have to be performed and which precedence constraints between them have to be respected. Especially in multiagent environments violations of plan structure might easily occur as the consequence of synchronization errors. Using a formal framework for plan diagnosis, we show how Model-Based Diagnosis can applied to identify these violations of plan structure specifications and we analyze the computational complexity of the associated diagnostic problems.
Abstract: In real-life multi-agent planning problems, long-term plans will often be invalidated by changes in the environment during or after the planning process. When this happens, short-term operational planning and scheduling methods have to be applied in order to deal with these changed situations. In addition to the dynamic environment, in such planning systems we also have to be aware of sometimes conï¬Ｊcting interests of diï¬erent parties, which render a centralized approach undesirable. In this paper we investigate two agent-based scheduling architectures where stakeholders are modelled as autonomous agents. We discuss this approach in the context of an interesting airport planning problem: the planning and scheduling of deicing and anti-icing activities. To coordinate the competition between agents over scarce resources, we have developed two mechanisms: one mechanism based on decommitment penalties, and one based on a more traditional (Vickrey) auction. Experiments show that the auction-based mechanism best respects the preferences of the individual agents, whereas the decommitment mechanism ensures a fairer distribution of delay over the agents.
Abstract: Given unexpected incidents on routes of guards that check security objects, like banks, one of the most challenging problems is still how to support improvisation by security personnel in taking decisions to prevent or resolve such incidents. Another as important associated problem is how a security company can naturally take advantage of its existing and novel knowledge about its organizational and ICT infrastructures, and the introduction of a decision support system to help leverage of improvisation by humans. To tackle all this, on the one hand we present a dynamic coalition formation framework that allows the (re)configurations of agents that are associated with joint tasks in situational contexts to be evaluated by appropriate value functions. On the other hand, we present a dynamic scale-space paradigm that allows a security company to distill ranked lists of robust context-dependent reconfigurations at critical scales. We highlight the merits of ASK-ASSIST as a solution to the problem of supporting human improvisation.
Abstract: Results from disaster research suggest that methods for coordination between individual emergency responders and organizations should recognize the independence and autonomy of these actors. These actor features are key factors in effective adaptation and improvisation of response to emergency situations which are inherently uncertain. Autonomy and adaptability are also well-known aspects of a multi-agent system (MAS). In this paper we present two MAS strategies that can effectively handle aircraft deicing incidents. These MAS strategies help improve to prevent and reduce e.g. airplane delays at deicing stations due to changing weather conditions or incidents at the station, where aircraft agents adopting pre-made plans that would act on behalf of aircraft pilots or companies, would only create havoc. Herein each agent using its own decision mechanism deliberates about the uncertainty in the problem domain and the preferences (or priorities) of the agents. Furthermore, taking both these issues into account each proposed MAS strategy outperforms a naive first-come, first-served coordination strategy. The simulation results help pilots and companies taking decisions with respect to the scheduling of the aircraft for deicing when unexpected incidents occur: they provide insights in the impacts and means for robust selection of incident-specific strategies on e.g. deicing station delays of (individual) aircraft.
Abstract: Resource scheduling problems with incomplete information and environment changes have been studied for decades. The vast majority of the research eï¬orts in the scheduling problems under uncertainty assume a central authority with a global objective of maximizing the resource usage. In real-life scheduling problems, in addition to the dynamic environment, sometimes conï¬Ｊcting interests of diï¬erent parties renders a centralized approach undesirable. Applying multi-agent approaches in resource scheduling overcomes the restrictions associated with traditional static centralized scheduling. This paper studies a multi-agent scheduling system in the context of an interesting airport planning problem: the planning and scheduling of deicing and anti-icing activities. In this application domain, self-interested aircraft agents have an incentive to reserve a deicing resource as early as possible, leading to sub-optimal
schedules. To counter this eï¬ect, we propose the use of decommitment penalties, forcing agents to reserve the deicing resources at a later time point, which results in a better overall schedule. This paper investigates the eï¬ects of agents learning an â椀ptimalâ strategy in this context. To learn an â椀ptimalâ strategy, we apply genetic algorithms to train a neural
network, the agent use to decide when to reserve the deicing resource. Experiments show that the neural-evolution algorithm outperforms the derived strategy based on simpli﬑d cost estimation in the decommitment penalties mechanism, which in turn signiſtantly improve the eï¬ツiency and fairness compared with naive First Come, First Served approach.
Abstract: In context-aware route planning, agents have to plan their route on a common infrastructure in such a way that plans made by other agents are not invalidated, and no conï¬Ｊcts
are introduced. Previous research on context-aware routing, mostly in the domain of automated guided vehicle (AGV) routing, has reported on an O(n4v2) (n the number of vehicles, v the number of infrastructure resources) algorithm. In this paper we present an improved algorithm with a complexity of only O(nv log(nv) + nv 2 ).
Our free path routing approach is based on a search through the graph of free time windows on the resources, rather than a search through the infrastructure itself. Our algorithm can
be used to ï¬］d a set of conï¬Ｊct-free routes for a number of agents by ï¬］ding the route for a single agent at a time. As a consequence, the order in which agents plan their route will determine the quality not only of the individual agent plans, but also of the global plan. Our experimental results conï¬〉m that for an individual agent, its position in the planning queue can make a signiſtant difference; for the total throughput of the airport, however, the order in which the agents make their plans is not highly signiſtant. Also the experiments compare our free path routing
approach to ï¬』ed path scheduling approaches. We show that for a reasonable amount of extra computation time (required to investigate alternative routes), a free path routing approach ï¬］ds more efſtient plans, because it manages to avoid bottlenecks in the infrastructure.
Abstract: We present a multi-scale physics-based framework to distill robust and sustainable distributed management schemes for self-organization of complex networks, which constitute of collaborating distributed ICT systems, organizations and multi-agent systems. Our framework is based on a dynamic scale-space paradigm, which assumes that appropriate network management structures manifest themselves as intrinsic network connections, metrics and evolutions at critical scales. This self-organization of complex networks is grounded by the continuous interaction and co-evolution of the network entities being aware to a certain extent of their own and others resource capabilities and constraints.
Abstract: We develop and evaluate ASK-ASSIST, a decision support system that enables automatically setting up communication networks and sharing knowledge amongst security personnel, in particular when they are confronted with a series of unexpected incidents while on patrol. Currently, team leaders of mobile security guards are still forced to assess the consequences of a series of incidents and to take decisions in a heuristic way. On the basis of incomplete and uncertain information they have to determine the security situation, who to bring in contact with whom, and which personnel or which information systems should be lined up in order to resolve the incidents as a whole. ASK-ASSIST, however, automates robust dynamic formation and coordination of the right coalitions of security personnel, such that they support human improvisation in determining the nature of incidents and taking decisions by the coalitions. These coalitions comprise security personnel, communication security infrastructures and knowledge management security infrastructures. ASK-ASSIST is based on a framework for self-organization that generates ranked lists of incident-specific critical (re)configurations of coalitions in which joint tasks are assigned to agents associated with roles, like guards or team leaders. Our main contributions are the grounding and evaluation of the framework underlying ASK-ASSIST. We instantiate, validate and test the system on the basis of real data. These data concern organizational structures reflected in the coalitions and implicit or explicit feedback provided by personnel from a private security company. The provided feedback relates to the daily operational mobile security surveillance processes including those that involve functionalities of ASK-ASSIST.
Abstract: This paper presents a matchmaking framework for a new matchmaking component in the ASK communication platform (http://www.ask-cs.nl/). The framework allows a variety of
matchmaking techniques to be applied in a single automated matchmaking system. A variety of settings are generalized in a way that combines coalition formation with typical matching settings such as perfect/maximal matching and bi/tri-partite matching. Our framework turns out to be useful to categorize existing work on coalition formation and matching, but at the same time allows us to identify new domains to be studied.
Abstract: 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 ï¬〉st come, ï¬〉st served heuristic combined with the concept of decommitment penalties. We demonstrate the feasibility of the approach through a series of experiments.
Abstract: In multi-agent planning problems agents are requested to jointly solve a complex task consisting of a set of interrelated tasks. Since none of the agents is capable to solve the whole task on its own, usually each of them is assigned to a subset of tasks. If agents are dependent upon each other via interrelated tasks they are assigned to, moderately-coupled teams of agents are called for. Such teams solve the task by coordinating during or after planning and revising their plans if necessary. In this paper we show that such complex tasks also can be solved by looselycoupled teams of agents that are able to plan independently, although the computational complexity of the coordination problems involved is high. We also investigate some of the factors influencing this complexity. Key words: Multi-agent system, complex tasks, task assignment, planning, coordination, computational complexity.
Abstract: We discuss a framework for coordinating self-interested agents that can be used to decompose a multi-agent task based planning problem into independent subproblems. This problem decomposition can be achieved by a simple protocol and allows the agents to solve their part of the problem without the need to interact with other agents and in such a way that the resulting plans can be seamlessly integrated into a joint plan without the need for revising individual plans. We illustrate the application of the framework to the logistic planning problems
used in the AIPS planning competition. After a thorough analysis of the problem we show how existing planners can beneï¬》 from such a decomposition technique.
Abstract: Decision support within transport companies should not only use traditional objective functions, but also reason about qualitative effects on all involved actors. We propose a fuzzy-logic rule base that can be used in addition to traditional operations research tools to calculate not just optimal solutions, but solutions that are optimal with respect to knowledge about the preferences of and long-term effects on customers, employees, and the environment.
We propose a fuzzy logic based judge module that is capable of evaluating logistical performance considering all parties involved in the act transporting a container. It is based on measurements of selected key performance indicators that are fuzzified and combined into satisfaction scores of customers, employees and society.
Our proposed method not only enables the continuity of the quality of planning by storing and maintaining valuable expert knowledge, but can also explain decisions based on this knowledge.
Abstract: Multi-attribute auctions allow negotiations over multiple attributes besides price. For example in task allocation, service providers can deï¬］e their service by means of multiple attributes, such as quality of service, deadlines, or delay penalties. Auction mechanisms assume that the players have evaluation functions over the space of attributes that assign a single value to any combination of attributes. This value (or cost) is directly comparable to price. We argue that in some situations, some of the attributes are diï¬ツult to convert to cost, e.g., in transportation it is often important which driver is going to deliver a given truckload. Such personal preferences of a customer are diï¬ツult to quantify.
To allow negotiations over such non-monetary attributes we relax the requirement of universally comparable utility functions, and give an incentive-compatible auction mechanism that uses only preference orders of the parties and not globally comparable function values. The suggested mechanism assumes that the bidders and the auctioneer have individual total orders over the space of possible contracts, but no utility functions. Each bidder places its bids using its own order, and the winner is chosen by the auctioneerâ冱 order. The actual attribute values are chosen based on the second-best bid. It is shown that this Vickrey intuition yields an incentive-compatible mechanism.
Abstract: In multi-agent planning problems agents are requested to jointly solve a complex task consisting of a set of interrelated tasks. Since none of the agents is capable to solve the whole task on its own, usually each of them is assigned to a subset of tasks. If agents are dependent upon each other via interrelated tasks they are assigned to, moderately-coupled teams of agents are called for. Such teams solve the task by coordinating during or after planning and revising their plans if necessary. In this paper we show that such complex tasks also can be solved by loosely- coupled teams of agents that are able to plan independently, although the computational complexity of the coordination problems involved is high. We also investigate some of the factors in uencing this complexity.
Abstract: Whenever independent, non-cooperative actors jointly have to solve a complex task, they need to coordinate their efforts. Typical examples of such task coordination problems are supply chain management, multi-modal transportation and patient-centered health care management. Common elements in such problems are a complex task, i.e., a set of interdependent subtasks, and a set of competitive actors. Solving a task coordination problem ï¬〉st of all requires to solve a task allocation problem (how to assign competitive actors to the subtasks). As a result, each of the actors will receive a set of subtasks to complete and will need to make a plan for this set of tasks. Therefore, also a plan coordination problem has to be solved (how to ensure that a joint plan always can be composed, whatever plan is chosen by the individual actors). The aim of this paper is twofold: ï¬〉st of all to present a general formal framework to study some computational aspects of this non-cooperative coordination problem, and secondly to establish some complexity results and to identify some of the factors that contribute to the complexity of this problem
Abstract: Logistical applications traditionally aim to decrease the cost of logistical activity. In accordance, researchers developed several techniques to compute economical routes for vehicles generating least costs. However, transportation companies experience a shift of emphasis in their planning nowadays. Due to the highly competitive nature of transportation, customer preferences play a more and more important role in planning. In our multi-agent model we chose to model customers as agents to emphasize their importance in planning. This is dierent from traditional models, where only vehicles are modeled. To have a package transported, a customer agent has to negotiate a contract with a transport agent. Any negotiation technique can be used to establish the contracts. To enable agents to adapt to changes, contracts can be broken and re-negotiated resulting in new agent plans.
This paper describes a multi-agent system where customer and vehicle agents dynamically change their contracts, hence change their planning. They use negotiation techniques like auctioning and decommitment to manipulate the contracts. Additionally, agents form coalitions to provide more sophisticated services, like multi-modal transportation.
Abstract: Agent technology is often suggested as a tool for developing software that is more adaptive in the face of changes in its environment. In agent-based approaches, complex automated systems are built from components that communicate with each other. To enable adaptive behaviour, both the components themselves and the communication architecture should be easily changeable. This paper presents the common hybrid agent platform (CHAP) that enables dynamic reconﬓuration of networks composed of small agents that may be changing themselves.
Abstract: Because of the apparent ineffectiveness of current disaster plans, we focus our research on modeling emergency response activities. If we can capture the crucial concepts of emergency response in a mathematical framework and apply this framework to construct disaster plans, then we pave the way for the development of automated decisions support systems for emergency response.
Abstract: We discuss task planning problems where a number of agents have to work on a joint planning problem that consists of a set of interdependent, hierarchically ordered tasks. Each agent is assigned a subset of tasks to perform for which it has to construct a plan. The agents are non-cooperative in that they insist on planning autonomously and do not want to revise their individual plans when a joint plan has to be assembled. The aim of this paper is twofold: first of all to present a general formal framework to study some computational aspects of this non-cooperative coordination problem, and secondly to establish some complexity results and to identify some of the factors that contribute to the complexity of this problem.
Abstract: We consider task planning problems where a number of noncooperative agents have to work on a joint problem. Such a problem
consists in completing a set of interdependent, hierarchically ordered tasks. Each agent is assigned a subset of tasks to perform for which it has to construct a plan. Since the agents are non-cooperative, they insist on planning independently and do not want to revise their individual plans when the joint plan has to be assemled from the individual plans. We present a formal framework to study some computational aspects of this non-cooperative coordination problem.
Abstract: We present a framework for coordinating autonomous planning agents. Together, these agents have to achieve a set of interdependent (elementary) tasks. Each of the agents receives a unique subset of tasks to achieve,
but an agent may be dependent on other agents completing (some of) their tasks ï¬〉st. Each of the agents needs to make a plan in order to achieve its set of subtasks. Task dependencies between tasks assigned to different agents, however, prevent them from making plans independently. Therefore, in order to guarantee planning autonomy, we need a pre-planning coordination method. We introduce a coordination method that can be used to guarantee a solution to the joint planning problem whatever individual plans the agents may have constructed independently. As a byproduct of our research, we show how this method can be applied to (re)use existing planning tools in a multi-agent context, by solving a multi-modal logistic planning problem by coordinating several autonomous vehicle routing planners.
Abstract: We discuss a general framework for coordinating self-interested agents in the pre-planning phase that can be used to decompose multi-agent task based planning problems into independent subproblems. The decomposition allows the agents to solve their part of the problem without the need to interact with other agents and such that the resulting plans can be easily combined into a joint plan. We illustrate the application of the framework to the logistic planning problems used in the AIPS planning competition. After a thorough analysis of the problem we show how existing planners can beneï¬》 from such a decomposition technique.
Abstract: We assume that a number of agents have to work together on some joint task T consisting of a number of elementary tasks t j , partially ordered by a set of precedence constraints. The elementary tasks are allocated to the agents using some given task allocation protocol (cf. [2]). We assume that (i) to perform its set of tasks, an agent needs to make a plan, and that (ii) each agent wishes to retain full planning autonomy, i.e., to retain the freedom to decide how to best perform its tasks.
Abstract: A planning problem can be transformed into a (temporal) constraint satisfaction problem called a Disjunctive Temporal Problem (DTP). Many planning problems have a distributed nature: multiple parties are involved in the
construction of a global plan. We discuss a multi-agent architecture where each agent acts as a DTP constraint solver responsible for the consistency of his own problem partition.
Though there are efficient algorithms for the Distributed Constraint Satisfaction Problem (DCSP), they can not be directly applied to a DTP. This is because multiple agents have to reach consensus over which simple constraint
in a disjunctive constraint to pursue. In this paper we propose a new method that combines the planning capabilities that DTPs oer with the distributed power found in DCSP algorithms. Our flexible representation and solutions provide ecient tools for on-line plan repair.
Abstract: Vehicle routing is an every-day problem for a range of companies from multi-national couriers to pizza boys all over the world. In this book, vehicle-routing problems that have to be solved in an uncertain environment are discussed. An agent-based and an on-line optimization-based approach to such vehicle-routing problems are discussed and their performance is compared in a set of realistic problem instances. It is shown that above certain levels of uncertainty, the agent-based heuristics outperform the on-line optimization method.
Abstract: In the ﬑ld of reservoir computing echo state networks (ESNs) and liquid state machines (LSMs) are the most commonly used networks. Comparative studies on these reservoirs identify the LSM as the network that yields the highest performance for speech recognition. But LSMs are not always usable in a real-time setting due to the computational costs of a large reservoir with spiking neurons.
In this paper a vowel classiſtation system is presented which consists of an ESN which processes cochlear ï¬〕tered audio. The performance of the system is tested on a vowel classiſtation task using different signal-to-noise ratios (SNRs). The usefulness of this method is measured by comparing it to formant based vowel classiſtation systems. Results show that this ESN based system can get a performance similar to formant based vowel classiſtation systems on the clean dataset with only a small reservoir and even outperforms these methods on the noisy dataset
Abstract: In actor-agent teams human and artificial entities interact and cooperate in order to enhance and augment their
individual and joint cognitive ergonomic and problem solving capabilities. Also actor-agent communities can benefit from â和mbient cognitionâ, a novel further reaching concept than ambient intelligence that hardly takes into account the resource limitations and capabilities changing over time of both humans and agents in collaborative settings. The Dutch Companion project aims at the realization of an agent that takes advantage of the ambient
cognition concerning actor-agent system dynamics such that natural emotion-sensitive interaction with an actor over a longer period of time can be sustained. We elaborate on our vision of pursuing ambient cognition within actor-agent systems and present the plans and expected results of the Dutch Companion project.
Abstract: In this document we examine an intelligent communications system (ASK) developed by Almende [1] and marketed by ASK Community Systems (ASK CS) [2] that provides several mechanisms for matching users requiring information or services with potential suppliers. The system oï¬ers intelligent and self-learning solutions using dynamic classiſtation, scheduling and feedback mechanisms, and is targeted at intelligent routing, dynamic resource planning and distributed knowledge management applications. Almende and ASK CS work in a synergistic collaboration, with Almende providing the continuing development of the ASK system using feedback given by ASK CS gained through its experience with deploying the system with clients.
Abstract: We consider the problem of coordinating autonomous agents that have to perform a joint task. This joint task consists of a set of elementary tasks, partially ordered by a set of precedence constraints. Each agent is assigned (using some given task allocation protocol) a subset of the available tasks. We assume that agents wish to be fully independent during the planning process, yet they are dependent on each other because of the precedences between tasks allocated to diï¬erent agents.
In this paper we concentrate on the following coordination problem: how to oï¬er complete autonomy for the participating agents in planning their part of the tasks, while at the same time guaranteeing that the individually constructed feasible plans (whatever they may be) are fully respected in constructing the joint plan. As we will see, this problem comes down to ï¬］ding a minimal set of additional constraints (a coordination set) such
that after adding these constraints a combined plan for executing all tasks can be achieved by simply joining whatever plans have been developed by the individual agents. We show that this problem can be decomposed into two subproblems: verifying that a given set of additional constraints is a coordination set, i.e., allows agents to plan independently (the coordination veriſtation problem), and ï¬］ding out whether a coordination set is of minimal size (the minimal coordination problem).
We will show that the coordination veriſtation problem alone is co-NPcomplete. In the general case, if the only dependencies are precedence constraints between tasks, the coordination problem is Σp2-complete; if we also
allow simultaneity constraints between tasks (i.e., constraints specifying that tasks may not be performed simultaneously), then the coordination problem is Î p3-complete. Even rather simple cases of the coordination problem turn out to be intractable and we show that it is very unlikely that constant-ratio approximation algorithms for this problem exist even if each agent has only a trivial planning task to perform.
Abstract: Ambient Intelligence is an emerging technology, and one domain where it can be applied is in intramural health care. In demented eldersâ homes, ambient intelligence could be used to track and identify people, so as to control environmental features, detect hazardous situations, make work more eï¬ツient, etc. We applied the paradigm of neural networks to sensor networks to create an algorithm that can track and identify agents in an environment. The algorithm is distributed, self-organizing and uses sensors that output only binary data. We tested the algorithm for its eï¬ツiency both in a simulation and for its feasibility in a real world prototype.
Abstract: We consider the problem of coordinating autonomous agents that have to achieve a joint task, consisting of a set of (elementary) tasks, partially ordered by a set of precedence constraints. Each agent is allocated a non-overlapping subset of tasks, for which it needs to make a plan. Precedences may exist between tasks allocated to the same agent (intra-agent precedences), or between tasks allocated to diï¬erent agents (inter-agent precedences). Because of the latter set of constraints, agents are dependent on each other, and coordination is required for successful joint operation.
We assume that an agent needs to make a plan to execute its subset of tasks. To guarantee an agent full autonomy in the planning of its tasks, we require that planning and coordination be separated. In the literature on multi-agent coordination, no approach yet exists where agents can (i) work together on a joint task, and (ii) where planning and coordination are separated. Therefore, we present a new pre-planning coordination framework in which agents receive a set of additional constraints prior to planning, such that subsequently the joint plan will always be feasible, regardless of the plans produced
by the individual agents.
The coordination problem, which is to ï¬］d a minimal set of additional constraints such that a feasible joint plan is guaranteed, is computationally hard. The problem of verifying whether a given set of additional constraints is a coordination solution (the coordination veriſtation problem) is co-NP-complete. The coordination problem itself is Σp2-complete.
Finally, we can show that it is highly unlikely that constant-ratio approximation algorithms exist for the coordination problem.
Nevertheless, we have designed approximation algorithms that return very eï¬ツient solutions when applied to the multi-modal logistics problem (which consists of delivering packages between and within cities). In fact, our pre-planning coordination algorithms (i) outperform state-of-the-art (multi-agent) planning systems on a set of benchmark logistic problems, and (ii) show that by eï¬ツiently separating planning from coordination, existing (single-agent) planning tools can be reused to solve multi-agent planning problems.
DOI 
