Ing. Antonín Komenda, Ph.D.

Automated planning and machine learning create a powerful combination of tools which allows us to apply general problem solving techniques to problems that are not modeled using classical planning techniques. In real-world scenarios and complex domains, creating a standardized representation is often a bottleneck as it has to be modeled by a human. That often limits the usage of planning algorithms to real-world problems. The standardized representation is also not a suitable for neural network processing and often requires further transformation. In this work, we focus on presenting three different grid representations that are well suited to model a variety of classical planning problems which can be then processed by neural networks without further modifications. We also analyze classical planning benchmarks in order to find domains that correspond to our proposed representations. Furthermore, we also show that domains that are not explicitly defined on a grid can be represented on a grid with minor modifications that are domain specific. We discuss advantages and drawbacks of our proposed representations, provide examples for many planning benchmarks and also discuss the importance of data and its structure when training neural networks for planning.

Automated planning provides a powerful general problem solving tool, however, its need for a model creates a bottleneck that can be an obstacle for using it in real-world settings. In this work we propose to use neural networks, namely Cellular Simultaneous Recurrent Networks (CSRN), to process a planning problem and provide a heuristic value estimate that can more efficiently steer the automated planning algorithms to a solution. Using this particular architecture provides us with a scale-free solution that can be used on any problem domain represented by a planar grid. We train the CSRN architecture on two benchmark domains, provide analysis of its generalizing and scaling abilities. We also integrate the trained network into a planner and compare its performance against commonly used heuristic functions.

Privacy preservation has become one of the crucial research topics in multi-agent planning. A number of techniques to preserve private information throughout the planning process have emerged. One major difficulty of such research is the comparison of properties related to privacy among such techniques. A metric allowing for comparison of such privacy preservation was introduced only recently, having a number of drawbacks such as prohibitive computational complexity. In this work we strengthen the theoretical foundations and simplify the metric in order to be practically usable. Moreover, we test the usability of the metric in an analysis of various techniques in multi-agent heuristic computation and search, determining which are the most beneficial in terms of privacy preservation. We also evaluate the techniques in terms of the classical IPC score to assess their impact on the overall planning performance. The results are somewhat surprising and show that extracting any privacy-related information even from the simplest variant of heuristic search is a very complicated task. Existing techniques such as distributed heuristic and sending only relevant states is shown to reduce the privacy leakage even more.

Automated planning for problems without an explicit model is an elusive research challenge. However, if tackled, it could provide a general approach to problems in real-world unstructured environments. There are currently two strong research directions in the area of artificial intelligence (AI), namely machine learning and symbolic AI. The former provides techniques to learn models of unstructured data but does not provide further problem solving capabilities on such models. The latter provides efficient algorithms for general problem solving, but requires a model to work with. Creating the model can itself be a bottleneck of many problem domains. Complicated problems require an explicit description that can be very costly or even impossible to create. In this paper, we propose a combination of the two areas, namely deep learning and classical planning, to form a planning system that works without a human-encoded model for variably scaled problems. The deep learning part extracts the model in the form of a transition system and a goal-distance heuristic estimator; the classical planning part uses such a model to efficiently solve the planning problem. Both networks in the planning system, we introduced, work with a problem in its graphic form and there is no need for any additional information to create the state transition system or to estimate a heuristic value. We proposed three different architectures for the heuristic estimator to compare different characteristics of well-known deep learning techniques. Besides the design of such planning systems, we provide experimental evaluation comparing the implemented techniques to classical model-based methods.

Classical planning provides models and algorithms for solving problems of finding a sequence of actions that transforms the initial state of the world into a state of the world with the desired properties. In classical planning, we assume that the solution plan entails all actors in the world and thus it can be computed centrally. In multi-agent planning, this assumption is dropped in favor of situations where there is multitude of actors with individual capabilities, goals, and objectives, called agents. In this work, we propose a novel technique for multi-agent planning which combines a state-of-the-art planner called Planning State Machine (PSM) Planner with a framework for mutli-party secure computation, Sharemind. This allows the agents to find a cooperative plan while preventing the leakage of private information in a practical and scalable way.

Potential heuristics assign a numerical value (potential) to each fact and compute the heuristic value for a given state as the sum of these potentials. A mutex is an invariant stating that a certain combination of facts cannot be part of any reachable state. In this paper, we use mutexes to improve potential heuristics in two ways. First, we show that the mutex-based disambiguations of the goal and preconditions of operators leads to a less constrained linear program yielding stronger heuristics. Second, we utilize mutexes in a construction of new optimization functions based on counting of the number of states containing certain sets of facts. The experimental evaluation shows a significant increase in the number of solved tasks.

Multi-agent planning (MAP) has recently gained traction in both planning and multi-agent system communities, especially with the focus on privacy-preserving multi-agent planning, where multiple agents plan for a common goal but with private information they do not want to disclose. Heuristic search is the dominant technique used in MAP and therefore it is not surprising that a significant attention has been paid to distributed heuristic computation, either with or without the concern for privacy. Nevertheless, most of the distributed heuristic computation approaches published so far are ad-hoc algorithms tailored for the particular heuristic. In this work we present a general, privacy-preserving, and admissible approach to distributed heuristic computation. Our approach is based on an adaptation of the technique of cost partitioning which has been successfully applied in optimal classical planning. We present the general approach, a particular implementation, and an experimental evaluation showing that the presented approach is competitive with the state of the art while having the additional benefits of generality and privacy preservation.

Similarly to classical planning, heuristics play a crucial role in Multi-Agent Planning (MAP). Especially, the question of how to compute a distributed heuristic so that the information is shared effectively has been studied widely. This question becomes even more intriguing if we aim to preserve some degree of privacy, or admissibility of the heuristic. The works published so far aimed mostly at providing an ad-hoc distribution protocol for a particular heuristic. In this work, we propose a general framework for distributing heuristic computation based on the technique of cost partitioning. This allows the agents to compute their heuristic values separately and the global heuristic value as an admissible sum. We evaluate the presented techniques in comparison to the baseline of locally computed heuristics and show that the approach based on cost partitioning improves the heuristic quality over the baseline.

Privacy-Preserving Multi-Agent Planning (PP-MAP) has recently gained the attention of the research community, resulting in a number of PP-MAP planners and theoretical works. Many such planners lack strong theoretical guarantees, thus in order to compare their abilities w.r.t. privacy, a versatile and practical metric is crucial. In this work, we propose such a metric, building on the existing theoretical work. We generalize and implement the approach in order to be applicable on real planning domains and provide an evaluation of stateof-the-art PP-MAP planners over the standard set of benchmarks. The evaluation shows that the proposed privacy leakage metric is able to provide a comparison of PP-MAP planners and reveal important properties.

Planning tasks for the distributed multi-agent planning in deterministic environments are described in highly expressive, but lifted, languages, similar to classical planning. On the one hand, these languages allow for the compact representation of exponentially large planning problems. On the other hand, the solvers using such languages need efficient grounding methods to translate the high-level description to a low-level representation using facts or atomic values. Although there exist ad-hoc implementations of the grounding for the multi-agent planning, there is no general scheme usable by all multi-agent planners. In this work, we propose such a scheme combining centralized processes of the grounding and the inference of mutex groups. Both processes are needed for the translation of planning tasks from the Multi-agent Planning Description Language (MA-PDDL) to the finite domain representation. We experimentally show a space reduction of the multi-agent finite domain representation in contrast to the binary representation on the common benchmark set.

Cooperative multi-agent planning (MAP) is a relatively recent research field that combines technologies, algorithms, and techniques developed by the Artificial Intelligence Planning and Multi-Agent Systems communities. While planning has been generally treated as a single-agent task, MAP generalizes this concept by considering multiple intelligent agents that work cooperatively to develop a course of action that satisfies the goals of the group.

Efficient allocation of charging capacity to electric vehicle (EV) users is a key prerequisite for large-scale adaption of electric vehicles. Dynamic pricing represents a flexible framework for balancing the supply and demand for limited resources. In this paper, we show how dynamic pricing can be employed for allocation of EV charging capacity. Our approach uses Markov Decision Process (MDP) to implement demand-response pricing which can take into account both revenue maximization at the side of the charging station provider and the minimization of cost of charging on the side of the EV driver. We experimentally evaluate our method on a real-world data set. We compare our dynamic pricing method with the flat rate time-of-use pricing that is used today by most paid charging stations and show significant benefits of dynamically allocating charging station capacity through dynamic pricing.

Mutex groups are defined in the context of STRIPS planning as sets of facts out of which, maximally, one can be true in any state reachable from the initial state. The importance of computing and exploiting mutex groups was repeatedly pointed out in many studies. However, the theoretical analysis of mutex groups is sparse in current literature. This work provides a complexity analysis showing that inference of mutex groups is as hard as planning itself (PSPACE-Complete) and it also shows a tight relationship between mutex groups and graph cliques. This result motivates us to propose a new type of mutex group called a fact-alternating mutex group (fam-group) of which inference is NP-Complete. Moreover, we introduce an algorithm for the inference of fam-groups based on integer linear programming that is complete with respect to the maximal fam-groups and we demonstrate how beneficial fam-groups can be in the translation of planning tasks into finite domain representation. Finally, we show that fam-groups can be used for the detection of dead- end states and we propose a simple algorithm for the pruning of operators and facts as a preprocessing step that takes advantage of the properties of fam-groups. The experimental evaluation of the pruning algorithm shows a substantial increase in a number of solved tasks in domains from the optimal deterministic track of the last two planning competitions (IPC 2011 and 2014).

Multi-agent planning using MA-STRIPS-related models is often motivated by the preservation of private information. Such a motivation is not only natural for multi-agent systems but also is one of the main reasons multi-agent planning problems cannot be solved with a centralized approach. Although the motivation is common in the literature, the formal treatment of privacy is often missing. In this article, we expand on a privacy measure based on information leakage introduced in previous work, where the leaked information is measured in terms of transition systems represented by the public part of the problem with regard to the information obtained during the planning process. Moreover, we present a general approach to computing privacy leakage of search-based multi-agent planners by utilizing search-tree reconstruction and classification of leaked superfluous information about the applicability of actions. Finally, we present an analysis of the privacy leakage of two well-known algorithms-multi-agent forward search (MAFS) and Secure-MAFS- both in general and on a particular example. The results of the analysis show that Secure-MAFS leaks less information than MAFS.

Currently the most efficient distributed multiagent planning scheme for deterministic models is based on coordination of local agents’ plans. In such a scheme, behavior of other agents is modeled using projections of their actions stripped of all private information. The planning scheme does not require any additional information, however using such can be beneficial for planning efficiency. Dependencies among the projected public actions caused by sequences of local private actions represent one particular type of such information.

With the increasing prevalence of electric vehicles (EVs), the provision of EV charging is becoming a standard commercial service. With this shift, EV charging service providers are looking for ways to make their business more profitable. Dynamic pricing is a proven technique to increase revenue in markets with time-variant, heterogeneous demand. In this paper, we propose a Markov Decision Process (MDP)-based approach to revenue-maximizing dynamic pricing for charging service providers. We implement the approach using an ensemble of policy iteration MDP solvers and evaluate it using a simulation based on real-world data. We show that our proposed method achieves significantly higher revenue than methods utilizing flat-based pricing. In addition to achieving higher revenue for charging service providers, the method also increases the efficiency of allocation measured in terms of the total utilization of the charging station.

Classical planning can solve large and real-world problems, even when multiple entities, such as robots, trucks or companies, are concerned. But when the interested parties, such as cooperating companies, are interested in maintaining their privacy while planning, classical planning cannot be used. Although, privacy is one of the crucial aspects of multi-agent planning, studies of privacy are underepresented in the literature. A strong privacy property, necessary to leak no information at all, has not been achieved by any planner in general yet. In this contribution, we propose a multiagent planner which can get arbitrarily close to the general strong privacy preserving planner for the price of decreased planning efficiency. The strong privacy assurances are under computational tractability assumptions commonly used in secure computation research.

Multi-agent planning using MA-STRIPS-related models is often motivated by the preservation of private information. Such motivation is not only natural for multi-agent systems, but it is one of the main reasons, why multi-agent planning (MAP) problems cannot be solved centrally. In this paper, we analyze privacy-preserving multi-agent planning (PP-MAP) from the perspective of secure multiparty computation (MPC). We discuss the concept of strong privacy and its implications and present two variants of a novel planner, provably strong privacy-preserving in general. As the main contribution, we formulate the limits of strong privacy-preserving planning in the terms of privacy, completeness and efficiency and show that, for a wide class of planning algorithms, all three properties are not achievable at once. Moreover, we provide a restricted variant of strong privacy based on equivalence classes of planning problems and show that an efficient, complete and strong privacy-preserving planner exists for such restriction.

Real world applications often require cooperation of multiple independent entities. Classical planning is a well established technique solving various challenging problems such as logistic planning, factory process planning, military mission planning and high-level planning for robots. Multi-agent planning aims at solving similar problems in the presence of multiple independent entities (agents). Even though such entities might want to cooperate in order to fulfill a common goal, they may want to keep their internal information and processes private. In such case, we talk about privacy-preserving multi-agent planning.

As a part of the workshop on Distributed and Multiagent Planning (DMAP) at the International Conference on Automated Planning and Scheduling (ICAPS) 2015, we have organized a competition in distributed and multiagent planning. The main aims of the competition were to consolidate the planners in terms of input format; to promote development of multiagent planners both inside and outside of the multiagent research community; and to provide a proof-of-concept of a potential future multiagent planning track of the International Planning Competition (IPC). In this paper we summarize course and highlights of the competition.

Similarly to classical planning, heuristics play a crucial role in most multi-agent and privacy-preserving multi-agent planning systems. It has been shown that distributed heuristics may crucially improve the search guidance, but are costly in terms of communication and computation time and are often a source of privacy concerns. One solution is to compute a heuristic additively, in the sense that each agent can compute its part of the heuristic independently and obtain a complete heuristic estimate by summing up the individual parts. In this preliminary paper, we propose a technique based on cost-partitioning allowing us to use any heuristic in such a way.

Unmanned aerial vehicles (UAVs) are suited to various remote sensing missions, such as measuring air quality. The conventional method of UAV control is by human operators. Such an approach is limited by the ability of cooperation among the operators controlling larger fleets of UAVs in a shared area. The remedy for this is to increase autonomy of the UAVs in planning their trajectories by considering other UAVs and their plans. To provide such improvement in autonomy, we need better algorithms for generating alternative trajectory variants that the UAV coordination algorithms can utilize. In this article, we define a novel family of multi-UAV sensing problems, solving task allocation of huge number of tasks (tens of thousands) to a group of configurable UAVs with non-zero weight of equipped sensors (comprising the air quality measurement as well) together with two base-line solvers. To solve the problem efficiently, we use an algorithm for diverse trajectory generation and integrate it with a solver for the multi-UAV coordination problem. Finally, we experimentally evaluate the multi-UAV sensing problem solver. The evaluation is done on synthetic and real-world-inspired benchmarks in a multi-UAV simulator. Results show that diverse planning is a valuable method for remote sensing applications containing multiple UAVs.

Multiagent planning addresses the problem of coordinated sequential decision making of a team of cooperative agents. One possible approach to multiagent planning, which proved to be very efficient in practice, is to find an acceptable public plan. The approach works in two stages. At first, a public plan acceptable to all the involved agents is computed. Then, in the second stage, the public solution is extended to a global solution by filling in internal information by every agent. In the recently proposed distributed multiagent planner, the winner of the Competition of Distributed Multiagent Planners (CoDMAP 2015), this principle was utilized, however with unnecessary use of combination of both public and internal information for extension of the public solution. In this work, we improve the planning algorithm by enhancements of the global solution reconstruction phase. We propose a new method of global solution reconstruction which increases efficiency by restriction to internal information. Additionally, we employ reduction techniques downsizing the input planning problem. Finally, we experimentally evaluate the resulting planner and prove its superiority when compared to the previous approach.

Distributed heuristic search is a well established technique for multi-agent planning. It has been shown that distributed heuristics may crucially improve the search guidance, but are costly in terms of communication and computation time. One solution is to compute a heuristic additively, in the sense that each agent can compute its part of the heuristic independently and obtain a complete heuristic estimate by summing up the individual parts. In this paper, we show that the recently published potential heuristic is a good candidate for such heuristic, moreover admissible. We also demonstrate how the multi-agent distributed A∗ search can be modified in order to benefit from such additive heuristic. The modified search equipped with a distributed potential heuristic outperforms the state of the art.

Coordinated sequential decision making of a team of cooperative agents can be described by principles of multiagent planning. Provided that the mechanics of the environment the agents act in is described as a deterministic transitions system, an appropriate planning model is MA-Strips. Multiagent planning modeled as MA-Strips prescribes exactly what information has to be kept private and which information can be communicated in order to coordinate toward shared or individual goals. We propose a multiagent planning approach which combines compilation for a classical state-of-the-art planner together with a compact representation of local plans in the form of finite-state machines. Proving soundness and completeness of the approach, the planner efficiency is further boosted up using distributed delete-relaxation heuristics and using an approximative local plan analysis. We experimentally evaluate applicability of our approach in full privacy setting where only public information can be communicated. We analyze properties of standard multiagent benchmarks from the perspective of classification of private and public information. We show that our approach can be used with different privacy settings and that it outperforms state-of-the-art planners designed directly for particular privacy classification.

Multi-agent planning using MA-STRIPS-related models is often motivated by the preservation of private information. Such motivation is not only natural for multi-agent systems, but is one of the main reasons, why multi-agent planning (MAP) problems cannot be solved centrally. Although the motivation is common in the literature, formal treatment of privacy is mostly missing. An exception is a definition of two extreme concepts, weak and strong privacy. In this paper, we first analyze privacy leakage in the terms of secure Multi-Party Computation and Quantitative Information Flow. Then, we follow by analyzing privacy leakage of the most common MAP paradigms. Finally, we propose a new theoretical class of secure MAP algorithms and show how the existing techniques can be modified in order to fall in the proposed class.

Reducing accidental complexity in planning problems is a well-established method for increasing efficiency of classical planning. Removal of superfluous facts and actions, and problem transformation by recursive macro actions are representatives of such methods working directly on input planning problems. Despite of its general applicability and thorough theoretical analysis, there is only a sparse amount of experimental results. In this paper, we adopt selected reduction methods from literature and amend them with a generalization-based reduction scheme and auxiliary reductions. We show that all presented reductions are polynomial in time to the size of an input problem. All reductions applied in a recursive manner produce only safe (solution preserving) abstractions of the problem, and they can implicitly represent exponentially long plans in a compact form. Experimentally, we validate efficiency of the presented reductions on the IPC benchmark set and show average 24% reduction over all problems. Additionally, we experimentally analyze the trade-off between increase of coverage and decrease of the plan quality

Problems of cooperative multiagent planning in deterministic environments can be efficiently solved both by distributed search or coordination of local plans. In the current coordination approaches, behavior of other agents is modeled as public external projections of their actions. The agent does not require any additional information from the other agents, that is the planning process ignores any dependencies of the projected actions possibly caused by sequences of other agents’ private actions. In this work, we formally define several types of internal dependencies of multiagent planning problems and provide an algorithmic approach how to extract the internally dependent actions during multiagent planning. We show how to take an advantage of the computed dependencies by means of reducing the multiagent planning problems. We experimentally show strong reduction of majority of standard multiagent benchmarks and nearly doubling of solved problems in comparison to a variant of a planne.

Multi-agent planning using MA-STRIPS-related models is often motivated by the preservation of private information. Such motivation is not only natural for multi-agent systems, but is one of the main reasons, why multi-agent planning problems cannot be solved centrally. Although the motivation is common in the literature, formal treatment of privacy is mostly missing. An exception is a definition of two extreme concepts, weak and strong privacy. In this paper, we first analyze privacy leakage in the terms of secure Multi-Party Computation and Quantitative Information Flow. Then, we follow by analyzing privacy leakage of the most common MAP paradigms. Finally, we propose a new theoretical class of secure MAP algorithms and show how the existing techniques can be modified in order to fall in the proposed class.

Multi-agent planning (MAP) is often motivated by the preservation of private information. Such motivation is not only natural for multi-agent systems, but is one of the main reasons, why MAP problems cannot be solved centrally. In this paper, we analyze privacy leakage of the most common MAP paradigms. Then, we propose a new class SECMAP of secure MAP algorithms and show how the existing techniques can be modified to fall in the proposed class.

This article reports on the first international Competition of Distributed and Multiagent Planners (CoDMAP). The competition focused on cooperative domain-independent planners compatible with a minimal multiagent extension of the classical planning model. The motivations for the competition were manifold: to standardize the problem description language with a common set of benchmarks, to promote development of multiagent planners both inside and outside of the multiagent research community, and to serve as a prototype for future multiagent planning competitions. The article provides an overview of cooperative multiagent planning, describes a novel variant of standardized input language for encoding mutliagent planning problems and summarizes the key points of organization, competing planners and results of the competition.

Heuristics are a crucial component in modem planning systems. In optimal multiagent planning the state of the art is to compute the heuristic locally using only information available to a single agent. This approach has a major deficiency as the local shortest path can arbitrarily underestimate the true shortest path cost in the global problem. As a solution, we propose a distributed version of a state-of-the-art LM-Cut heuristic. We show that our distributed algorithm provides estimates provably equal to estimates of the centralized version computed on the global problem. We also evaluate the algorithm experimentally and show that on a number of domains, the distributed algorithm can significantly improve performance of a multiagent planner. Copyright © 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Distributed computation of heuristic functions has recently become a hot topic in multiagent planning. One of the classical heuristics most often adapted for distribution is the FF heuristic. In this paper we compare two approaches used to distribute the FF heuristic, which were previously incomparable, as each was implemented in a different planning scheme, a greedy best-first search and a forward-chaining partial order planner.

As a part of the 2015 DMAP workshop at ICAPS, we are organizing a semi-official experimental competition in multi-agent planning. The main aims of the competition are to consolidate the planners in terms of input format and formalism, so they can be better compared and to provide a proof-of-concept of a potential future IPC track on multi-agent planning. Another aim is to bring closer the classical and multi-agent planning communities in terms of comparable benchmarks and techniques. In this paper we explain our decisions, describe the formalism and language used and propose how the IPC track might look like. The success (or failure) of the competition will show the potential suitability of such a dedicated IPC track.

Coordinated sequential decision making of a team of cooperative agents is described by principles of multiagent planning. In this work, we extend the MA-Strips formalism with the notion of extensibility and reuse a well-known initiator–participants scheme for agent negotiation. A multiagent extension of the Generate-And-Test principle is used to distributively search for a coordinated multiagent plan. The generate part uses a novel plan quality estimation technique based on metrics often used in the field of diverse planning. The test part builds upon planning with landmark actions by compilation to classic planning. We designed a new multiagent planning domain which illustrates the basic properties of the proposed multiagent planning approach. Finally, our approach was experimentally evaluated on four classic IPC benchmark domains modified for multiagent settings. The results show (1) which combination of plan quality estimation and (2) which diversity metrics provide the best planning efficiency.

In this short paper we present the MADLA (Multi-agent Distributed and Local Asynchronous) Planner which entered the centralized track of the Competition of Distributed and Multi-Agent Planners (CoDMAP). The planner combines two variants of FF heuristic, a projected (local) variant and a distributed variant, in a multi-heuristic state-space search. The main idea of the search is that while waiting for the computation of the distributed heuristic, the local one asynchronously continues the search.

In this paper, we present a brand new multi-agent planner called MAPlan. The planner implements state space heuristic search on factorized problems retrieved from either unfactored or factored version of MA-PDDL files. It can run both in a multi-thread and distributed configuration with a communication over network or within a process. This paper briefly describes the details of the MAPlan configurations used in the 2015 CoDMAP competition.

Deterministic domain-independent multiagent planning is an approach to coordination of cooperative agents with joint goals. Provided that the agents act in an uncertain and dynamic environment, such plans can fail. The straightforward approach to recover from such situations is to compute a new plan from scratch, that is to replan. Even though, in a worst case, plan repair or plan re-use does not yield an advantage over replanning from scratch, there is a sound evidence from practical use that approaches trying to repair the failed original plan can outperform replanning in selected problems. One of the possible plan repairing techniques is based on preservation of fragments of the older plans. This work theoretically analyses complexity of plan repairing approaches based on preservation of fragments of the original plan and experimentally studies three practical aspects affecting its efficiency in various multiagent settings. We focus both on the computational, as well as the communication efficiency of plan repair in comparison to replanning from scratch and we report on the influence of the following properties on the efficiency of plan repair: (1)~the number of involved agents in the plan repairing process, (2)~inter-dependencies among the repaired actions, and finally (3)~particular modes of re-use of the older plans.

Multiagent planning is a coordination technique used for deliberative acting of a team of agents. One of vital planning techniques uses declarative description of agents’ plans based on Finite State Machines and their later coordination by intersection of such machines with successive verification of the resulting joint plans. In this work, we firstly propose to use projections of agents’ actions directly for multiagent planning based on iterative building of a coordinated multiagent plan. Secondly, we describe integration of the static analysis provided by process calculi type systems for approximate verification of exchanged local plans. Finally, we compare our approach with current state-of-the-art planner on an extensive benchmark set.

Narrative planning, as an approach to automated storytelling, uses techniques of automated planning to emulate intelligent behavior of story characters, which helps to generate believable tales. Following the idea of interactive storytelling, where the characters are represented by agents, we propose to use multiagent planning by means of plan merging to generate believable stories. As the story characters represent people, we bound rationality of the planning agents by the concept of a Cognitive Hierarchy, which we use on decisions described as plans. Not only the Cognitive Hierarchy improves believability of the characters, it also increases efficiency of the planning process as sub-optimal solutions might be used. With help of a classical planner and novel compilation for narrative multiagent planning, we experimentally show the efficiency is comparable with the state of the art. Moreover, we show how adjustment of character’s cognitive level produces believable simple-minded behavior.

Agents planning under STRIPS-related model using separation of facts and actions to private and public can model behavior of other agents as public external pro- jections of their actions. In the most simplistic case, the agent does not require any additional information from the other agents, that is the planning process ignores any dependencies of the projected actions possibly caused by sequences of other agents’ private actions. In this work, we formally define several types of in- ternally dependencies of multiagent planning problems and provide an algorithmic approach how to extract the internally dependent actions during multiagent plan- ning. We show how to take an advantage of computed dependencies in multiagent planning. Additionally, we analyze the standard benchmarks used for mutliagent planning and present overview of various sub-types of internal dependencies of public actions in particular planning domains.

Interruptible pure exploration in multi-armed bandits (MABs) is a key component of Monte-Carlo tree search algorithms for sequential decision problems. We introduce Discriminative Bucketing (DB), a novel family of strategies for pure exploration in MABs, which allows for adapting recent advances in non-interruptible strategies to the interruptible setting, while guaranteeing exponential-rate performance improvement over time. Our experimental evaluation demonstrates that the corresponding instances of DB favorably compete both with the currently popular strategies UCB1 and ε-Greedy, as well as with the conservative uniform sampling.

One possible approach to domain independent multiagent planning (DMAP) is to equip all the agents with information about public actions of other agents. This allows every agent to plan public actions for other agents. This approach can be used together with planning state machines (PSM) which provide a compact representation of sets of plans. In a PSM-based planner, every agent keeps generating plans and stores the generated plans in a PSM . This process continues until a plan acceptable for all the agents is found. We describe PSM-based planners submitted to the Competition of Distributed and Multiagent Planners (CoDMAP) held at DMAP Workshop of ICAPS 2015. We describe two configurations of a PSM-based planner which differ in the set of used features, and in the amount of private information revealed to other agents. Both of these two configurations can be used both in a distributed and a centralized setting. Hence we describe altogether four P SM -based planners submitted to the competition.

Multiagent planning is a coordination technique used for deliberative acting of a team of agents. One of vital planning techniques uses declarative description of agents’ plans based on Finite State Machines and their later coordination by intersection of such machines with successive verification of the resulting joint plans. In this work, we firstly introduce a method of multiagent planning which makes use of projections of other agent actions in order to iteratively search for a skeleton of a multiagent plan. Secondly, we describe integration of the static analysis provided by process calculi type systems for approximate verification of exchanged local plans. Furthermore, we introduce an alternative method to accomplish the above verification by a classical planner. Finally, we compare our approach with current state-of-the-art planner on an extensive benchmark set.

Achieving joint objectives in distributed domain-independent planning problems by teams of cooperative agents requires significant coordination and communication efforts. For systems facing a plan failure in a dynamic environment, arguably, attempts to repair the failed plan in general, and especially in the worst-case scenarios, do not straightforwardly bring any benefit in terms of time complexity. However, in multi-agent settings, the communication complexity might be of a much higher importance, possibly a high communication overhead might be even prohibitive in certain domains. We hypothesize that in decentralized systems, where frequent coordination is required to achieve joint objectives, attempts to repair failed multi-agent plans should lead to lower communication overhead than replanning from scratch. Here, we formally introduce the multi-agent plan repair problem. Building upon the formal treatment, we present the core hypothesis underlying our work and subsequently describe three algorithms for multi-agent plan repair reducing the problem to specialized instances of the multi-agent planning problem. Finally, we present an experimental validation, results of which confirm the core hypothesis of the paper. Our rigorous treatment of the problem and experimental results pave the way for both further analytical, as well algorithmic investigations of the problem.

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.

Deterministic domain-independent planning techniques for multiagent systems stem from principles of classical planning. Three most recently studied approaches comprise (i) DisCSP+Planning utilizing Distributed Constraint Satisfaction Problem solving for coordination of the agents and individual planning using local search, (ii) multiagent adaptation of A* with local heuristics and (iii) distribution of the GraphPlan approach based on merging of planning graphs. In this work, we summarize the principles of these three approaches and describe a novel implementation and optimization of the multiagent GraphPlan approach. We experimentally validate the influence of parametrization of the inner extraction phase of individual plans and compare the best results with the former two multiagent planning techniques.

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.

Use of heuristics in search-based domain-independent deterministic multiagent planning is as important as in classical planning. In this work we propose a formal and an algorithmic adaptation of a well-known heuristic Fast-Forward into multiagent planning. Such treatment is important as it solves challenges in decentralization of this and other heuristics based on relaxation of the original planning problem. Such decentralization enables global heuristic estimates to be computed without exposing local information. Additionally, since Fast-Forward heuristic is based on relaxed planning, we propose a multiagent approach for building factored relaxed planning graphs among the agents. We sketch proofs that the results of the distributed version of the algorithm gives the same results as the centralized version. Finally, we experimentally validate dierent distribution strategies of the heuristic estimate.

Deterministic domain-independent multi-agent planning is an approach to coordination of cooperative agents with joint goals. Provided that the agents act in an imperfect environment, such plans can fail. The traightforward approach to recover from such situations is to compute a new plan from scratch, that is to replan. Even though, in a worst case, plan repair or plan re-use does not yield an advantage over replanning from scratch, there is a sound evidence from practical use that approaches trying to repair the failed original plan can outperform replanning in selected problems. One of the possible plan repairing techniques is based on preservation of the older plans. This work experimentally studies three aspects affecting efficiency of plan repairing approaches based on preservation of fragments of the original plan in a multi-agent setting. We focus both on the computational, as well as the communication efficiency of plan repair in comparison to replanning from scratch. In our study, we report on the influence of the following issues on the efficiency of plan repair: 1) the number of involved agents in the plan repairing process, 2) interdependencies among the repaired actions, and finally 3) particular modes of re-use of the older plans.

Distributed multi-agent planning presents several challenges as yet not addressed by existing techniques. First, the complexity of planning scales non-linearly as a function of the number of agents. Second, most multi-agent planning approaches assume perfect and reliable communications are available to coordinate actions across the distributed agents. Third, even given reliable communications, agents may not be able to converge on a reliable overall plan for the group without resorting to computationally expensive (and communication intensive) problem centralization. This paper develops a formalization of the multi-agent planning problem and a novel three-phase approach which generates plans, solves them using the approximate, robust Max-Sum DCOP algorithm and then uses plan repair to address these three points. We provide sketches of the proofs of these claims as well as empirical results, for a restricted version of the Crane-Robot domain, of better scalability than existing approaches, and robust performance with up to 90% message loss.

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.

AgentPolis is a fully agent-based platform for modeling multi-modal transportation systems. It comprises a high-performance discrete-event simulation core, a cohesive set of high-level abstractions for building extensible agent-based models and a library of predefined components frequently used in transportation and mobility models. Together with a suite of supporting tools, textsc{AgentPolis} enables rapid prototyping and execution of data-driven simulations of a wide range of mobility and transportation phenomena. We illustrate the capabilities of the platform on a model of fare inspection in public transportation networks.

Achieving joint objectives by teams of cooperative planning agents requires significant coordination and communication efforts. For a single-agent system facing a plan failure in a dynamic environment, arguably, attempts to repair the failed plan in general do not straightforwardly bring any benefit in terms of time complexity. However, in multi-agent settings the communication complexity might be of a much higher importance, possibly a high communication overhead might be even prohibitive in certain domains. We hypothesize that in decentralized systems, where coordination is enforced to achieve joint objectives, attempts to repair failed multi-agent plans should lead to lower communication overhead than replanning from scratch.

The development of control algorithms for tactical missions is being impeded by the significant gap between the way the artificial intelligence (A.I.) algorithms have been designed and validated and the way the robotic applications for (high-fidelity simulations) of tactical missions are being developed. On the one hand, we have low-level robotic simulators (or even robotic field testing). On the other hand, we have synthetic - usually mathematically defined - environments used for the design and formal testing of A.I. algorithms, e.g. randomly generated problem instances, synthetic graph structures, logical structures, regular grids, and similar. In this work, we are proposing a development process and a related software toolkit helping to narrow this gap. We use the simulation-aided development approach and tailor it towards the domain of tactical missions. The process is demonstrated on a specific application scenario, employing a general software toolkit Alite to glue together and adapt a number of A.I. algorithms, originally designed as highly abstract.

With scaling of multi-robot teams deployed in military operations, there is a need to boost autonomy of individual, as well as team behaviors. We developed a feature-rich simulation testbed for experimental evaluation of multi-agent coordination mechanisms applicable in tactical military operations in urban warfare. In particular, we investigated and implemented four approaches including multi-agent mission planning and plan repair, reactive planning for teamwork, patrolling of mobile targets, and tracking of smart targets. Besides the live-system demonstrator, we aim to showcase a scenario engaging a human in a pursuit-evasion game against the algorithms we implemented.

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.

Coordinated multi-agent planning and acting in dynamic and uncertain environments poses a number of challenges. We present a conceptual framework formalising the problem of multi-agent planning and subsequent plan repair. As a first step towards tackling the problem of multi-agent plan repair, we introduce a sequel of three algorithms. As a preliminary experiment, we evaluate and compare one of them with re-planning from scratch in a synthetic domain of multi-robot cranes and show computational and communication gains of the plan repairing technique.

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.

Considering Unmanned Autonomous Vehicles (UAVs) the planning tasks mainly consist of finding paths between given waypoints with respect to given constraints. In this paper we developed a path planning system for flying UAVs (VTOLs and CTOLs) built upon Hexagonal grids which also supports simple dynamics (handling with speed). The planning system is additionally supported by a trajectory smoothing mechanism based on a dynamics model of a helicopter. The model can be also used for the simulation of the helicopter movement.

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.

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.

The problem of controlling entities in heterogeneous distributed environment is crucial for many domains. Classical centralized methods depend on one central planning system. This approach faces various problems. One problem is enormous demand for performance of central planning system. The other problem is the need for real-time re-planning based on dynamically changing environment and conditions in the time. In distributed methods of planning each entity plans it's own plan. Cooperation and heading to common goals is done by negotiating methods. Presented approach is based on newly designed multi-layer planning architecture and all plans are described in the form of social commitments, substituting plan actions.

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.

In this paper a synthetic mobility model which represents behavior and movement pattern of heterogeneous units in disaster relief and battlefield scenarios is proposed. These operations usually take place in environment without pre-existing communication infrastructure and units thus have to be connected by wireless communication network. Units cooperate to fulfil common tasks and communication network has to serve high amount of communication requests, especially data, voice and video stream transmissions. To verify features of topology control, routing and interaction protocols software simulations are usually used, because of their scalability, repeatability and speed. Behavior of all these protocols relies on the mobility model of the network nodes, which has to resemble real-life movement pattern. Proposed mobility model is goal-driven and provides support for various types of units, group mobility and realistic environment model with obstacles.

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.

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.

This contribution presents a distributed, multi-layer collision avoidance architecture supporting efficient utilization of air space shared by several autonomous aerial vehicles. Presented multi-layer architecture is based on deliberative deployment of several collision avoidance methods by the aircraft at the same time. Both cooperative and non-cooperative collision avoidance methods are presented in the paper. The robustness of the architecture is justified by means of experimental validation of multi-agent simulation.