This paper proposes FMAP (Forward Multi-Agent Planning), a fully-distributed multi-agent planning method that integrates planning and coordination. Although FMAP is specifically aimed at solving problems that require cooperation among agents, the flexibility of the domain-independent planning model allows FMAP to tackle multi-agent planning tasks of any type. In FMAP, agents jointly explore the plan space by building up refinement plans through a complete and flexible forward-chaining partial-order planner. The search is guided by @math , a novel heuristic function that is based on the concepts of Domain Transition Graph and frontier state and is optimized to evaluate plans in distributed environments. Agents in FMAP apply an advanced privacy model that allows them to adequately keep private information while communicating only the data of the refinement plans that is relevant to each of the participating agents. Experimental results show that FMAP is a general-purpose approach that efficiently solves tightly-coupled domains that have specialized agents and cooperative goals as well as loosely-coupled problems. Specifically, the empirical evaluation shows that FMAP outperforms current MAP systems at solving complex planning tasks that are adapted from the International Planning Competition benchmarks.
In the literature, there are two main approaches for solving MAP tasks like the one described in Example . MAP involves using an intermediary agent that has complete knowledge of the task. The or decentralized approach spreads the planning responsability among agents, which are in charge of interacting with each other to coordinate their local solutions, if necessary @cite_3 @cite_12 . The adoption of a centralized approach is aimed at improving the planner performance by taking advantage of the inherent structure of the MAP tasks @cite_8 @cite_15 . Centralized approaches assume a single planning entity that has complete knowledge of the task, which is rather unrealistic if the parties involved in the task have sensitive private information that they are not willing to disclose @cite_0 . In Example , the three agents involved in the task want to protect the information regarding their internal processes and business strategies, so a centralized setting is not an acceptable solution.
@cite_8 @cite_3 @cite_0 @cite_15 @cite_12
1541379879 2078234787 1982485071 2099752828 2042213761
Partially ordered plan structures are highly suitable for centralized multi-agent planning, where plans should be minimally constrained in terms of precedence between actions performed by different agents. In many cases, however, any given agent will perform its own actions in strict sequence. We take advantage of this fact to develop a hybrid of temporal partial order planning and forward-chaining planning. A sequence of actions is constructed for each agent and linked to other agents' actions by a partially ordered precedence relation as required. When agents are not too tightly coupled, this structure enables the generation of partial but strong information about the state at the end of each agent's action sequence. Such state information can be effectively exploited during search. A prototype planner within this framework has been implemented, using precondition control formulas to guide the search process. A common assumption made in multi-robot research is the connectedness of the underlying network. Although this seems a valid assumption for static networks, it is not realistic for mobile robotic networks, where communication between robots usually is distance dependent. Motivated by this fact, we explicitly consider the communication limitations. This paper extends the LFIP based exploration framework previously developed by (Cogn. Comput. doi: 10.1007 s12559-012-9142-7 , 2012), to address the Multi-Agent Territory Exploration (MATE-n k ) task under severe communication constraints. In MATE-n k task agents have to explore their environment to find and visit n checkpoints, which only count as "visited" when k agents are present at the same time. In its simplest form, the architecture consists of two layers: an "Exploration layer" consisting of a selection of future locations for the team for further exploring the environment, and "Exploration and CheckpointVisit layer", consisting of visiting the detected checkpoints while continuing the exploration task. The connectivity maintenance objective is achieved via two ways: (1) The first layer employs a leader-follower concept, where a communication zone is constructed by the leader using a distance transforms method, and (2) In the second layer we make use of a graph theory for characterizing the communication, which employs the adjacency and Laplacian matrices of the graph and their spectral properties. The proposed approach has been implemented and evaluated in several simulated environments and with varying team sizes and communication ranges. Throughout the paper, our conclusions are corroborated by the results from extensive simulations. Distributed or multi-agent planning extends classical AI planning to domains where several agents can plan and act together. There exist many recent developments in this discipline that range over different approaches for distributed planning algorithms, distributed plan execution processes or communication protocols among agents. One of the key issues about distributed planning is that it is the most appropriate way to tackle certain kind of planning problems, specially those where a centralized solving is unfeasible. In this paper we present a new planning framework aimed at solving planning problems in inherently distributed domains where agents have a collection of private data which cannot share with other agents. However, collaboration is required since agents are unable to accomplish its own tasks alone or, at least, can accomplish its tasks better when working with others. Our proposal motivates a new planning scheme based on a distributed heuristic search and a constraint programming resolution process. Many real-world planning domains, including those used in common benchmark problems, are based on multiagent scenarios. It has long been recognised that breaking down such problems into sub-problems for individual agents may help reduce overall planning complexity. This kind of approach is especially effective in domains where interaction between agents is limited. In this paper we present a fully centralised, offline, sequential, total-order planning algorithm for solving classical planning problems based on this idea. This algorithm consists of an automated decomposition process and a heuristic search method designed specifically for decomposed domains. The decomposition method is part of a preprocessing step and can be used to determine the "multiagent nature" of a planning problem prior to actual plan search. The heuristic search strategy is shown to effectively exploit any decompositions that are found and performs significantly better than current approaches on loosely coupled domains. Unorganized traffic is a generalized form of travel wherein vehicles do not adhere to any predefined lanes and can travel in-between lanes. Such travel is visible in a number of countries e.g. India, wherein it enables a higher traffic bandwidth, more overtaking and more efficient travel. These advantages are visible when the vehicles vary considerably in size and speed, in the absence of which the predefined lanes are near-optimal. Motion planning for multiple autonomous vehicles in unorganized traffic deals with deciding on the manner in which every vehicle travels, ensuring no collision either with each other or with static obstacles. In this paper the notion of predefined lanes is generalized to model unorganized travel for the purpose of planning vehicles travel. A uniform cost search is used for finding the optimal motion strategy of a vehicle, amidst the known travel plans of the other vehicles. The aim is to maximize the separation between the vehicles and static obstacles. The search is responsible for defining an optimal lane distribution among vehicles in the planning scenario. Clothoid curves are used for maintaining a lane or changing lanes. Experiments are performed by simulation over a set of challenging scenarios with a complex grid of obstacles. Additionally behaviours of overtaking, waiting for a vehicle to cross and following another vehicle are exhibited.