A multitude of autonomous agents - encompassing a range of technologies, including robots and drones - represent a crucial modern tool for the execution of a multitude of tasks, including surveillance, delivery and the saving of lives. In order to optimally utilise these agents, it is vital to configure each agent, the composition of the entire eflet of agents and the mission plan associated with each agent in the most effective manner possible. The following article presents a knowledge model for the configuration of a fleet of heterogeneous agents, encompassing the three levels of configuration: agent configuration, agent fleet configuration, and mission plan configuration. It explicitly delineates the relationships between these three configuration levels, thereby facilitating rapid, efficient, robust, and simultaneous configuration. A toy problem illustrates our first proposals.
1. Introduction
of ground agents with at least the ability to Travel and
Communicate, and aerial agents with at least the ability to
With the increasing autonomy of drones and robots, fleets Observe and Communicate. The success of a multi-agent
of agents are now being used for many different types mission depends, among other things, on the configuration
of missions, such as exploration, rescue, disaster relief, of the fleet executing it [
This multi-level configuration problem raises many research questions, such as: ConfWS’24: 26th International Workshop on Configuration, Sep 2–3, 2024, Girona, Spain ∗ Corresponding author. • the representation/modeling of configuration † These authors contributed equally. knowledge (compact modeling language), $ thomas.poure@student.isae-supaero.fr (T. Pouré); stephanie.roussel@onera.fr (S. Roussel); • eliciting constraints (what is allowed or forbidden) elise.vareilles@isae-supaero.fr (E. Vareilles); and criteria (what is preferable) that apply both to gauthier.picard@onera.fr (G. Picard) the fleet configuration and to each robot in it, and https://onera.academia.edu/SRoussel (S. Roussel); https://pagespro.isae-supaero.fr/elise-vareilles/ (E. Vareilles); • the development of algorithms to generate optimal https://gauthier-picard.info/ (G. Picard) or, at least, good-quality solutions.
0000-0001-7033-555X (S. Roussel); 0000-0001-6269-8609
(E. Vareilles); 0000-0002-9888-9906 (G. Picard) This problem can be tackled in several ways. First of
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License all, there is the question of how to express knowledge,
Attribution 4.0 International (CC BY 4.0).
constraints and preferences, both from the point of view and an illustrative example. Finally, we conclude and
of fleet configuration and from the point of view of per- discuss future works in Section 6.
formance and robustness in the context of mission [
Approaches such as constraint programming and multiagent modeling [3, Chap.2 and 15] appear to be suitable 2. Mission candidates.
Following several works dedicated to Search and Res- A mission allows to represent the several tasks that the
cue applications such as [
This article focuses on initial ideas for modeling the • static: the mission remains static throughout the knowledge of this multi-level configuration problem of lfeet’s intervention. No edges or vertices are introheterogeneous agents fleets. More precisely, we propose a duced or removed during the mission. formal modelling of the inputs of each level configuration problem, along with the decisions that have to be made. 2.1. Description The formalization of constraints associated with each level are out of scope of this paper and are left for future work. A Mission is composed of the following elements.
The paper is organized as follows. In Section 2, we formally describe the type of mission we consider. Then, • The location on which the agents can evolve is repSections 3, 4 and 5 are respectively dedicated to the Agent resented by a connected and non-directed Graph. Configuration Problem or ACP, the Fleet Configuration Such a graph is composed of vertices (Vertex Problem or FCP and the Plan Configuration Problem or class), representing way points or places of interPCP. In each of these sections, we formally present the est in the mission context, and edges (Edge class), inputs of the problem, the associated decision variables representing routes for moving. 1..* Edge 1 Traficability 1..* 1..*
Task *
1 Graph -base 2
1..* Vertex 1
1
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, . . . , nV ) is the vector of vertices. We suppose that vertex with number 1 is the base. • E = (ei, j)i, j∈[1..nV ]2 is the adjacency matrix of size nV2 that represents the connection between vertices V . For all vertices i, j ∈ [1..nV ]2, ei, j = 1 if there exists an edge between vertices i and j, ei, j = 0 otherwise. • T = (1, . . . , nT ) is the vector of tasks that have to be performed during the mission. • TV = (tvi)i∈[1..nT ] is a vector of size nT such that for all task i ∈ [1..nT ], tvi ∈ [1..nV ] is the vertex the task i is assigned to. • C = (1, . . . , nC) is the vector of capability types. • CT = (cti)i∈[1..nT ] is a vector of size nT , such that for each task i ∈ [1..nT ] in m, cti ∈ [1..nC] represents the capability required by task i. • R = (1, . . . , nR) is the vector of traficabilities. • RE = (rei, j)i, j∈[1..nV ]2 is a matrix of size nV2 , such as for each edge (i, j) ∈ [1..nV ]2, rei, j ∈ [1..nR] is the trafficability of the edge ei, 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.
∀i ∈ [1..nV ], ei,i = 0 • The graph is non-oriented and the trafficability matrix is symmetrical.
E = ET
RE = RET • The graph is connected, i.e. from any two vertices i and j, there exists a path of edges connecting them. Formally, ∀i, j ∈ [1..nV ]2, ∃k ∈ N∗ , ∃(v1, . . . , vk) ∈ [1..nV ]k, such that: ∀r ∈ [1..k − 1], v1 = i, vk = j • The vertices vector of locations is V = ︁( 1 2 3︁) , where 1 is the "base" (c), 2 is the "ruins" (r), and 3 is the "aid camp" (_). (1) (2) (3) (4) (5) c k
r 4 4 _
Task g Capa. ~ 3. Agent Configuration Problem 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 PlatformType 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 EquipmentType, 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 Traficability 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. * Traficability
* PlatformType
Platform
Catalog
1 ACP
1..* EquipmentType
1
Equipment • maxQ ∈ N∗ is an upper bound on the number of instances of each equipment type that can be carried by an agent pattern, • 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 ∈ [1..nT ], ∃ j ∈ [1..nP], ∃k ∈ N∗ , (v1, . . . , vk) ∈ [1..nV ]k, s. t.
∀r ∈ [1..k − 1]2, v1 = 1, vk = tvi
The catalog is the only input of the ACP.
For a given catalog cat, the objective of ACP is to • RP = (r pi, j)i, j∈[1..nP]× [1..nR] is the plat- compute a tuple Tcat = (1, . . . , nT ) where each element form/traficability compatibility matrix of is an index of an agent pattern, as defined previously, and size nQ.nR. For each platform type i ∈ [1..nP] nT the number of elements in the tuple. and each trafficability j ∈ [1..nR], r pi, j = 1 if the As we do not consider any constraint in this paper, platform type i is compatible with trafficability j. there are nT = nP · nmaxQ possible agent patterns. In real Otherwise, r pi, j = 0. world applications, thQe ACP should of course satisfy some • CQ = (cqi, j)i, j∈[1..nQ]× [1..nC] is the equip- constraints (e.g. max payload, mission’s budget, etc.) and ment/capability relation matrix of size nQ.nC. could optimize some criteria (e.g. cost minimization). For each equipment type i ∈ [1..nQ] and each This is out of scope of this paper, and so are the precise capability j ∈ [1..nC], cqi, j = 1 if the equipment definitions of platform and equipment attributes related type i provides the capability j. It equals 0 to them (such as weight, price, etc.). Note that even with otherwise. constraints consideration, the vector Tcat might be too large to be exhaustively explored. 3.2.2. Assumptions 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:
nQ ∀ j ∈ [1..nT ], ∑ cqi,ct j ≥ 1 i=1 (6)
We consider the mission m defined in Subsection 2.3.
We define the catalog cat the following way.
• The platform types vector is P = (︁ 1 1 is "UAV" (Ê) and 2 is "rover" (). 2︁) , where • The equipment types vector is Q = (︁ 1 2︁) , where 1 is "camera" () and 2 is "trunk" ().
FCP
*
Stock AgentPattern * Agent Fleet
However, r p1,2 = 0, which means that this equipment does not provide capability 2 ("carry").
The two following agent patterns belong to Tcat: camera and zero trunk.
camera and one trunk. • a1 = (1, (︁ 1
0︁) ) is a UAV equipped with one • a2 = (2, (︁ 1
1︁) ) is a rover equipped with one There is a total of nT = 6 possible agent patterns (Tcat = (a1, . . . , a6)). 4. Fleet Configuration Problem 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.
• Af = (ai)i∈[1..na] is the finite vector of size agents in the fleet such as, for each i ∈ [1..na], ai ∈ [1..nT ] is the index of the agent pattern of the na of agent i in the fleet.
Note that the model allows to have the same agent pattern present several times in Af, 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 Tcat defined in Subsection 3.3.
We define the stock scat the following way.
• The platform instance vector is Ps = (︁ 2 1︁) , 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 Qs = (︁ 2 1︁) .
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: • fs1cat,Tcat = (1, (a2)), is a fleet composed of a single agent with the pattern a2 (a rover equipped with one camera and one trunk - + + ). AgentPlan 1 1 *
Agent PCP 5. Plan Configuration Problem
In order to represent the position of each agent in the so• fs2cat,Tcat = (2, (a1, a2)), is a fleet composed of two lution plan, we use binary decision variables (Vpl matrix) agents with the respective patterns a1 (a UAV that indicate whether an agent is at a given position at equipped with one camera - Ê+ ) and a2 (a each time step. Similarly, for each task, we use binary rover equipped with one camera and one trunk - 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, scat, a mission m, a fleet fscat,Tcat , a plan is a tuple plm, fscat,Tcat = (H, Tpl, Vpl) where: 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. 5.2.1. Inputs For a catalog cat, a stock on this catalog, scat, the PFD associated to this stock requires two additional inputs: • H ∈ N∗ is the temporal plan horizon. • Tpl = (tpli, j,h)i, j,h∈[1..na]× [1..nT ]× [1..H] is the allocation of tasks over agents for each time steps, represented as a tensor of size na · nT · H. For each agent i ∈ [1..na], each task j ∈ [1..nT ] and each time step h ∈ [1..H], tpli, j,t = 1 if the agent ai ∈ Af is executing the task j at the time h. It equals 0 otherwise. • Vpl = (vpli, j,h)i, j,h∈[1..na]× [1..nV ]× [1..H] is the position of the agents for each time steps, defined by a tensor of size na · nT · H. For each agent i ∈ [1..na], each task j ∈ [1..nT ] and each time step h ∈ [1..H], vpli, j,t equals 1 if the agent ai ∈ Af is at the vertex j at the time h. It equals 0 otherwise.
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. r 4 Ê c 4
k
Vpl2)︁ ), il- configuration problem for a fleet of heterogeneous agent. moves to the aid camp; then, they both perform the required tasks in their respective locations; finally, they both come back to from Example 5.3: starting from the base, the UAV moves to the ruins while the rover We consider the following plan for the fleet
6. Conclusion Ê c 4
k (a) Step 1 _ f 2 scat,Tcat = (2, (a1, a2)): plm, fscat,Tcat lustrated in Fig. 7, where: • Tpl1 =
is the task allocation matrix of the first agent of the fleet, that has pattern (platform Ê). It performs the task "explore the
a1 ruins" (☼) at time step 2. • Vpl1 = ⎝0
0⎠ describes the movement of the first agent of the fleet, that has pattern starts at the "base" (c) than goes to the "ruins"
a1. It (r) and comes back to the "base" (c). • Tpl2 =
is the task allocation matrix ︃( 0
0 ⎛1
0 ︃( 0
0 ⎛1 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 ︃) ︃) 1⎞ 0 1⎞ 0 • Vpl2 = ⎝0
0⎠ describes the movement of the second agent of the team, with pattern a2. It starts at the "base" (c) than goes to the "aid camp" (_) and comes back to the "base" (c).
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.
plies" (g) at the time step 2. of the second agent of the team, with pattern a2 (platform ). It performs the task "deliver sup- the evaluation of solutions produced by PCP and FCP can In this paper, we model and formalize the multi-level 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 [
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, 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 [
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 [10] R. F. Lemme, E. F. Arruda, L. Bahiense, Optirequiring synchronisation between multiple agents), a mization model to assess electric vehicles as an alnon-deterministic setting (e.g. uncertainty on tasks dura- ternative for fleet composition in station-based car tion) and a dynamic environment (e.g. discover the edges sharing systems, Transportation Research Part D: trafficability, agent’s loss). Transport and Environment 67 (2019) 173–196. [11] R. Pinto, A. Lagorio, R. Golini, Urban freight lfeet composition problem, IFAC-PapersOnLine Acknowledgments 51 (2018) 582–587. [12] H. R. Sayarshad, R. Tavakkoli-Moghaddam, SolvThe authors would like to thank the ONERA, ISAE- ing a multi periodic stochastic model of the rail–car SUPAERO and ENAC Federation for its support of this lfeet sizing by two-stage optimization formulawork. This work is partly founded by the ONERA fed- tion, Applied Mathematical Modelling 34 (2010) erative project on cooperative and interactive intelligent 1164–1174. doi:https://doi.org/10.1016/j. multi-robot systems (SICICOD). apm.2009.08.004.