=Paper=
{{Paper
|id=Vol-3812/paper1
|storemode=property
|title=Configuration of Heterogeneous Agent Fleet: a Preliminary Generic Model
|pdfUrl=https://ceur-ws.org/Vol-3812/paper1.pdf
|volume=Vol-3812
|authors=Thomas Pouré,Stephanie Roussel,Elise Vareilles,Gauthier Picard
|dblpUrl=https://dblp.org/rec/conf/confws/Poure0VP24
}}
==Configuration of Heterogeneous Agent Fleet: a Preliminary Generic Model==
https://ceur-ws.org/Vol-3812/paper1.pdf
Configuration of Heterogeneous Agent Fleet: a Preliminary
Generic Model
Thomas Pouré1,† , Stéphanie Roussel2,† , Elise Vareilles1,3,∗,† and Gauthier Picard2,†
1 ISAE SUPAERO, Université de Toulouse, 10 avenue Édouard Belin, BP 54032 - 31055 Toulouse CEDEX 4, France
2 DTIS, ONERA, Université de Toulouse, 2 avenue Édouard Belin, BP 74025 - 31055 Toulouse CEDEX 4, France
3 CGI / IMT Mines Albi, Université de Toulouse, allée des sciences, 81000 Albi, France
Abstract
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 fleet 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.
Keywords
Multi-level Configuration, Autonomous Agent, Knowledge Formalisation, Heterogeneous Fleet,
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 [1].
civil and military security. In this article, the term "agent" This paper addresses the problem of multi-level con-
is used to refer to any system that is capable of acting figuration of heterogeneous agent fleets, as presented in
autonomously in a variety of environments, including Fig. 1. By multi-level configuration, we mean the several
ground, water, and air. The term encompasses a di- interleaved problems that must be solved when setting
verse range of platforms, including quadrupeds, bi-blades, up a fleet to carry out a mission. The first level is the
underwater rockets, and others. Additionally, the term simultaneous configuration of each agent (Agent Configu-
"agent" encompasses a wide range of capabilities, includ- ration Problem, ACP). The second consists in configuring
ing communication, rescue, and delivery. Therefore, the the fleet itself (Fleet Configuration Problem, FCP), i.e.
term "agent" can be used to describe a diverse range of sys- defining precisely what the composition of the fleet is.
tems, from household robots to high-tech stealth military The final level is the fleet deployment problem in order
drones. Some of these applications require heterogeneous to carry out dedicated missions in an efficient and robust
agent fleets, i.e. with different platforms, capabilities, mo- way (Plan Configuration Problem, PCP). This multi-level
bility and equipment. Such fleet of heterogeneous agents configuration problem requires an analysis of the rela-
may or may not be coordinated autonomously to carry out tionships between these three configuration levels, both
the missions to which the fleet is dedicated. For exam- upstream in fleet composition and downstream in fleet
ple, an exploration mission may require the collaboration operation.
This multi-level configuration problem raises many re-
ConfWS’24: 26th International Workshop on Configuration, Sep 2–3, search questions, such as:
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
Attribution 4.0 International (CC BY 4.0). all, there is the question of how to express knowledge,
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
Figure 1: Multi-level configuration of an heterogeneous fleet of robots.
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 [2].
Approaches such as constraint programming and multi-
agent 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 [4] and [5], a mission consists agents have to perform and the graph on which they can
here in the execution of several tasks distributed on an move. The elements composing a mission can be repre-
intervention zone represented by a graph. A fleet and a sented in a UML diagram as illustrated in Fig. 2. Those
plan of action are configured in order to accomplish the elements are first briefly described and then formalized
mission, i.e. successfully complete all the tasks. The per- in a second step. In our work, we have made several
formance of a fleet for a mission can be evaluated along assumptions on a mission. A mission is therefore:
several criteria: the global time required for performing • deterministic: the mission is perfectly known
all tasks, the fleet cost (platform, equipment), the fleet from the beginning and during the fleet’s interven-
and the plan robustness (capacity of the fleet/the plan to tion, and agents cannot suffer from malfunctions,
support damages and complications), etc.
This article focuses on initial ideas for modeling the • static: the mission remains static throughout the
knowledge of this multi-level configuration problem of fleet’s intervention. No edges or vertices are intro-
heterogeneous 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 rep-
Sections 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 inter-
PCP. 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..* V . For all vertices i, j ∈ [1..nV ]2 , ei, j = 1 if there
Mission Task
exists an edge between vertices i and j, ei, j = 0
*
1 otherwise.
Graph • T = (1, . . . , nT ) is the vector of tasks that have to
1..* 1..* be performed during the mission.
-base
Edge Vertex • TV = (tvi )i∈[1..nT ] is a vector of size nT such that
1..* 2 1
for all task i ∈ [1..nT ], tvi ∈ [1..nV ] is the vertex
1 1 the task i is assigned to.
Trafficability Capability
• C = (1, . . . , nC ) is the vector of capability types.
Figure 2: UML representation of a mission. • CT = (cti )i∈[1..nT ] is a vector of size nT , such that
for each task i ∈ [1..nT ] in m, cti ∈ [1..nC ] repre-
sents the capability required by task i.
• One of the vertices is called the base, and is the • R = (1, . . . , nR ) is the vector of traficabilities.
location at which the agents start and finish their
missions. • 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 actions that the agents have to perform to the trafficability of the edge ei, j in m.
achieve the mission are called Tasks. Each task
is assigned to a single vertex, that represents the We call the graph associated to a mission m the pair
location at which it must be executed. A capability (V, E). A mission m is said to be well-formed if the fol-
is associated to each task, it is the requirement to lowing assumptions hold:
perform a task.
• The graph does not contain any edge from a vertex
For the agent to be able to move through the graph and to itself.
execute task, we define two additional classes. ∀i ∈ [1..nV ], ei,i = 0 (1)
• A Capability describes how an agent accom- • The graph is non-oriented and the trafficability
plishes the mission’s tasks. More precisely, each matrix is symmetrical.
task requires a single specific capability to be exe-
cuted. Examples of capabilities are observe, grab E = ET (2)
material, transport a injured person, etc. RE = RE T (3)
• One instance of Trafficability is associated to each • The graph is connected, i.e. from any two ver-
edge, representing the edge practical environment tices i and j, there exists a path of edges con-
for agent moves. Instances of Trafficability could necting them. Formally, ∀i, j ∈ [1..nV ]2 , ∃k ∈ N∗ ,
be Aerial, Terrestrial or more fine-grained proper- ∃(v1 , . . . , vk ) ∈ [1..nV ]k , such that:
ties such as Forest, Field, Street, etc. Note that a
trafficability could also be combinations such as v1 = i, vk = j (4)
Terrestrial and Aerial. ∀r ∈ [1..k − 1], evr ,vr+1 = 1 (5)
• For any vertices i, j ∈ [1..nV ]2 , ei, j = 1 means that
2.2. Formalization there is exactly one edge between vertices i and j.
We propose here a mathematical formalization of the mis- In order to illustrate the notations defined previously,
sion, that can be used as input for the multi-level configu- we consider the following toy example.
ration problem.
A mission is a tuple m = (V, E, T, TV, C, CT, R, RE)
where: 2.3. Toy Problem Mission
We define a simple Search & Rescue mission m, illustrated
• V = (1, . . . , nV ) is the vector of vertices. We sup-
in Fig. 3, composed of the following elements.
pose that vertex with number 1 is the base.
• The vertices vector of locations is V =
• E = (ei, j )i, j∈[1..nV ]2 is the adjacency matrix of size (︁ )︁
1 2 3 , where 1 is the "base" (c), 2 is the
nV2 that represents the connection between vertices "ruins" (r), and 3 is the "aid camp" (_).
Task ☼ types and equipment types, by using the notion of agent
r Capa. 4 pattern.
k
4 3.1. Description
c
As illustrated in Fig. 4, an AgentPattern represents a
4 Task g
_ Capa. ~
type of robot or a type of drone that can act somewhat
autonomously. Elements composing an agent pattern are
Figure 3: Illustration for Example 2.3. Three locations are divided as follows:
considered: a base (c), ruins (r) to explore, and an aid camp
(_) to supply. Moving from the base to the ruins requires • Platform represents the skeleton of an agent pat-
an aerial agent (k), while moving to the camp requires a tern. Each agent pattern has a single platform.
terrestrial agent (4).
• Each Platform is associated to a unique Platform-
Type representing the agent pattern skeleton type.
⎛ ⎞ Examples of such platform types could be aerial,
0 1 1
terrestrial, marine. It would also be possible to
• The edges matrix of paths is E = ⎝1 0 1⎠.
consider more fine-grained platform types, such
1 1 0
as quadcopter or submarine. The platform type
For instance, e1,3 = 1 holds, meaning that it is
limits and defines most of the agent pattern char-
possible to directly go from vertex 1 ("base") to
acteristics.
vertex 3 ("aid camp").
(︁ )︁ • Equipment represents the payload that can equip
• The tasks vector is T = 1 2 , where 1 is "ex-
an agent pattern. An agent pattern can be equipped
plore the ruins" (☼), and 2 is "deliver supplies"
with several equipments.
(g).
• Each Equipment is associated to a unique Equip-
• The assignment of
)︁ tasks to the vertices is the vec-
(︁ mentType, which represents the type of the equip-
tor TV = 2 3 , representing that task 1 ("ex-
ment (e.g. camera, sensor, motor).
plore the ruins") and task 2 ("deliver supplies")
must respectively be executed in vertex 2 ("ruins") • Available PlatformTypes and EquipmentTypes
and vertex 3 ("aid camp"). are grouped in a Catalog.
(︁ )︁
• The capabilities vector is C = 1 2 , where 1 is An agent is able to interact with the mission throughout
"carry" (~), and 2 is "observe" (4). two connections to the mission description:
• The assignment (︁ of capabilities
)︁ to the tasks is the • Each Equipment instance has a set of Capability
vector CT = 2 1 , meaning that capability 2 instances, allowing agents to execute tasks. If an
("observe") is required for task 1 ("explore the agent pattern is equipped with an equipment that
ruins") and capability 1 ("carry") is required for provides the capability associated to a task, then
task 2 ("deliver supplies"). any agent following that pattern will be able to
(︁ )︁ perform the task.
• The traficabilities are R = 1 2 , where 1 is "ter-
restrial" (4), and 2 is "aerial" (k). • Each PlatformType instance is associated with
a set of Trafficability instances representing the
• The assignment ⎛ of traficabilities
⎞ to the edges is the types of environments it is compatible with. Con-
0 2 1 sequently, an agent pattern is compatible with an
matrix RE = ⎝2 0 1⎠. For instance the path edge if and only if the edge trafficability belongs to
1 1 0 the agent pattern platform type set of compatible
(1, 2) has the trafficability 2 ("aerial"), whereas the traficabilities.
path (2, 3) has the trafficability 1 ("terrestrial").
3.2. Formalization
3. Agent Configuration Problem
We first formalize the inputs of the agent configuration
In this section, we present the model associated with the problem and then define the decision variables. We next
Agent Configuration Problem (ACP), which consists in present some assumptions on the problems we consider
deciding agents’ composition wrt. a catalog of platform and finally illustrate the concepts on the toy example.
* * • Task Reachability. For each task, there exists a
Trafficability Capability
platform type and a path from the base to the task’s
vertex such that the platform type is compatible
Catalog with all the path’s edges trafficabilities. Formally,
1..* 1 1..* ∀i ∈ [1..nT ], ∃ j ∈ [1..nP ], ∃k ∈ N∗ , (v1 , . . . , vk ) ∈
[1..nV ]k , s. t.
PlatformType EquipmentType
1 ACP 1 v1 = 1, vk = tvi (7)
Platform Equipment ∀r ∈ [1..k − 1]2 , evr ,vr+1 = 1 (8)
1 output * rp j,revr ,vr+1 = 1 (9)
AgentPattern
Those two assumptions ensure that for each task in the
mission, there exists an agent pattern compatible with the
Legend
task perform it.
ACP Input
ACP Decision
3.2.3. Decision Variables
Figure 4: UML representation the ACP. We present here the decision variables that must be as-
signed a value when solving an ACP. To do so, we first
formally define an agent pattern.
3.2.1. Inputs For a given catalog cat, an agent pattern is a tuple
acat = (ap, AQ) where :
Let m be a mission. A catalog on m is a tuple catm =
(P, Q, maxQ , RP, CQ) where: • ap is an integer in [1..nP ] that represents the plat-
form of catalog cat associated with acat .
• P = (1, . . . , nP ) is the platform types vector,
• Q = (1, . . . , nQ ) is the equipment types vector, • AQ = (aqi )i∈[1..nQ ] is the acat equipment vector of
size nQ . For all equipment type i ∈ [1..nQ ], aqi is
• maxQ ∈ N∗ is an upper bound on the number of in- an integer in [1..maxQ ] that represents the number
stances of each equipment type that can be carried of equipment type i present in acat .
by an agent pattern,
For a given catalog cat, the objective of ACP is to
• RP = (rpi, 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 ], rpi, j = 1 if the As we do not consider any constraint in this paper,
platform type i is compatible with trafficability j. max
there are nT = nP · nQ Q possible agent patterns. In real
Otherwise, rpi, j = 0. world applications, the 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.
The catalog is the only input of the ACP.
3.3. Toy Problem ACP
3.2.2. Assumptions
We consider the mission m defined in Subsection 2.3.
A catalog cat should satisfy the following assumptions.
We define the catalog cat the following way.
• Task Feasibility. For each task, there is at least (︁ )︁
one equipment type in the catalog that provides its • The platform types vector is P = 1 2 , where
capability, which translates into: 1 is "UAV" (Ê) and 2 is "rover" ().
(︁ )︁
nQ • The equipment types vector is Q = 1 2 , where
∀ j ∈ [1..nT ], ∑ cqi,ct j ≥ 1 (6) 1 is "camera" () and 2 is "trunk" ().
i=1
1 4.1. Description
Stock Fig. 5 contains a UML representation of the Fleet Config-
* * uration Problem. The FCP class takes as an input the set
Platform Equipment of AgentPattern computed by the ACP, as presented in
the previous section. Its output is a Fleet, i.e. a collection
1 * of Agents, where each Agent is associated to a unique
AgentPattern AgentPattern.
In order to model the fact that equipment and platform
* 1
are available in limited quantities, we define the class
FCP Agent Legend Stock. Such a class is associated to a set of Platforms
1..*
ACP Solution and a set of Equipments. The FCP takes an instance of
FCP Input Stock as an input. Even if it is clear that the stock will
output
Fleet FCP Decision impose hard constraints on FCP, the precise formalization
of these constraints is left for future work.
Figure 5: UML representation of the FCP.
4.2. Formalization
We first formalize the inputs of the agent configuration
• the maximum number for each equipment instance problem, then define the decision variables and illustrate
on an agent pattern is maxQ = 1. the formalization on the toy example.
• The platform/trafficability compatibility matrix is
(︃
0 1
)︃ 4.2.1. Inputs
RP = . In this example, rp1,2 = 1 holds,
1 0 Let cat be a catalog. The FCP associated to this catalog
meaning that platform 1 ("UAV") is compatible has two inputs:
with the trafficability 2 ("aerial"). However, as
rp1,1 = 0, platform 1 is not compatible trafficabil- • A stock associated with cat, denoted scat , and de-
ity 1 ("terrestrial"). fined by a pair (Ps , Qs ) where:
– Ps = (pi )i∈[1..nP ] is a vector of size nP such
• The(︃ equipment/capability relation matrix is CQ =
)︃ that for each platform type i ∈ [1..nP ] in cat,
1 0
. In this example, rp1,1 = 1 holds, mean- pi ∈ N∗ defines how many type i platform
0 1
instances are in the stock.
ing that the equipment 1 ("camera") provides the
capability 2 ("observe"). However, rp1,2 = 0, – Qs = (q j ) j∈[1..nQ ] is a vector of size nQ
which means that this equipment does not provide such that for each equipment type j ∈
capability 2 ("carry"). [1..nQ ] in cat, q j ∈ N∗ defines how many
type j equipment instances are in the stock.
The two following agent patterns belong to Tcat :
(︁ )︁ • A vector of agents pattern Tcat . Such a vector can
• a1 = (1, 1 0 ) is a UAV equipped with one for instance come from the output resulting from
camera and zero trunk. the ACP solving.
(︁ )︁
• a2 = (2, 1 1 ) is a rover equipped with one
4.2.2. Decision Variables
camera and one trunk.
Given a catalog cat, a stock scat on this catalog, and Tcat
There is a total of nT = 6 possible agent patterns (Tcat =
a vector of the agent patterns, a fleet is a tuple fscat ,Tcat =
(a1 , . . . , a6 )).
(na , Af ) where:
• na is the size of the fleet.
4. Fleet Configuration Problem
• Af = (ai )i∈[1..na ] is the finite vector of size na of
In this section, we present the model associated with the agents in the fleet such as, for each i ∈ [1..na ], ai ∈
Fleet Configuration Problem (FCP), which aims at decid- [1..nT ] is the index of the agent pattern of the
ing the composition of the fleet wrt. the available stock. 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.
4.3. Toy Problem FCP 1
Mission
We consider the mission m defined in Subsection 2.3, 1
the catalog cat and the agent patterns Tcat defined in
Subsection 3.3. output *
PCP Plan AgentPlan
We define the stock scat the following way.
(︁ )︁
• The platform instance vector is Ps = 2 1 ,
1 Legend
meaning that there are 2 instances of type 1 plat- 1 *
form ("UAV" - Ê) and 1 instance of type 2 plat- Fleet Agent FCP Solution
form ("rover" - ) in the stock. PCP Input
(︁ )︁ PCP Decision
• The equipment instances vector is Qs = 2 1 .
In this example, there are two instances of type Figure 6: UML representation of the PCP.
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 • a mission m,
agents. For instance, we define two fleets as follows:
• a fleet fscat ,Tcat .
• f1scat ,Tcat = (1, (a2 )), is a fleet composed of a single
agent with the pattern a2 (a rover equipped with 5.2.2. Decision Variables
one camera and one trunk - + + ).
In order to represent the position of each agent in the so-
• f2scat ,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 =
5. Plan Configuration Problem (H, Tpl, Vpl) where:
In this section, we present the model associated with the • H ∈ N∗ is the temporal plan horizon.
Plan Configuration Problem (PCP), which aims at decid-
ing the agents’ positions and tasks all along the mission. • Tpl = (tpli, j,h )i, j,h∈[1..na ]×[1..nT ]×[1..H] is the allo-
cation of tasks over agents for each time steps,
represented as a tensor of size na · nT · H. For
5.1. Description each agent i ∈ [1..na ], each task j ∈ [1..nT ] and
The plan configuration is the last problem to solve in order each time step h ∈ [1..H], tpli, j,t = 1 if the agent
to get a solution for the multi-level configuration problem. ai ∈ Af is executing the task j at the time h. It
As illustrated on Fig. 6, it takes as input a Mission and a equals 0 otherwise.
Fleet. Its output is a Plan which consists of an AgentPlan
• Vpl = (vpli, j,h )i, j,h∈[1..na ]×[1..nV ]×[1..H] is the posi-
for each Agent in the fleet. For each agent in the fleet, an
tion of the agents for each time steps, defined by a
AgentPlan describes exhaustively at any given time step
tensor of size na · nT · H. For each agent i ∈ [1..na ],
the position of the agent and the task currently executed,
each task j ∈ [1..nT ] and each time step h ∈ [1..H],
if any.
vpli, j,t equals 1 if the agent ai ∈ Af is at the vertex
j at the time h. It equals 0 otherwise.
5.2. Formalization
Through this plan formalization, moves of agents are
We first formalize the inputs of the plan configuration not explicitly described, but this piece of information
problem and then define the decision variables. could be retrieved through their positions.
5.2.1. Inputs
5.3. Toy problem PCP
For a catalog cat, a stock on this catalog, scat , the PFD
We consider the definitions of mission m, catalog cat,
associated to this stock requires two additional inputs:
introduced in the three previous examples.
Ê Ê Ê
☼
k
r k
r k
r
Ê Ê Ê
4 4 4
c c c
4 4 4
_ _ _
g
(a) Step 1 (b) Step 2 (c) Step 3
Figure 7: Execution of plan plm, fs ,T from Example 5.3: starting from the base, the UAV moves to the ruins while the rover
cat cat
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 6. Conclusion
fs2cat ,Tcat = (2, (a1 , a2 )):
In this paper, we model and formalize the multi-level
(︁ )︁ (︁ )︁
plm, fscat ,Tcat = (3, Tpl1 Tpl2 ), Vpl1 Vpl2 ), il- configuration problem for a fleet of heterogeneous agent.
lustrated in Fig. 7, where: This problem is decomposed into three problems, ACP,
(︃ )︃ FCP and PCP and for each of them, we formally define
0 1 0 their inputs and their decision variables and we illustrate
• Tpl1 = is the task allocation matrix
0 0 0 them on a toy problem. We focus on Search and Rescue
of the first agent of the fleet, that has pattern a1 missions where tasks have to performed on some nodes
(platform Ê). It performs the task "explore the of a given graph.
ruins" (☼) at time step 2. The work presented in this paper is a first step for solv-
⎛
1 0 1
⎞ ing the multi-level configuration problem. As mentioned
• Vpl1 = ⎝0 1 0⎠ describes the movement of in the paper, the next step is to formally define the set of
0 0 0 constraints and the eventual criteria associated to ACP,
the first agent of the fleet, that has pattern a1 . It FCP and PCP. To do so, it will be possible to study the
starts at the "base" (c) than goes to the "ruins" literature associated with each problem, such as [1] for
(r) and comes back to the "base" (c). ACP, [3, 6] for FCP and [7, 8, 9] for PCP.
(︃ )︃ Then, we have presented the three configuration prob-
0 0 0 lems independently but in practice, they are interleaved.
• Tpl2 = is the task allocation matrix
0 1 0 For instance the output of ACP is an input of FCP, and the
of the second agent of the team, with pattern a2 output of FCP is an input for PCP. In the other direction,
(platform ). It performs the task "deliver sup- the evaluation of solutions produced by PCP and FCP can
plies" (g) at the time step 2. influence the choices made in ACP. If the evaluation of
⎛ ⎞ the overall multi-level configuration solution is not satis-
1 0 1
factory, there might be several interactions between each
• Vpl2 = ⎝0 0 0⎠ describes the movement of
level before converging (if any convergence is possible).
0 1 0
In order to avoid these interactions, it would be possible
the second agent of the team, with pattern a2 . It
to solve all the configuration problems simultaneously.
starts at the "base" (c) than goes to the "aid camp"
Some works have started contributing towards that ob-
(_) and comes back to the "base" (c).
jective [10, 11, 12, 2]. Following those works, we aim
Note that the time steps used in that example plan give at proposing a global solver/architecture for solving the
a macro view of the agents actions. It would be possible multi-level configuration problem.
to have a much finer discretization of the time in order to Finally, we have considered here a simple model of
handle temporal constraints such as task duration, or edge a Search and Rescue mission. It would be possible to
traversal duration. 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 forc-
ing 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, Opti-
requiring synchronisation between multiple agents), a mization model to assess electric vehicles as an al-
non-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
fleet composition problem, IFAC-PapersOnLine
Acknowledgments 51 (2018) 582–587.
[12] H. R. Sayarshad, R. Tavakkoli-Moghaddam, Solv-
The 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 fleet sizing by two-stage optimization formula-
work. 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.
References
[1] É. Vareilles, S. Roussel, G. Picard, PERFECT: per-
formant and robust read-to-fly fleet configuration:
from robot to mission plan, in: J. M. Horcas, J. A.
Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Pro-
ceedings of the 25th International Workshop on Con-
figuration (ConfWS 2023), Málaga, Spain, Septem-
ber 6-7, 2023, volume 3509 of CEUR Workshop
Proceedings, CEUR-WS.org, 2023, pp. 104–107.
[2] C. Lei, W.-H. Lin, L. Miao, A two-stage robust opti-
mization approach for the mobile facility fleet sizing
and routing problem under uncertainty, Computers
& Operations Research 67 (2016) 75–89.
[3] G. Weiss, Multiagent systems, Second Edition, MIT
press, 2013.
[4] G. Radzki, P. Golinska-Dawson, G. Bocewicz,
Z. Banaszak, Modelling robust delivery scenarios
for a fleet of unmanned aerial vehicles in disaster
relief missions, Journal of Intelligent & Robotic
Systems 103 (2021) 1–18.
[5] T. Calamoneri, F. Corò, S. Mancini, A realistic
model to support rescue operations after an earth-
quake via uavs, IEEE Access 10 (2022) 6109–6125.
[6] J. F. Hübner, J. S. Sichman, O. Boissier, Moise+
towards a structural, functional, and deontic model
for mas organization, in: Proceedings of the first in-
ternational joint conference on Autonomous agents
and multiagent systems: part 1, 2002, pp. 501–502.
[7] J. Blythe, An overview of planning under uncer-
tainty, Artificial Intelligence Today: Recent Trends
and Developments (2001) 85–110.
[8] Ç. Koç, T. Bektaş, O. Jabali, G. Laporte, Thirty
years of heterogeneous vehicle routing, European
Journal of Operational Research 249 (2016) 1–21.
[9] L. Berghman, Y. Kergosien, J.-C. Billaut, A re-
view on integrated scheduling and outbound vehicle
routing problems, European Journal of Operational
Research 311 (2023) 1–23.