A Non-cooperative Game-Theoretic Approach for Conflict Resolution in Multi-agent Planning
- PDF / 2,049,115 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 92 Downloads / 163 Views
A Non‑cooperative Game‑Theoretic Approach for Conflict Resolution in Multi‑agent Planning Jaume Jordán1 · Alejandro Torreño1 · Mathijs de Weerdt2 · Eva Onaindia1
© Springer Nature B.V. 2020
Abstract This paper presents FENOCOP, a game-theoretic approach for solving non-cooperative planning problems that involve a set of self-interested agents. Each agent wants to execute its own plan in a shared environment but the plans may be rendered infeasible by the appearance of potential conflicts; agents are willing to coordinate their plans in order to avoid conflicts during a joint execution. In order to attain a conflict-free combination of plans, agents must postpone the execution of some of their actions, which negatively affects their individual utilities. FENOCOP is a two-level game approach: the General Game selects a Nash equilibrium among several combinations of plans, and the Scheduling Game generates, for a combination of plans, an executable outcome by introducing delays in the agents’ plans. For the Scheduling Game, we developed two algorithms that return a Pareto optimal and fair equilibrium from which no agent would be willing to deviate. Keywords Planning · Multi-agent planning · Game theory · Nash equilibrium · Pareto optimal · Fairness
* Jaume Jordán [email protected] Alejandro Torreño [email protected] Mathijs de Weerdt [email protected] Eva Onaindia [email protected] 1
Institut Valencià d’Investigació en Intel·ligència Artificial (VRAIN), Universitat Politècnica de València, Camino de Vera, s/n, 46022 Valencia, Spain
2
EEMCS, Algorithmics, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands
13
Vol.:(0123456789)
J. Jordán et al.
1 Introduction Planning is the ability of selecting the appropriate action, among a set of alternatives, in a particular situation considering the conditions of the world state, the knowledge of the environment, the impact of the effects of the action, and the extent to which the decision helps in finding a solution for the planning task. The singleagent planning problem is conceived as a search process by which a single entity synthesizes a set of actions (plan) to reach a goal from an initial situation (Ghallab et al. 2004). There exists a large variety of planners, many of which have participated in the different editions of the International Planning Competition (IPC)1 event held to date. While the first IPCs aimed at evaluating the performance of solvers in deterministic planning, the most recent editions have extended the competition to temporal planning and probabilistic planning. Planning with multiple agents involves coordinating planning, control and execution activities. In general, Multi-Agent Planning (MAP) deals with the problem of automated planning in domains where multiple agents plan and act together in a shared environment (Weerdt and Clement 2009; Nguyen and Katarzyniak 2009). Motivated by the growing research in MAP, the first Competition of Distributed and Multi-Agent Planners (CoDMAP) was held in 2
Data Loading...
