doc. Ing. Jiří Vokřínek, Ph.D.

Electric vehicle (EV) travel planning is a complex task that involves planning the routes and the charging sessions for EVs while optimizing travel duration and cost. We show the applicability of the multi-objective EV travel planning algo- 5 rithm with practically usable solution times on country-sized road graphs with a large number of charging stations and a realistic EV model. The approach is based on multi-objective A* search enhanced by Contraction hierarchies, optimal dimensionality reduction, and sub-optimal ϵ-relaxation tech10 niques. We performed an extensive empirical evaluation on 182 000 problem instances showing the impact of various algorithm settings on real-world map of Bavaria and Germany with more than 12 000 charging stations. The results show the proposed approach is the first one capable of performing 15 such a genuine multi-objective optimization on realistically large country-scale problem instances that can achieve practically usable planning times in order of seconds with only a minor loss of solution quality. The achieved speed-up varies from ∼ 11× for optimal solution to more than 250× for sub20 optimal solution compared to vanilla multi-objective A*.

Being an NP-hard problem, multicriteria shortest path search is difficult to solve with speed satisfactory for real-world use. Therefore, this article examines the combination of t-discarding kPC-MLS [1] and multiple pruning heuristics. Apart from comparing the efficiency of the individual techniques, the research also evaluates the ability of t-discarding kPC-MLS to employ such heuristics. Since the experiments were conducted on country-size roadmaps, the results are expected to be relevant to real-world applications. According to the measurements, t-discarding kPC-MLS gains a higher speedup than standard MLS [2], operating on comparable roadmaps in a matter of seconds.

In large-scale automated mobility-on-demand systems, the fleet manager is able to assign routes to individual automated vehicles in a way that minimizes formation of congestion. We formalize the problem of on-demand fleet routing in capacitated networks with time-varying demand. We demonstrate the limits of application of the steady-state flows approach in systems with time-varying demand and formulate a linear program to compute congestion-free routes for the vehicles in capacitated networks under time-varying demand. We evaluate the proposed approach in the simulation of a simplified, but characteristic illustrative example. The experiment reveals that the proposed routing approach can route 42% more traffic in congestion-free regime than the steady-state flow approach through the same network.

Routing of a fleet of automated unit-occupancy vehicles in a capacitated transportation network is an emerging problem that needs to be addressed to realize large-scale automated transportation systems. We adopt an existing network-flow-based model for the problem and present a new reformulation based on Dantzig-Wolfe decomposition. This reformulation allows us to apply the column generation solution technique which, in turn, enables us to solve large-scale problem instances with tens of thousands of requests on networks with thousands of links. We empirically compare our method to the state-of-the-art approach on several standard benchmark instances and find that the computational time of our solution approach scales qualitatively better in all tested problem instance parameters: namely, in the size of the transportation network, in the magnitude of demand intensity, and in the number of demand flows.

Intelligent cars represent a promising technology expected to drastically improve safety and efficiency of automobile transportation. In this paper, we introduce an agent-based simulation platform AgentDrive and argue that it can be used to speed up the development and evaluation of new coordination algorithms for intelligent cars. We present the high-level architecture of the simulator and characterize the class of tasks for which is the tool best suited. In addition, we present a case study of AgentDrive being used for development of a lane-changing assistant technology. We describe the developed solution in detail and present the benchmark result, which were obtained using AgentDrive simulator, that demonstrate that coordinated lane changing enables safer and swifter lane changing then the traditional non-coordinated approach.

In this chapter, we present the concept of an integrated multi-agent simulation platform to support the development and validation of autonomic cooperative car-to-car systems. The simulation allows to validate the car-to-car coordination strategies in various traffic scenarios in variable technology penetration levels (i.e. mixing different strategies) and user acceptance of such system as an external observer and/or as a part of the traffic (human in the loop with intelligent cooperative guidance system). The platform combines features of realistic driving simulation, traffic simulation with flexible level of detail and AI controlled vehicles. The principal idea of the platform is to allow the development and study of complex autonomic distributed car-to-car systems for vehicles coordination. The platform provides a development environment and a tool chain that is necessary for the validation of such complex systems. Autonomic car-to-car systems are based on coordination mechanisms between agents, where an agent represents a reasoning unit of a single vehicle. The road traffic is modelled as a multi-agent system of cooperative agents. The interaction between the agents brings autonomic properties into the emerged system (e.g. the traffic adapts to a blockage of a lane and vehicles merge into a second lane). The system also exhibits autonomic properties from a single user perspective. The driver approaches the system in a form of a driver assistance system—we can refer it as an autonomic driver assistance system. The driver is interacting only with the assistance system via a human-machine interface (HMI). The autonomic driver assistance system is hiding the complexity of multi-agent interactions from the user. The related agent of the single vehicle is responsible for an interaction with other agents in the system without any user’s intervention.

Multi-agent approach to study coordination among intelligent cars is discussed. Intelligent cars are presented as a promising domain for multi-agent applications as modelling, simulations and coordination algorithms. AgentDrive coordination platform is introduced to illustrate possibilities in development of such applications. AgentDrive allows development of coordination algorithms and their validation via simulation. The ‘coordination algorithms’ notion covers some of the following tasks: dynamic routing, trajectory planning, collision avoidance and cooperation. Simulation can be performed in an arbitrary level of detail by using various external physics simulators.

We suggest an efficient polynomial algorithm for the vehicle routing problem with time windows (VRPTW) based on agent negotiation. A generic agent decomposition of the problem is introduced featuring a clear separation between the local planning performed by the individual vehicles and the abstract global coordination achieved by negotiation --- differentiating the presented algorithm from the classical centralized algorithms. The semantic of the abstract negotiation process is discussed as well as the two alternative local planning strategies used by the individual vehicles. A relevant comparison to the state-of-the-art classical and agent-based algorithms is provided missing from most previous agent-based studies. The algorithm performs slightly worse than the state-of-the-art classical algorithms but improves on all the previous comparable agent-based algorithms.

We consider a system consisting of multiple mobile robots in which the user can at any time issue relocation tasks ordering one of the robots to move from its current location to a given destination location. In this paper, we deal with the problem of finding a trajectory for each such relocation task that avoids collisions with other robots. The chosen robot plans its trajectory so as to avoid collision with other robots executing tasks that were issued earlier. We prove that if all possible destinations of the relocation tasks satisfy so-called valid infrastructure property, then this mechanism is guaranteed to always succeed and provide a trajectory for the robot that reaches the destination without colliding with any other robot. The time-complexity of the approach on a fixed space-time discretization is only quadratic in the number of robots. We demonstrate the applicability of the presented method on several real-world maps and compare its performance against a popular reactive approach that attempts to solve the collisions locally. Besides being dead-lock free, the presented approach generates trajectories that are significantly faster (up to 48% improvement) than the trajectories resulting from local collision avoidance.

We demonstrate how AgentDrive platform can be used to develop agent-based driver assistance systems. We expect that new V2X technologies penetrating automotive industry can lead to more sophisticated coordination mechanisms among road vehicles. Driver assistance system that is enabled to communicate with other vehicles promises safer and more efficient future of road traffic. AgentDrive allows to prototype agent-based coordination mechanisms. The developer using our platform is provided with a tool to prepare realistic simulation scenarios. The scenarios are based on real world data generated from OpenStreetMap. The development of the sophisticated multi-agent coordination algorithms is supported by possibility to evaluate the algorithms in arbitrary level of simulation detail. Human-in-the-loop simulation is enabled by integrating a driving simulator. Developers are empowered to challenge multiagent coordination algorithms by the presence of a human driver in the control loop.

Avoiding collisions is one of the vital tasks for systems of au- tonomous mobile agents. We focus on the problem of find- ing continuous coordinated paths for multiple mobile disc agents in a 2-d environment with polygonal obstacles. The problem is PSPACE-hard, with the state space growing ex- ponentially in the number of agents. Therefore, the state of the art methods include mainly reactive techniques and sampling-based iterative algorithms. We compare the performance of a widely-used reactive method ORCA with three variants of a popular planning algorithm RRT* applied to multi-agent path planning and find that an algorithm combining reactive collision avoid- ance and RRT* planning, which we call ORCA-RRT* can be used to solve instances that are out of the reach of ei- ther of the techniques. We experimentally show that: 1) the reactive part of the algorithm can efficiently solve many multi-agent path finding problems involving large number of agents, for which RRT* algorithm is often unable to find a solution in limited time and 2) the planning component of the algorithm is able to solve many instances containing local minima, where reactive techniques typically fail.

This demonstration presents the integrated multi-agent traffic simulation for human-in-the-loop cooperative drive systems testing. Its openness and flexibility supports a wide range of testing and validation possibilities for the researchers and developers in the field of autonomous vehicles, cooperative drive, driver assistants, and HMI design and development. The system is able to integrate various driving simulators, car control techniques, cooperative car coordination and user-driven vehicles. The usability of the system is demonstrated in various scenarios and configurations.

This paper introduces a novel mobility model for indoor conference scenarios. A multi-agent event-based simulator for evaluation of crowd behavior is used for users’ movement modelling inside a conference scenario. The radiowave propagation calculation is performed using a 3D semideterministic propagation model. Based on the two inputs, it is shown that users’ behavior needs to be taken into account when designing a new wireless network. If not, some of the access points can be overloaded for most of the time, while the rest can remain idle despite the fact that they provide satisfactory coverage in the entire scenario.

In this paper, we address the multi-goal motion planning problem in which it is required to determine an order of visits of a pre-specified set of goals together with the shortest trajectories connecting the goals. The considered problem is inspired by inspection planning missions, where multiple goals must be visited with a required precision. The problem combines challenges of the combinatorial traveling salesman problem with difficulties of the motion planning. The presented approach is based on unsupervised learning of the self-organizing map technique for the traveling salesman problem applied in the configuration space. This learning technique takes an advantage of acquiring information about exploring the configuration space into a topology of the map that is simultaneously exploited in determination of the multi-goal trajectory and further directions of motion planning roadmap expansion. Presented results indicate that the proposed approach is feasible and it is able to provide a solution of the multi-goal motion planning problem without a priori known sequence of the goals visits.

In this paper, a cooperative driver model for a multi-agent traffic simulation is proposed. The model combines maneuver-based trajectory planning of the vehicles with a cooperative conflict resolving. The proposed model is able to provide a safe drive in complex traffic situations at the highest possible speed. The idea of the model and its feasibility have been verified in complex scenarios such as line change under heavy traffic, highway entering or highway crossing. Moreover, the developed cooperative driver model is being integrated with a human operated driving simulator that enables verification of the proposed model in mixed scenarios enriching the simulation for a human driver with highly cooperative background traffic; thus, providing a platform for further studies on benefits of assistive technologies. The paper provides description of the proposed model and its early evaluation on the selected scenarios in a multi-agent traffic simulation.

We present an efficient route minimization algorithm for the vehicle routing problem with time windows. The algorithm uses a generic agent decomposition of the problem featuring a clear separation between the local planning performed by the individual vehicles and the abstract global coordination achieved by negotiation --- differentiating the presented algorithm from the traditional centralized algorithms. A novel negotiation semantics is introduced on the global coordination planning level allowing customers to be temporarily ejected from the emerging solution being constructed. This allows the algorithm to efficiently backtrack in situations when the currently processed customer cannot be feasibly allocated to the emerging solution. Over the relevant widely-used benchmarks the algorithm equals the best known solutions achieved by the centralized algorithms in 90.7% of the cases with an overall relative error of 0.3%, outperforming the previous comparable agent-based algorithms.

In this paper, the multi-robot motion coordination planning problem is addressed. Although a centralized prioritized planning strategy can be used to solve the problem, we rather consider a decentralized variant, which is a more suitable for a robotic system of cooperating unmanned aerial vehicles (UAVs) due to communication limitations, privacy concerns, and a better exploitation of computational resources distributed among the individual robots. However, the existing decentralized prioritized planning algorithm contains synchronization points that all the agents must be able to pass synchronously, which is impractical and inefficient for a real-world deployment of the robotic systems. Therefore, we introduce a new asynchronous decentralized prioritized planning algorithm and show that the method can converge faster than both the synchronous decentralized and centralized algorithms. Further, we demonstrate the applicability of the proposed method as a coordination mechanism within a complex mission planning for a real robotic system consisting of several autonomous UAVs.

Small Unmanned Aerial Vehicles (UAVs) are becoming increasingly popular for tasks such as surveillance or target tracking in various types of tactical missions. Traditionally, each UAV in a mission is controlled by one or more operators. In our previous work we have developed a collection of distributed algorithms that allow one operator to control a whole team of small UAVs. Here, we report on our successful effort to deploy the developed multi-agent control algorithms to a team of hardware UAVs. To reduce costs and risk, we first developed the multi-agent control algorithms using simulated approximation of the target environment. Then, we gradually refined the model of the target environment by adding higher-fidelity models of the assets and hardware-in-the loop assets. In the final step, the algorithms were deployed and field tested in a full hardware setting and in a mixed-reality setting, where hardware UAVs are accompanied by a a number of simulated UAVs.

The development process and simulation architecture presented here help narrow the gap between how theoretical AI algorithms are traditionally designed and validated and how practical algorithms for controlling robotic assets in simulated tactical missions are developed.

Cooperative pathfinding is a problem of finding a set of non-conflicting trajectories for a number of mobile agents. Its applications include planning for teams of mobile robots, such as autonomous aircrafts, cars, or underwater vehicles. The state-of-the-art algorithms for cooperative pathfinding typically rely on some heuristic forward-search pathfinding technique, where A* is often the algorithm of choice. Here, we propose MA-RRT*, a novel algorithm for multi-agent path planning that builds upon a recently proposed asymptotically-optimal sampling-based algorithm for finding single-agent shortest path called RRT*. We experimentally evaluate the performance of the algorithm and show that the sampling-based approach offers better scalability than the classical forward-search approach in relatively large, but sparse environments, which are typical in real-world applications such as multi-aircraft collision avoidance.

Cooperative pathfinding is a problem of finding a set of non-conflicting trajectories for a number of mobile agents. Its applications include planning for teams of mobile robots, such as autonomous aircrafts, cars, or underwater ve- hicles. The state-of-the-art algorithms for cooperative pathfinding for embod- ied robots typically rely on some heuristic forward-search pathfinding technique, where A* is often the algorithm of choice. Here, we propose MA-RRT*, a novel algorithm for multi-agent motion planning that builds upon a recently proposed asymptotically-optimal sampling-based algorithm called RRT*. In this paper, we focus on the case where the agents’ mobility model is a discrete graph. We eval- uate the performance of the proposed algorithm and its scalability with respect to the number of agents and the size of the environment. Our results show that the sampling-based approach offers better scalability than the classical forward- search approach in relatively sparse environments, which are typical in real-world applications such as multi-aircraft collision avoidance.

Since late 90’s of the last century, rapid advances in technology, mechanical engineering, miniaturization, telecommunications and informatics enabled development and routine deployment of sophisticated robots in many real world domains. Besides many applications in assembly industry, e.g., in car, or electronics assembly lines, defense organizations, together with space exploration and mining industries belong to the most demanding and optimistic users of robotic technology [25]. Especially in the military domain we nowadays witness a routine deployment of robotic assets in the field.

We present an ongoing effort in developing efficient agent-based algorithms for solving the vehicle routing problem with time windows. An abstract algorithm based on a generic agent decomposition of the problem is introduced featuring a clear separation between the local planning performed by the individual vehicles and the global coordination achieved by negotiation. The semantics of the underlying negotiation process is discussed as well as the alternative local planning strategies used by the individual vehicles. Finally a parallel version of the algorithm is presented based on efficient search diversification and intensification strategies. The presented effort is relevant namely for (i) yielding results significantly improving on all previous agent-based studies, (ii) the inclusion of relevant widely-used benchmarks missing from these studies and (iii) the breadth and depth of the provided evidence and analysis including relevant comparison to the state-of-the-art centralized solvers.

The goal of the paper is to present an application of TARF (Task Agent Resource Function) in UAV domain. This TARF is used to optimize the tasks allocation in case of cooperation between multiple Unmanned Aerial Vehicles. It plays the role of a generic mission planner for cross domain such as UAV, maritime, automotive and manned aerial vehicle (MAV). This paper concentrates on how to integrate TARF in Paparazzi platform - an UAV platform based on PPRZ autopilot - in order to perform a swarm of aircrafts doing different tasks. The TARF contributes a new module to this platform for the simulation and real demonstrations.

We suggest an efficient algorithm for the vehicle routing problem with time windows (VRPTW) based on agent negotiation. The algorithm is based on a set of generic negotiation methods and state-of-the-art insertion heuristics. Experimental results on well known Solomon's and Homberger-Gehring benchmarks demonstrate that the algorithm outperforms previous agent based algorithms. The relevance of the algorithm with respect to the state-of-the-art centralized solvers is discussed within a comprehensive performance and algorithmic analysis, that has not been provided by previous works. The main contribution of this work is the assessment of general applicability of agent based approaches to routing problems in general providing for a solid base for future research in this area.

Cooperative pathfinding is a multi-agent path planning problem where a group of vehicles searches for a corresponding set of non-conflicting space-time trajectories. Many of the practi- cal methods for centralized solving of cooperative pathfinding prob- lems are based on the prioritized planning strategy. However, in some domains (e.g., multi-robot teams of unmanned aerial vehicles, au- tonomous underwater vehicles, or unmanned ground vehicles) a de- centralized approach may be more desirable than a centralized one due to communication limitations imposed by the domain and/or pri- vacy concerns. In this paper we present an asynchronous decentralized variant of prioritized planning ADPP and its interruptible version IADPP. The algorithm exploits the inherent parallelism of distributed systems and allows for a speed up of the computation process. Unlike the synchro- nized planning approaches, the algorithm allows an agent to react to updates about other agents' paths immediately and invoke its local spatio-temporal path planner to find the best trajectory, as response to the other agents' choices. We provide a proof of correctness of the algorithms and experimentally evaluate them on synthetic domains.

We suggest an improved algorithm for the vehicle routing problem with time windows (VRPTW). The algorithm is based on negotiation between a fleet of agents corresponding to the routed vehicles using a set of generic negotiation methods and a state-of-the-art insertion heuristic. A search diversification and pruning strategy is introduced which allows for a wide range of competing algorithm instances to be instantiated and efficiently managed throughout the solving process. Experimental results on the widely used Solomon's and the extended Homberger's benchmarks prove that the algorithm is broadly competitive with respect to the established centralized state-of-the-art algorithms equalling the best known solutions in 64% of the cases with an overall relative error of 2.4%, thus achieving a new best known result for an agent based algorithm to date. The vastly improved negotiation process and the inherent parallelization features provide for excellent anytime features, outperforming even the state-of-the-art algorithms in this respect.

In this paper we present a parallel solver for the vehicle routing problem with time windows (VRPTW) and the pickup and delivery problem with time windows (PDPTW). The solver is based on parallel competition of particular solvers solving the given problem instance. The particular solvers are based on negotiation between a fleet of agents representing individual vehicles using a cost structure corresponding to the well-known travel time savings insertion heuristic. The performance of the solver is assessed on the Homberger-Gehring and Li-Lim benchmark sets for the VRPTW and PDPTW case respectively. While both sets are widely used across the routing community, they were not addressed by previous agent-based studies. Thus the achieved average solution quality of 95% and 87% for the VRPTW and PDPTW cases represents a new best known result for these benchmark sets for agent-based approaches. An analysis of the solver's convergence, runtime and parameter sensitivity is provided within the experimental evaluation section that has also not been provided by previous agent-based studies.

Problem solving and planning in decentralized environments is a key technical challenge in numerous industrial applications, ranging from manufacturing, logistics, virtual enterprizes to multirobotics systems. We present an abstract architecture of a multiagent solver and respective algorithm providing decomposition, task allocation, and task delegation. Various features of the abstract architecture, such as computational complexity or admissibility of the underlying optimization heuristics, are analyzed in the paper. Four instances of the abstract architecture implementations are given to demonstrate the applicability of the abstract solver in a wide variety of real-problem domains.

This paper proposes a mechanism for simulating limited com- munication bandwidth and processing power available to an agent in multi-agent simulations. Although there exist dedicated tools able to simulate computer networks, most multi-agent platforms lack support for this kind of resource allocation. We target such multi-agent plat- forms and offer an easy method to implement the missing functionality by the agent designer. The introduced method assigns two additional message buffers to each agent, which are used to (i) limit the number of messages an agent is able to send in one simulation round, and (ii) limit the number of messages an agent is able to process in one simulation round.

Autonomous control of group of unmanned aerial vehicles based on task allocation mechanisms shows great potential for ground tactical mission support. We introduce experimental simulation system combining flexible mission control of ground assets in urban environment and autonomous aerial support utilizing multi-agent problem solving techniques. Two case-studies are presented for evaluation - cooperative area surveillance and dynamic target tracking with undervalued number of assets. We show the strength and benefits of multi-agent task allocation and delegation mechanisms in such dynamic scenarios mainly in case of limited number of assets.

We present an approach to plan representation in multi-actor scenarios that is suitable for flexible replanning and plan revision purposes in dynamic non-deterministic multi-actor environments. The key idea of the presented approach is in representation of the distributed hierarchical plan by social commitments, as a theoretically studied formalism representing mutual relations among intentions of collaborating agents. The article presents a formal model of a recursive form of commitments and discusses how it can be deployed to a selected hierarchical planning scenario. The decommitment rules definition and their influence on the plan execution robustness and stability is also presented. The approach was verified and evaluated in a simulated environment. The experimental validation confirms the performance, stability, and robustness of the system in complex scenarios.

A multi-agent VRP solver is presented in this paper. It utilizes the contract-net protocol based allocation and several improvement strategies. It provides the solution with the quality of 81% compared to the optimal solution on 115 benchmark instances in polynomial time. The self-organizing capability of the system successfully minimizes the number of vehicles used. The presented solver architecture supports great runtime parallelization with incremental increase of solution quality. The presented solver demonstrates applicability to the VRP problem and easy adaptation to problem variants.

Navigation of unmanned ground vehicles in an urban area is a fundamental problem which has to be solved prior to real-world deployment of the autonomous ground assets. Since the topology data of the environment are usually known a priori, they can be exploited in high-level planning of the routes. On the other hand, the low-level robot control requires precise path to follow and thus trajectory planning has to be adopted as well. Finally, the particular details of the environment can differ from the known topology and thus the vehicles need an area exploration method. The integrated multi-agent system for cooperative navigation in partially unknown urban environment is introduced and validated using vehicle physics based simulation. The goal is to support the navigation of a convoy by a set of unmanned vehicles in an urban environment to avoid convoy stops or u-turns and minimize the total traveled distance of all vehicles.

This chapter presents set of different decision support systems to demonstrate different ways, how the decision support process can be extended outside a single company

Monitoring of fulfilment of obligations defined by electronic contracts in distributed domains is presented in this paper. A two-level model of contract-based systems and the types of observations needed for contract monitoring are introduced. The observations (inter-agent communication and agents' actions) are collected and processed by the contract observation and analysis pipeline. The presented approach has been utilized in a multi-agent system for electronic contracting in a modular certification testing domain.

Electronic contracting, based on explicit representation of different parties's; commitments, is a promising way to specify and regulate behaviour in distributed business applications. In this paper, we show how the contract-based approach can be employed in the domain of European Computer Driving Licence (ECDL) testing in which test centres, testers and test room operators cooperate in order to deliver certification testing to ECDL candidates. We describe how the cross-organisational transactions involved in ECDL testing can be specified in terms of machine-processable business contracts and how these contracts can be automatically negotiated, managed and monitored using the technologies developed in the IST-CONTRACT project. The application of the contracting technology enables important business advantages, in particular increased flexibility and reliability in delivering the testing services to ECDL candidates.

The process of planning in complex, multi-actor environment depends strongly on the ability of the individual actors to perform intelligent decommitment upon specific changes in the environment. Reasoning about decommitment alternatives during the planning process contributes to flexibility and robustness of the resulting plan. In this article we formally introduce and discuss three specific decommitment rules: (i) relaxation, (ii) delegation and (iii) full decommitment. We argue that appropriate selection, setting and preference ordering of the decommitment rules contributes to robustness (measured as a number of failures) of the overall plans. The presented claims are supported by empirical experiments.

We present a demonstration of a multi-agent prototype for distributed planning and coordination in dynamic non-deterministic multi-actor mixed-initiative environments. The system provides flexible planning, replanning, and task allocation. The key technologies utilized in the system are (i) I-X hierarchical planner with (ii) agent-based architecture and (iii) commitment-based plan representation. The implementation of the system was verified and evaluated in simulated environment. The experimental validation confirms the performance, stability, and robustness of the system in complex scenarios. In this demonstration we present the compilation of the most representative scenarios.

We present an approach to distributed planning and coordination architecture for dynamic non-deterministic multi-actor mixed-initiative environment. The system provides flexible planning, replanning, and task allocation. The key idea of the presented approach is in integration of (i) I-X hierarchical planner with (ii) agent-based architecture and (iii) commitment-based plan representation. The implementation of the system was verified and evaluated on simulated environment. The experimental validation confirms the performance, stability, and robustness of the system in complex scenarios.

Resources planning system for domain of modular certification testing is presented in this paper. In our domain, there are several independent resources owners and services providers, who together are able to provide their customers with service of certification testing. We are presenting concept of distributed system for supporting negotiation about the certification testing session's life-cycle support, i.e. from the session arrangement, through its execution, to results distribution. Each of the session participants is represented by mutually independent agents supporting all the certification session processes except the act of filling and evaluation of tests.

One of the problems that must be solved during coalition operations is the planning problem: finding a course of actions for the operation. Knowledge-based planning is a technique that can be used to address this problem. However, traditional planning has focussed on the finding of a plan that achieves a given goal or accomplishes a given task. During a coalition operation such a plan may need to be agreed between the different parties involved in the coalition. In this paper we shall describe an approach that can be used for finding an agreed plan. This plan will include a set of decommitment rules allowing participants to specify conditions under which they are allowed to deviate from the agreed course of action. The proposed algorithm can be used as the basis for an automated planner, but it should also be usable in a mixed-initiative setting.

The role of social commitments in distributed, multi-agent planning and plan execution will be discussed in this article. We argue agents' capability to reason about the actions in the form of social commitments directly improving robustness of the plans in dynamic, multi-actor environment. We focused on relaxation decommitment strategy, targeted specifically to the time interval in which the agent agrees to accomplish the commitment. We will discuss how changes of this interval affect the plan execution and how the potential changes of this interval can be represented in the commitment itself. The value of the use of social commitments in planning in dynamic, multi-actor environment has been documented on a series of empirical experiments.

The only possibility for Small and Medium Enterprises (SMEs) to succeed in marketing competition with big corporations is cooperation and sharing of knowledge and resources. A promising way to cooperate and keep their independence is the formation of semipermanent collaborative networks, which facilitate Virtual Organisation (VO) creation and management. This work concentrates on the maintenance and facilitation of partners' profiles and competency management in such networks. The aim of our effort is to support potential partner identification during the VO creation and adaptation processes, as well as the facilitation of advertisement of oneself to be identified as a potential partner. The contributions of the work are the definition of competency and profile-related terms, the description of competency structures and an architecture of a competency and profiles management system, as well as a prototype verifying the presented theoretical work in a real business environment.

The proposed protocol has been designed to support the flexible formation of Request-Based Virtual Organisations (RBVOs) with an emphasis on reflecting the conditions of real competitive environments. It supports automated or semi-automated negotiations mainly in the creation part of a Virtual Organisation (VO) life cycle and it accounts for the use of Service Level Agreements (SLAs). The protocol consists of three phases: (1) potential partner search, (2) negotiation of SLAs and the RBVO establishment, and (3) RBVO (execution and) dissolution. The protocol complies with Foundation for Intelligent Physical Agents (FIPA) standards and it has been utilised in the multiagent prototype in a real industrial case. The prototype has been implemented on top of a web-service-based agent platform.

This demonstration concentrates on eServices (supporting electronic services) for Virtual Organization (VO) management support. The eServices are provided by the VOM toolkit (a suite of VO management tools), which was developed to support the VO manager in managing the VO throughout its life-cycle. In this demo the eServices related to all phases of the VO life-cycle are demonstrated together with the toolkit and benefits identified during pilot testing.

The Decision Support System (DSS) for Virtual Organization Management is a component of the Virtual Organization (VO) management toolkit, which is being developed in the ECOLEAD project. The DSS mainly supports VO operational and strategic management by simulated rescheduling and reconfiguration of a VO. Such simulations allow "what-if-analysis", verifying and comparing various configurations and their robustness, discovering possible bottlenecks, and pre-preparing potential adaptations of VO configuration and schedule. The outputs are presented in a "human-friendly" way to support the VO manager in decision about and negotiation for VO adaptation.

This article presents a concept and a prototype of a tool for profile and competency management for SME clusters - the e-Cat. The main goal is to simplify and integrate cooperation between SMEs by sharing information about their abilities, competencies and services that collaboratively cover new business opportunities. The e-Cat is based on a hybrid architecture consisting of peer-to-peer cooperating units supported by centralized components.

The ExtraPlanT system addresses the concept of the extra-enterprise production planning in order to manage efficient resource allocation not only within the enterprise, but also at the company external environments (e.g. suppliers, co-operators involved in the supply chain or virtual organization environments). ExtraPlanT demonstrates the ability of multi-agent systems to improve business processes on the extra-enterprise level and to bring the virtual organization ideas to the real industrial environment.

This paper presents a specific contracting algorithm that contributes to the process of distributed planning and resource allocation in competitive, semi-trusted environments. The presented contraction algorithm is based on incrementally refined acquaintance models (IRAM) of the actor that provide the right set of approximate knowledge needed for appropriate task decomposition and delegation. This paper reports on empirical evaluation of the IRAM algorithm deployment in consortia formation domain.

This paper presents a specific contracting algorithm that contributes to the process of distributed planning and resource allocation in competitive, semi-trusted environments. The presented contraction algorithm is based on incrementally refined acquaintance models (IRAM) of the actor that provide the right set of approximate knowledge needed for appropriate task decomposition and delegation. This paper reports on empirical evaluation of the IRAM algorithm deployment in Request-based Virtual Organizations formation domain.

We present an approach to plan representation in multi-actors scenarios that is suitable for flexible replanning and plan revision purposes. The key idea of the presented approach is in integration of (i) the results of an arbitrary HTN (hierarchical task network) -oriented planner with (ii) the concept of commitments, as a theoretically studied formalism representing mutual relations among intentions of collaborating agents. The paper presents formal model of recursive form of commitments and discusses how it can be deployed to a selected scenario.

The paper presents the concept of ProPlanT multi-agent system which has been designed for planning the manufacturing process in project driven production domain.

Service-Oriented Architectures (SOAs) enable businesses to flexibly address their current and future needs in an agile manner. This is achieved by organizing their software assets as interoperable services, which can be flexibly, cost-effectively and timely combined to form business processes according to business requirements. A SOA approach however can also benefit Virtual Organizations (VOs), by enabling participant companies to increase their responsiveness and adaptability with regards to addressing a collaborative business opportunity. Value can also be added to the operations of such a VO with the use of Web2.0 concepts, as well as Intelligent Agents to automate the processes of finding collaborating partners and negotiating the creation of VOs, based on user-defined business rules.

Sharing information about profiles and offered competencies of individual members within an alliance of cooperating companies facilitates searching for potential members of Virtual Organizations. This paper presents a concept of structuring of the competencies as well as a prototype proving this concept. The prototype follows a naturally hybrid architecture of alliances that consists of mutually independent alliance partners, who may be supported by central institutions of the alliance. The use of the agent-based solution enables information sharing among partners in such distributed and dynamic environment.

The proposed Competitive Contract Net Protocol has been designed to facilitate a flexible cooperation in competitive multi-agent environments and to support automated or semi-automated negotiations in competitive domains. The protocol is based on FIPA standards. The protocol covers not only the phase of contracting the commitments, but also allows for a decommitment negotiation and contract termination. Thus, it consists of three phases: (i) a contracting phase, where conditions of agreement are concluded, (ii) an optional decommitment phase, where contract may be breached, and (iii) a contract termination phase, where the compliance with the concluded contract conditions is evaluated

A cooperation of agents in competitive environments is more complicated than in collaborative ones. Both the replanning and reconfiguration play the crucial role in the cooperation and introduce a means for an implementation of a system flexibility. The concepts of commitments, decommitments with the penalties and subcontracting may facilitate effective reconfiguration and replanning. Agents in competitive environments are fully autonomous and self-interested. Therefore the setting of penalties and the profit computation cannot be provided centrally. Both the costs and gain differ from agent to agent with respect to contracts already agreed and resources load. This paper proposes an acquaintance model for contracting in competitive environments and introduces possibilities of a reconfiguration in competitive environments as a means of a decommitment optimization with respect to resources load and profit maximization.

The proposed protocol has been designed to support a flexible formation of Request-based Virtual Organizations with an emphasis on reflecting the conditions of real competitive environments. It supports automated or semi-automated negotiations mainly in the creation part of a Virtual Organization life cycle and accounts for a use of Service Level Agreements. The protocol consists of three phases: (i) potential partner search, (ii) negotiation of SLAs and RBVO establishment, and (iii) RBVO execution and dissolution. The protocol is based on FIPA standards.

Cílem příspěvku je seznámit s návrhem a vývojem systému pro inteligentní podporu rozhodování v oblasti domácí péče.

Cílem příspěvku je seznámit s návrhem a vývojem systému pro inteligentní podporu rozhodování v oblasti domácí péče.

A cooperation of agents in competitive environments is more complicated than in collaborative ones. Both the replanning and reconfiguration play the crucial role in the cooperation and introduce a means for an implementation of a system flexibility. The concepts of commitments, decommitments with the penalties and subcontractions may facilitate effective reconfiguration and replanning. Agents in competitive environments are fully autonomous and self-interested. Therefore the setting of penalties and the profit computation cannot be provided centrally. Both the costs and gain differ from agent to agent with respect to contracts already agreed and resources load. This paper introduces possibilities of a reconfiguration in competitive environments as a means of a decommitment optimization with respect to resources load and profit maximization.

The e-Cat is a research prototype of a tool for maintenance of members' profiles and competencies in a Virtual Organisation Breeding Environment. The system combines peer-to-peer approach and centralized architecture. Distribution enables members to maintain their profiles locally and to work in the off-line mode when needed. Centralized components of the system ensure coherence in the common schema of competency and support common understanding. They also prevent anonymous users from advertising incorrect data via the catalogue and allow full control over members entering or leaving the community.

A cooperation of agents in competitive environments is more complicated than in collaborative ones. Both the replanning and reconfiguration play the crucial role in the cooperation and introduce a means for an implementation of a system flexibility. The concepts of commitments, decommitments with the penalties and subcontractions may facilitate effective reconfiguration and replanning. Agents in competitive environments are fully autonomous and self-interested. Therefore the setting of penalties and the profit computation cannot be provided centrally. Both the costs and gain differ from agent to agent with respect to contracts already agreed and resources load. This paper proposes an acquaintance model for contracting in competitive environments and introduces possibilities of a reconfiguration in competitive environments as a means of a decommitment optimization with respect to resources load and profit maximization.

This paper presents a unified multi-agent technology for decision-making support in production planning and scheduling, manufacturing simulation and collaboration among enterprises. We distinguish intra-enterprise and extra-enterprise levels of production planning problem. Two technologies covering both levels have been developed, ExPlanTech for intra-enterprise level and ExtraPlanT for extra-enterprise level. Developed technology implementing prototypes can be used separately, be connected to other systems or together to maximize utility. The technology has been tested on industrial cases.

This article presents and discusses the potential of agent technologies in the manufacturing domain. It reports on the authors' experiences in deploying an open, Foundation for Intelligent Physical Agents-compliant agent-based solution in several industrial applications-namely, planning, simulation, and supply chain management. It primarily discuses and presents multiagent technologies' integration aspects. Besides the state-of-the-art review, the article provides a basic introduction to agent-based systems and lists requirements an application needs to be well suited to an agent-based solution. The articles' key contribution is its presentation of the ExPlanTech multiagent framework and technological architecture. The authors demonstrate the framework's general applicability through several use cases and in pivotal applications.

Testing on real equipment is very expensive. Simulation of manufacturing processes helps find out best possible configuration of the production process even if the real equipment doesn't exist. Extension or reconfiguration of the existing processes can be tested and evaluated before investment takes place. Validation of the plans in the simulated environment can also bring significant benefits. Proposed simulation system makes use of advantages of the agent technologies such as high flexibility and modular architecture, openness and easy reconfiguration. Simulation system allows testing several configurations of production processes and locates bottlenecks or possible problems. Using different planning techniques with different configurations allows adapting the planning algorithms and finding the best plan for the appropriate configuration. All the experimental results can be analytically evaluated and used for improving production processes.

We present a unified multi-agent technology for decision making support in production planning and scheduling, manufacturing simulation in and supply chain management. The technology has been tested on several industrial cases and is used in a daily production processes of one important automobile industry supplier in the Czech Republic.

An intelligent support and automation of production planning in both small and medium enterprises as much as big manufacturers is a key for achieving fast due-dates, high degree of manufacturing flexibility, minimization of stock resources, balanced load of the manufacturing machinery, etc. in this contribution we present a jade-based multi-agent solution for intra-enterprise production planning and for extra-enterprise activities such as supply chain management.

The paper reviews the main reasons leading to utilization of distributed systems for project-oriented production planning and it introduces a family of multi-agent systems/technologies developed in the Gerstner Laboratory to achieve this goal. The entire solution consists of three generations of MAS systems: ProPlanT, ExPlanTech and ExtraPlanT. ProPlanT is presented as a general agent based planning system shell which became a basis for a MAS system to be used for production planning in Modelarna Liaz, sro. The system running in LIAZ is described in some more details.

Disaster reconstruction is very discussed problem in the modern world. Mobile robots play important role in the stage of exploration of inaccessible or dangerous places for the human rescuer. The robots are able to operate in the disaster area right after disaster faded down or directly during the disaster course. However, nowadays technology provides only direct control by human operator (wireless or hard-wired). This technology is very advanced, but dependence on human is very restrictive. So the autonomous independent robots development is quite important. The RoboCupRescue project as the software simulation is very close to this domain and the results of this project can be used for human rescue squads support and lately for real robot rescue teams control. This project main goal is to develop new algorithms and technologies for software agents' behaviors, which will simulate rescue robots in RoboCupRescue Simulation domain.

By reusing and extending the classical multi-agent production planning infrastructure the extra-enterprise technology helps to organise external business relations of an enterprise and optimize their supply chains. It is obvious that small and medium enterprises that operate in project-driven manufacturing need to share their available resources in the most optimal way. Apart from technological infrastructure that need to interoperable across the extended enterprise, this paper emphasis the role of a shared ontologies and semantic meaning of the inter-agent communication.

This paper presents work carried out within the 'ExPlanTech' project (IST-1999-20171) funded in part by the European Commission's Information Technologies Programme. The mission of the ExPlanTech technology transfer project is to introduce, customize and exploit the multi-agent production planning technology (ProPlanT multi-agent system research prototype) in two specific industrial enterprises. An agent driven service negotiations and decision process based on usage-centred knowledge about task requirements substitutes the traditional production planning activity. We introduce methodology for integration of the project-driven production planning based on agent-based engineering within the existing enterprise resource planning system.

The mission of the ExPlanTech technology transfer project is to introduce, customize and exploit the multi-agent production planning technology in two distinct industrial cases. The traditional production planning activity is substituted by agent driven service negotiations, intelligent decomposition and distributed decision-making. This paper describes a FIPA-compliant implementation of the ExPlanTech technology at the LIAZ Pattern Shop manufacturing company. We describe the structure of the agent community, types of agents, implementation of the planning strategy and its incorporation within the real production environment.

In the domain of production planning multi-agent systems there is a strong demand for extending the solution outside the borders of the single enterprise in order to meet future business requirements: (i) to manage the extra-enterprise production planning effectively, (ii) to create and reconfigure flexible dynamic virtual enterprises (e.g. collaborating business partners). The concept of extra-enterprise agents helps to facilitate secure remote access and manage the production planning processes from outside of the factory, inspect the current and the future load of particular production units, modify already running customer-project or include/invoke a new customer-project into the system remotely.

The work presented in this paper reports on extending the intra-enterprise multi-agent production planning to the extra-enterprise level. By reusing and extending the classical multi-agent production planning infrastructure the extra-enterprise technology helps to organise external business relations of an enterprise and optimize their supply chains. It is obvious that small and medium enterprises that operate in project-driven manufacturing, need to share their available resources in the most optimal way.

In the domain of production planning multi-agent systems there is a strong demand for extending the solution beyond the borders of a single enterprise in order to meet future business requirements: (i) to manage the extra-enterprise production planning effectively, (ii) to create and reconfigure flexible dynamic configuration of virtual enterprises (e.g. among collaborating business partners). The concept of extra-enterprise agents helps to facilitate secure remote access and manage the production planning processes from outside the factory, inspect the current and the future load of particular production units, modify already running customer-projects, or include/invoke a new customer-project into the system remotely

The mission of the ExPlanTech technology transfer project is to introduce, customize and exploit the multi-agent production planning technology in two distinct industrial cases. The traditional production planning activity is substituted by agent driven service negotiations, intelligent decomposition and distributed decision-making. This paper describes a FIPA-compliant implementation of the ExPlanTech technology at the LIAZ Pattern Shop manufacturing company. We describe the structure of the agent community, types of agents, implementation of the planning strategy and its incorporation within the real production environment.

The article presents the basic replanning approach for multi-agents planning systems.