With the increasing autonomy of drones and robots, fleets of agents are now being used for many different types of missions, such as exploration, rescue, disaster relief, civil and military security. In this article, the term "agent" is used to refer to any system that is capable of acting autonomously in a variety of environments, including ground, water, and air. The term encompasses a diverse range of platforms, including quadrupeds, bi-blades, underwater rockets, and others. Additionally, the term "agent" encompasses a wide range of capabilities, including communication, rescue, and delivery. Therefore, the term "agent" can be used to describe a diverse range of systems, from household robots to high-tech stealth military drones. Some of these applications require heterogeneous agent fleets, i.e. with different platforms, capabilities, mobility and equipment. Such fleet of heterogeneous agents may or may not be coordinated autonomously to carry out the missions to which the fleet is dedicated. For example, an exploration mission may require the collaboration of ground agents with at least the ability to Travel and Communicate, and aerial agents with at least the ability to Observe and Communicate. The success of a multi-agent mission depends, among other things, on the configuration of the fleet executing it [1].
This paper addresses the problem of multi-level configuration of heterogeneous agent fleets, as presented in Fig. 1. By multi-level configuration, we mean the several interleaved problems that must be solved when setting up a fleet to carry out a mission. The first level is the simultaneous configuration of each agent (Agent Configuration Problem, ACP). The second consists in configuring the fleet itself (Fleet Configuration Problem, FCP), i.e. defining precisely what the composition of the fleet is. The final level is the fleet deployment problem in order to carry out dedicated missions in an efficient and robust way (Plan Configuration Problem, PCP). This multi-level configuration problem requires an analysis of the relationships between these three configuration levels, both upstream in fleet composition and downstream in fleet operation.
This multi-level configuration problem raises many research questions, such as:
• the representation/modeling of configuration knowledge (compact modeling language),
• eliciting constraints (what is allowed or forbidden) and criteria (what is preferable) that apply both to the fleet configuration and to each robot in it, and
• the development of algorithms to generate optimal or, at least, good-quality solutions.
This problem can be tackled in several ways. First of all, there is the question of how to express knowledge, constraints and preferences, both from the point of view of fleet configuration and from the point of view of performance and robustness in the context of mission [2]. Approaches such as constraint programming and multiagent modeling [3, Chap.2 and 15] appear to be suitable candidates.
Following several works dedicated to Search and Rescue applications such as [4] and [5], a mission consists here in the execution of several tasks distributed on an intervention zone represented by a graph. A fleet and a plan of action are configured in order to accomplish the mission, i.e. successfully complete all the tasks. The performance of a fleet for a mission can be evaluated along several criteria: the global time required for performing all tasks, the fleet cost (platform, equipment), the fleet and the plan robustness (capacity of the fleet/the plan to support damages and complications), etc.
This article focuses on initial ideas for modeling the knowledge of this multi-level configuration problem of heterogeneous agents fleets. More precisely, we propose a formal modelling of the inputs of each level configuration problem, along with the decisions that have to be made. The formalization of constraints associated with each level are out of scope of this paper and are left for future work.
The paper is organized as follows. In Section 2, we formally describe the type of mission we consider. Then, Sections 3, 4 and 5 are respectively dedicated to the Agent Configuration Problem or ACP, the Fleet Configuration Problem or FCP and the Plan Configuration Problem or PCP. In each of these sections, we formally present the inputs of the problem, the associated decision variables and an illustrative example. Finally, we conclude and discuss future works in Section 6.
A mission allows to represent the several tasks that the agents have to perform and the graph on which they can move. The elements composing a mission can be represented in a UML diagram as illustrated in Fig. 2. Those elements are first briefly described and then formalized in a second step. In our work, we have made several assumptions on a mission. A mission is therefore:
• deterministic: the mission is perfectly known from the beginning and during the fleet's intervention, and agents cannot suffer from malfunctions,
• static: the mission remains static throughout the fleet's intervention. No edges or vertices are introduced or removed during the mission.
A Mission is composed of the following elements. • One of the vertices is called the base, and is the location at which the agents start and finish their missions.
• The actions that the agents have to perform to achieve the mission are called Tasks. Each task is assigned to a single vertex, that represents the location at which it must be executed. A capability is associated to each task, it is the requirement to perform a task.
For the agent to be able to move through the graph and execute task, we define two additional classes.
• A Capability describes how an agent accomplishes the mission's tasks. More precisely, each task requires a single specific capability to be executed. Examples of capabilities are observe, grab material, transport a injured person, etc.
• One instance of Trafficability is associated to each edge, representing the edge practical environment for agent moves. Instances of Trafficability could be Aerial, Terrestrial or more fine-grained properties such as Forest, Field, Street, etc. Note that a trafficability could also be combinations such as Terrestrial and Aerial.
We propose here a mathematical formalization of the mission, that can be used as input for the multi-level configuration problem.
A mission is a tuple m = (V, E, T, TV, C, CT, R, RE) where:
• V = (1, . . . , n V ) is the vector of vertices. We suppose that vertex with number 1 is the base.
V that represents the connection between vertices V . For all vertices i, j ∈ [1..n V ] 2 , e i, j = 1 if there exists an edge between vertices i and j, e i, j = 0 otherwise.
• T = (1, . . . , n T ) is the vector of tasks that have to be performed during the mission.
.n V ] is the vertex the task i is assigned to.
• C = (1, . . . , n C ) is the vector of capability types.
.n C ] represents the capability required by task i.
• R = (1, . . . , n R ) is the vector of traficabilities.
is the trafficability of the edge e i, j in m.
We call the graph associated to a mission m the pair (V, E). A mission m is said to be well-formed if the following assumptions hold:
• The graph does not contain any edge from a vertex to itself.
• The graph is non-oriented and the trafficability matrix is symmetrical.
• The graph is connected, i.e. from any two vertices i and j, there exists a path of edges connecting them. Formally, ∀i, j ∈
• For any vertices i, j ∈ [1..n V ] 2 , e i, j = 1 means that there is exactly one edge between vertices i and j.
In order to illustrate the notations defined previously, we consider the following toy example.
We define a simple Search & Rescue mission m, illustrated in Fig. 3, composed of the following elements.
, where 1 is the "base" ( ), 2 is the "ruins" ( ), and 3 is the "aid camp" ( ).
Task ☼ Capa. Task Capa.
Illustration for Example 2.3. Three locations are considered: a base ( ), ruins ( ) to explore, and an aid camp ( ) to supply. Moving from the base to the ruins requires an aerial agent ( ), while moving to the camp requires a terrestrial agent ( ).
• The edges matrix of paths is
For instance, e 1,3 = 1 holds, meaning that it is possible to directly go from vertex 1 ("base") to vertex 3 ("aid camp").
• The tasks vector is
, where 1 is "explore the ruins" (☼), and 2 is "deliver supplies" ( ).
• The assignment of tasks to the vertices is the vector
)︁ , representing that task 1 ("explore the ruins") and task 2 ("deliver supplies") must respectively be executed in vertex 2 ("ruins") and vertex 3 ("aid camp").
, where 1 is "carry" ( ), and 2 is "observe" ( ).
• The assignment of capabilities to the tasks is the vector
)︁ , meaning that capability 2 ("observe") is required for task 1 ("explore the ruins") and capability 1 ("carry") is required for task 2 ("deliver supplies").
, where 1 is "terrestrial" ( ), and 2 is "aerial" ( ).
• The assignment of traficabilities to the edges is the
(1, 2) has the trafficability 2 ("aerial"), whereas the path (2, 3) has the trafficability 1 ("terrestrial").
In this section, we present the model associated with the Agent Configuration Problem (ACP), which consists in deciding agents' composition wrt. a catalog of platform types and equipment types, by using the notion of agent pattern.
As illustrated in Fig. 4, an AgentPattern represents a type of robot or a type of drone that can act somewhat autonomously. Elements composing an agent pattern are divided as follows:
• Platform represents the skeleton of an agent pattern. Each agent pattern has a single platform.
• Each Platform is associated to a unique Platform-Type representing the agent pattern skeleton type.
Examples of such platform types could be aerial, terrestrial, marine. It would also be possible to consider more fine-grained platform types, such as quadcopter or submarine. The platform type limits and defines most of the agent pattern characteristics.
• Equipment represents the payload that can equip an agent pattern. An agent pattern can be equipped with several equipments.
• Each Equipment is associated to a unique Equip-mentType, which represents the type of the equipment (e.g. camera, sensor, motor).
• Available PlatformTypes and EquipmentTypes are grouped in a Catalog.
An agent is able to interact with the mission throughout two connections to the mission description:
• Each Equipment instance has a set of Capability instances, allowing agents to execute tasks. If an agent pattern is equipped with an equipment that provides the capability associated to a task, then any agent following that pattern will be able to perform the task.
• Each PlatformType instance is associated with a set of Trafficability instances representing the types of environments it is compatible with. Consequently, an agent pattern is compatible with an edge if and only if the edge trafficability belongs to the agent pattern platform type set of compatible traficabilities.
We first formalize the inputs of the agent configuration problem and then define the decision variables. We next present some assumptions on the problems we consider and finally illustrate the concepts on the toy example.
Let m be a mission. A catalog on m is a tuple cat m = (P, Q, max Q , RP, CQ) where:
• P = (1, . . . , n P ) is the platform types vector, The catalog is the only input of the ACP.
A catalog cat should satisfy the following assumptions.
• Task Feasibility. For each task, there is at least one equipment type in the catalog that provides its capability, which translates into:
• Task Reachability. For each task, there exists a platform type and a path from the base to the task's vertex such that the platform type is compatible with all the path's edges trafficabilities. Formally, ∀i ∈
Those two assumptions ensure that for each task in the mission, there exists an agent pattern compatible with the task perform it.
We present here the decision variables that must be assigned a value when solving an ACP. To do so, we first formally define an agent pattern.
For a given catalog cat, an agent pattern is a tuple a cat = (ap, AQ) where :
• ap is an integer in [1..n P ] that represents the platform of catalog cat associated with a cat .
For a given catalog cat, the objective of ACP is to compute a tuple T cat = (1, . . . , n T ) where each element is an index of an agent pattern, as defined previously, and n T the number of elements in the tuple.
As we do not consider any constraint in this paper, there are n T = n P • n max Q Q possible agent patterns. In real world applications, the ACP should of course satisfy some constraints (e.g. max payload, mission's budget, etc.) and could optimize some criteria (e.g. cost minimization). This is out of scope of this paper, and so are the precise definitions of platform and equipment attributes related to them (such as weight, price, etc.). Note that even with constraints consideration, the vector T cat might be too large to be exhaustively explored.
We consider the mission m defined in Subsection 2.3.
We define the catalog cat the following way.
• The platform types vector is
, where 1 is "UAV" ( ) and 2 is "rover" ( ).
, where 1 is "camera" ( ) and 2 is "trunk" ( ). • the maximum number for each equipment instance on an agent pattern is max Q = 1.
• The platform/trafficability compatibility matrix is
)︃ . In this example, rp 1,2 = 1 holds, meaning that platform 1 ("UAV") is compatible with the trafficability 2 ("aerial"). However, as rp 1,1 = 0, platform 1 is not compatible trafficability 1 ("terrestrial").
• The equipment/capability relation matrix is CQ = (︃ 1 0 0 1
)︃ . In this example, rp 1,1 = 1 holds, meaning that the equipment 1 ("camera") provides the capability 2 ("observe"). However, rp 1,2 = 0, which means that this equipment does not provide capability 2 ("carry").
The two following agent patterns belong to T cat :
•
) is a UAV equipped with one camera and zero trunk.
)︁
) is a rover equipped with one camera and one trunk.
There is a total of n T = 6 possible agent patterns (T cat = (a 1 , . . . , a 6 )).
In this section, we present the model associated with the Fleet Configuration Problem (FCP), which aims at deciding the composition of the fleet wrt. the available stock.
Fig. 5 contains a UML representation of the Fleet Configuration Problem. The FCP class takes as an input the set of AgentPattern computed by the ACP, as presented in the previous section. Its output is a Fleet, i.e. a collection of Agents, where each Agent is associated to a unique AgentPattern.
In order to model the fact that equipment and platform are available in limited quantities, we define the class Stock. Such a class is associated to a set of Platforms and a set of Equipments. The FCP takes an instance of Stock as an input. Even if it is clear that the stock will impose hard constraints on FCP, the precise formalization of these constraints is left for future work.
We first formalize the inputs of the agent configuration problem, then define the decision variables and illustrate the formalization on the toy example.
Let cat be a catalog. The FCP associated to this catalog has two inputs:
• A stock associated with cat, denoted s cat , and defined by a pair (P s , Q s ) where:
.n P ] is a vector of size n P such that for each platform type i ∈ [1..n P ] in cat, p i ∈ N * defines how many type i platform instances are in the stock.
-Q s = (q j ) j∈[1..n Q ] is a vector of size n Q such that for each equipment type j ∈ [1..n Q ] in cat, q j ∈ N * defines how many type j equipment instances are in the stock.
• A vector of agents pattern T cat . Such a vector can for instance come from the output resulting from the ACP solving.
Given a catalog cat, a stock s cat on this catalog, and T cat a vector of the agent patterns, a fleet is a tuple f s cat ,T cat = (n a , A f ) where:
• n a is the size of the fleet.
.n a ] is the finite vector of size n a of agents in the fleet such as, for each
is the index of the agent pattern of the agent i in the fleet.
Note that the model allows to have the same agent pattern present several times in A f , representing the fact that there are some identical agents in the fleet.
We consider the mission m defined in Subsection 2.3, the catalog cat and the agent patterns T cat defined in Subsection 3.3.
We define the stock s cat the following way.
• The platform instance vector is
)︁ , meaning that there are 2 instances of type 1 platform ("UAV" -) and 1 instance of type 2 platform ("rover" -) in the stock.
• The equipment instances vector is
)︁ . In this example, there are two instances of type 1 equipment ("camera" -) and one instance of type 2 equipment ("trunk" -) in the stock.
With this stock, it is possible to configure several fleets of agents. For instance, we define two fleets as follows:
), is a fleet composed of a single agent with the pattern a 2 (a rover equipped with one camera and one trunk -+ + ).
• f 2 s cat ,T cat = (2, (a 1 , a 2 )), is a fleet composed of two agents with the respective patterns a 1 (a UAV equipped with one camera -+ ) and a 2 (a rover equipped with one camera and one trunk -+ + ).
In this section, we present the model associated with the Plan Configuration Problem (PCP), which aims at deciding the agents' positions and tasks all along the mission.
The plan configuration is the last problem to solve in order to get a solution for the multi-level configuration problem. As illustrated on Fig. 6, it takes as input a Mission and a Fleet. Its output is a Plan which consists of an AgentPlan for each Agent in the fleet. For each agent in the fleet, an AgentPlan describes exhaustively at any given time step the position of the agent and the task currently executed, if any.
We first formalize the inputs of the plan configuration problem and then define the decision variables.
For a catalog cat, a stock on this catalog, s cat , the PFD associated to this stock requires two additional inputs: • a mission m,
• a fleet f s cat ,T cat .
In order to represent the position of each agent in the solution plan, we use binary decision variables (Vpl matrix) that indicate whether an agent is at a given position at each time step. Similarly, for each task, we use binary decision variables indicating whether an agent executes this task at the time step (Tpl matrix).
Formally, for a catalog cat, a stock on this catalog, s cat , a mission m, a fleet f s cat ,T cat , a plan is a tuple pl m, f s cat ,T cat = (H, Tpl, Vpl) where:
• H ∈ N * is the temporal plan horizon.
• Tpl = (tpl i, j,h ) i, j,h∈ [1..n Through this plan formalization, moves of agents are not explicitly described, but this piece of information could be retrieved through their positions.
We consider the definitions of mission m, catalog cat, introduced in the three previous examples. 3: starting from the base, the UAV moves to the ruins while the rover moves to the aid camp; then, they both perform the required tasks in their respective locations; finally, they both come back to the base.
We consider the following plan for the fleet f 2 s cat ,T cat = (2, (a 1 , a 2 )):
), illustrated in Fig. 7, where:
is the task allocation matrix of the first agent of the fleet, that has pattern a 1 (platform ). It performs the task "explore the ruins" (☼) at time step 2.
• Vpl 1 = ⎛ ⎝ 1 0 1 0 1 0 0 0 0 ⎞ ⎠ describes the movement of the first agent of the fleet, that has pattern a 1 . It starts at the "base" ( ) than goes to the "ruins" ( ) and comes back to the "base" ( ).
• Tpl 2 = (︃ 0 0 0 0 1 0 )︃ is the task allocation matrix of the second agent of the team, with pattern a 2 (platform ). It performs the task "deliver supplies" ( ) at the time step 2.
• Vpl 2 = ⎛ ⎝ 1 0 1 0 0 0 0 1 0 ⎞ ⎠ describes the movement of the second agent of the team, with pattern a 2 . It starts at the "base" ( ) than goes to the "aid camp" ( ) and comes back to the "base" ( ).
Note that the time steps used in that example plan give a macro view of the agents actions. It would be possible to have a much finer discretization of the time in order to handle temporal constraints such as task duration, or edge traversal duration.
In this paper, we model and formalize the multi-level configuration problem for a fleet of heterogeneous agent. This problem is decomposed into three problems, ACP, FCP and PCP and for each of them, we formally define their inputs and their decision variables and we illustrate them on a toy problem. We focus on Search and Rescue missions where tasks have to performed on some nodes of a given graph.
The work presented in this paper is a first step for solving the multi-level configuration problem. As mentioned in the paper, the next step is to formally define the set of constraints and the eventual criteria associated to ACP, FCP and PCP. To do so, it will be possible to study the literature associated with each problem, such as [1] for ACP, [3,6] for FCP and [7,8,9] for PCP.
Then, we have presented the three configuration problems independently but in practice, they are interleaved. For instance the output of ACP is an input of FCP, and the output of FCP is an input for PCP. In the other direction, the evaluation of solutions produced by PCP and FCP can influence the choices made in ACP. If the evaluation of the overall multi-level configuration solution is not satisfactory, there might be several interactions between each level before converging (if any convergence is possible). In order to avoid these interactions, it would be possible to solve all the configuration problems simultaneously. Some works have started contributing towards that objective [10,11,12,2]. Following those works, we aim at proposing a global solver/architecture for solving the multi-level configuration problem.
Finally, we have considered here a simple model of a Search and Rescue mission. It would be possible to make it more realistic in several ways. For instance, it would be possible to consider: more complex mission (e.g. with multiple bases), autonomy constraints on agents forcing them to recharge in some specific locations, more complex tasks (e.g. requiring multiple capabilities, or requiring synchronisation between multiple agents), a non-deterministic setting (e.g. uncertainty on tasks duration) and a dynamic environment (e.g. discover the edges trafficability, agent's loss).
The authors would like to thank the ONERA, ISAE-SUPAERO and ENAC Federation for its support of this work. This work is partly founded by the ONERA federative project on cooperative and interactive intelligent multi-robot systems (SICICOD).