Introduction. Automated planning is a central area of Arti cial Intelligence which aims to design a powerful deliberation layer for autonomous intelligent systems. Autonomy of intelligent systems doesn't concern only planning and deliberation but also acting. These two aspects are not completely disjoint: actors may deliberate or plan both before and during acting in order to perform intelligent executions, and deliberation may be strictly in uenced by acting details ([1]). The gap between planning and execution is one of the main problems to face in building an autonomous system and in order to successfully do it, planning should capture important features of real world domains ([2]). In particular, when problems involve teams of (possibly heterogeneous) agents which must cooperate, relevant features to take into account are cooperation, consumable resources, continuous numeric change, as well as concurrency, time and temporal constraints. In recent years, automatic planning languages have been extended with primitives allowing to express numerical and temporal aspects of problems (e.g. PDDL 2.1 and PDDL 2.2 ([3] and [4])). In this way, relevant aspects for execution can be taken into account already at planning time. Many alternative approaches to action-based planning have been developed. In particular timeline-based approaches (e.g. [5], [6] or the mission planning frameworks [7], [8]) or MILP approaches (e.g. [9], [10]). De ning the problem. In this work we aim at showing how complex realworld multi-agent1 problems involving consumable resources, continuous numeric change, time and multi-agent coordination can be faced with action-based approaches such as numerical and temporal planning by employing state-of-art general purpose planners. We developed a complex software architecture oriented to a centralized o line planning system. This approach to multi-agent planning is justi ed by the many interactions required among agents, by the expensive coordination activities in heterogeneous teams and by optimization reasons (i.e. maximizing the number of tasks assigned to the agents and minimizing the number of agents employed). These factors make more appropriate a centralized approach than a distributed one. However, we left the low-level controls (e.g. sensor pointing, 1 We focused our attention on multi-UAV mission, leveraging the experience and knowledge acquired on UAVs (Unmanned Aerial Vehicles), and in particular on MALE (Medium Altitude Long Endurance) and MAME (Medium Altitude Medium Endurance) UAVs, by participating to industrial research project SMAT [11], coordinated by Alenia Aermacchi. However the solutions found can be easily adapted for other robotic domains and the results that can be achieved are similar.
agents' movements, etc.) to single agents which have speci c on-line acting and
deliberative capabilities (intelligent monitoring, re-planning or continual
planning, [
We addressed a class of real-world aerospace planning problems involving teams of heterogeneous UAVs whose objective is to observe a set of targets (POINT-targets or LOC-target, i.e. polygonal chains de ned by a sequence of vertices, such as portion of a river or of a motorway). Targets observation must meet a series of user requirements which specify the type of sensor to use and temporal constraints. UAVs con guration depends on logistic information which express both the suite of sensors and the temporal windows of availability of the vehicles. Therefore, w.r.t. a speci c temporal window, each UAV is able to observe a subset of the set of mission's targets according to its con guration and the sensors required for the observation. Since targets observations are not a priori assigned to agents, the planning system must also autonomously decide which agents employ to perform observations, possibly minimizing the number of agents employed and the global duration of the mission. The following gure reports a graphical example of plan automatically synthesized by the planning system and involving two UAVs and requiring four observations of three di erent targets. For target trg1 an observation involving two sensors together is required in order to perform a data fusion operation.
The nontrivial class of problems introduced above can be de ned as Class U = hU AV; OR; Ci, where U AV is a set of UAVs a priori con gured with suites of sensors, OR is a set of user requests of observations of targets (specifying the minimum duration of observation of a target and the sensors to use) and C is a set of constraints related to the mission (e.g. temporal constraints on global mission duration, UAVs resource constraints and initial position, etc.). We extended this class with two additional types of temporal goals: a set of constraints M among di erent targets observations (e.g. trg1 must be observed BEFORE trg2) and a set of constraints W which speci es the time windows of observability of targets (e.g. trg1 must be observed between 9 a.m. and 12 a.m.).
Encoding and decoding. Temporal aspects and numerical resources play a
central role in this class of problems. In this work we studied how to encode the
described class of problems by adopting two di erent PDDL-based approaches:
a temporal approach, employing durative actions and timed-initial-literals and
exploiting the temporal planners capability to automatically handle temporal
aspects of planning (e.g. actions' temporal location and duration and
concurrency), and a numerical approach, in which time is treated as a numerical uent
and therefore time passing and concurrency must be simulated (an approach
similar to [
Encoding isn't a trivial process and, despite the many knowledge engineering
solutions proposed over the years ([
It is worth noting that in addition to encoding, a signi cant decoding phase is essential to provide exhaustive and meaningful information to the user, especially in numerical (but also in temporal) planning. Numerical planners, in fact, don't provide any relevant temporal information about the scheduled actions. Therefore it is necessary a complex decoding procedure which, for each agent, simulates the execution of the actions.2.
Experimental results. We performed our tests on both synthetic problems
and real-world multi-UAV multi-target planning scenarios. We automatically
generated a dataset of 600 di erent problems encoded in both numerical and
temporal formalism. We de ned three main classes of examples based on the
dimensionality of problems in terms of number of UAVs and targets involved:
Class 2U6T involving two UAVs and six targets, Class 3U8T and Class
4U10T. Problems were then fed to four numeric planners (COLIN [
Preliminary results shown very di erent degrees of scalability, therefore we
considered more accurate and di erent classes of problems.4 The system easily
handles the increase of the number of UAVs and target involved in problems
when few (or no) temporal constraints are involved. See for instance column
U for numerical planning or column U+M for temporal planning. Conversely,
2 A more extensive description of encoding and decoding solutions, as well as a more
detailed experimental validation, are available in [
j
U 2U6T 80,0% 3U8T 50,0% 4U10T 40,0% Total 60,0%
Temporal model U+M U+W 90.0% 60,0% 95,0% 10,0% 80,0% 0,0% 88,3% 23,0%
j U+M+W U 40,0% 100% 45,0% 100% 25,0% 100% 36,6% 100%
Numerical model U+M U+W 97.5% 100% 62,5% 80,0% 5,0% 60,0% 55,0% 80,0%
U+M+W 92,5% 62,5% 17,5% 57,5% j
We also tested the system by considering six real-world scenarios (missions
very similar to the ones used in SMAT ([
Conclusions. The work shows that PDDL numerical and temporal
approaches can be successfully employed (with some work of knowledge engineering
and a nontrivial encoding phase) to e ciently model and solve a great number
of real life complex problems involving cooperative heterogeneous robotic agents
in which numerical resources, time and continuous e ects are mandatory. The
main di culty of these approaches is not expressiveness, but rather scalability,
which is mainly due to temporal constraints. In particular constraints between
di erent agents are challenging for numerical models, due to the simulation of
concurrency, while temporal windows of observability of targets are more
demanding for a temporal model than a numerical one which treats them as
numerical constraints, ignoring time concept. Results shown that the adoption of
a numerical model, despite the necessity of much more complex encoding and
decoding phases, is advantageous in real-world scenarios, since it reacts better
than temporal model. However, there is no clear winner between the two models:
each one is better for a certain type of problems. It is easy to integrate the two
approaches within the same architecture and decide which model to use,
according to the types of requirements the user expressed. Action-based approaches
therefore have proven to be competitive with other state-of-art proposals to
multi-agent planning (e.g. our results are comparable to [