Article Preview
Top1. Introduction
Planning in multiagent domains, where multiple intelligent entities (called agents) are interacting under temporal constraints, is a challenging problem. This is particularly true if the agents define some cost on their actions, and have to cooperate in order to achieve a shared-goal. Studies on temporal multiagent systems declined during these last years. However, there is still a lack of a simple and expressive formalism to model temporal multiagent systems. In this paper, we propose an efficient framework to represent non-deterministic systems, defined as a group of interacting agents. The first issue is to model, for each agent, its proper dynamics subject to explicit timing constraints and cost of actions that can eventually be uncontrollable. This paper is an extended work of (Largouet, 2016).
Temporal planning introduced with PDDL 2.1 (Fox, 2003) extends classical planning schemes with the modeling of durative actions and the expression of concurrent plans. More recently, the planner TFPOP (Kvarnström, 2011) is a fully centralized approach that combines temporal and forward-chaining planning. In TFPOP minimum and maximum duration are specified on actions. When the number of agents and interactions grows, the resulting complexity makes difficult the planning task: this is known as the state explosion problem. For the exploration of large state spaces, symbolic model-checking has been introduced and is now widely applied for the verification of real-time systems. The connection between planning and model-checking, first proposed by (Giunchiglia, 1999; Cimatti, 2003) is relatively recent and generated numerous papers on a variety of planning domains. These works have emphasized that this promising approach can tackle the problem of generating plans on nondeterministic models for extended goals. The planner MIPS (Edelkamp, 2003) implements heuristic search algorithms to solve a large number of problems including temporal constraints on actions. More recently works have proposed temporal models such as timed automata in timeline-based planning (Khatib, 2000; Cesta, 2009, 2010; Orlandini, 2011). Combining network of automata (Jezequel, 2011) or merging finite state machines (Tozicka, 2014) are proposed approaches to come up with the scalability of multiagent planning problems.
Following this idea, we propose to represent the system as a network of interacting agents, each agent being described as an extended timed automaton. To cope with the complexity of large systems, we reformulate the planning problem in terms of model-checking and controller synthesis. To model the system we chose the formalism of Priced Timed Game Automata (PTGA), an extension of timed automata (Bouyer, 2004). PTGA appears to be a simple and expressive representation of planning multiagent systems that define: non-determinism, timing constraints and costs on actions. The interaction between agents can be performed through synchronized actions. However, existing model-checking tools rely on simple representation of extended timed automata: Timed Game Automata (TGA) and Priced Timed Automata (PTA). The idea is to reformulate the PTGA description model into TGA and PTA and to combine them to answer the planning problem. Whereas time and costs are key issues, the goal is expressed using the temporal logic TCTL (Timed Computational Tree Logic).
Given this representation framework, we propose a planning algorithm, relying on the efficient and recognized tools for the model-checking and the synthesis, to answer a temporal goal. The following requirement is asked: “What is the best strategy to guide the system to a specific goal at a specific time?”. In our case, “best” means that a criterion should be minimized and this criterion is the strategy cost. We introduce a classical planning problem, the Transport Domain, distributed to the interacting agents case and extended to include temporal constraints, costs on actions and some uncontrollable actions. The idea here is not to automatically encode any PDDL domain into PTGA but to illustrate our approach with a classical well-known planning benchmark to highlight the benefit of the formalism and to show experimental results.
The paper is structured as follows. Section 2 introduces the formalism of PTGA. Section 3 presents some of the background in model-checking and controller synthesis and gives the definitions of decision rule and strategy. Section 4 describes our planning algorithm based on PTGA. Section 5 presents the Transport Domain and its adaptation to a multiagent planning problem defined as a PTGA model. Section 6 reports on experimental results while Section 7 demonstrate the interest of the approach with experiments on a real-case study in ecosystem management. Section 8 concludes the paper and gives some perspectives.