2023

[1]Charlie Street

1]School of Computer Science, University of Birmingham, UK

2]Oxford Robotics Institute, University of Oxford, UK

# Formal Modelling for Multi-Robot Systems Under Uncertainty

<EMAIL_ADDRESS>Masoumeh Mansouri<EMAIL_ADDRESS>Bruno Lacerda
<EMAIL_ADDRESS>[  [

###### Abstract

Purpose of Review: To effectively synthesise and analyse multi-robot
behaviour, we require formal task-level models which accurately capture multi-
robot execution. In this paper, we review modelling formalisms for multi-robot
systems under uncertainty, and discuss how they can be used for planning,
reinforcement learning, model checking, and simulation.
Recent Findings: Recent work has investigated models which more accurately
capture multi-robot execution by considering different forms of uncertainty,
such as temporal uncertainty and partial observability, and modelling the
effects of robot interactions on action execution. Other strands of work have
presented approaches for reducing the size of multi-robot models to admit more
efficient solution methods. This can be achieved by decoupling the robots
under independence assumptions, or reasoning over higher level macro actions.
Summary: Existing multi-robot models demonstrate a trade off between
accurately capturing robot dependencies and uncertainty, and being small
enough to tractably solve real world problems. Therefore, future research
should exploit realistic assumptions over multi-robot behaviour to develop
smaller models which retain accurate representations of uncertainty and robot
interactions; and exploit the structure of multi-robot problems, such as
factored state spaces, to develop scalable solution methods.

###### keywords:

Multi-Robot Systems, Markov Models, Uncertainty

##  1 Introduction

The demand for multi-robot systems (MRSs) is increasing, due to their
performance, flexibility, and fault tolerance iocchi2000reactivity ;
yan2013survey . Successful multi-robot deployments have been completed in a
range of domains, such as fulfilment centres ocadocfc , fruit fields
khan2020incorporating , and roads robotaxifleet . For safe and robust multi-
robot coordination in the real world, it is often desirable to consider
_formal models_ of the MRS, which enable policy synthesis for well-defined
objectives, as well as a formal analysis of such policies. In this review
paper, we consider formal models that capture the task-level behaviour of the
MRS. These model high-level capabilities such as navigation or manipulation,
while abstracting the lower-level control required to implement these
capabilities. Formal models are used alongside multi-robot planning
boutilier1996planning  and reinforcement learning (RL) bucsoniu2010multi
techniques to synthesise robot behaviour, and alongside model checking
herd2015quantitative  and simulation damas2004stochastic  techniques to
evaluate task-level metrics of multi-robot performance. However, the success
of these techniques is limited by the model’s accuracy, in particular its
capacity to capture and predict execution-time multi-robot behaviour
baier2008principles . For example, if we plan on an inaccurate model, our
expectations of robot behaviour during planning diverge from what is observed
during execution, which can lead to inefficient execution-time behaviour, or
robot failure in the worst case.

In this paper, we focus on modelling the _stochasticity_ of MRSs as, in any
environment, robot behaviour is affected by the stochastic dynamics of the
environment and the other robots. For example, a mobile robot operating in an
office may fail to navigate upon a door being closed unexpectedly; or it may
be unable to dock at a charging station if another robot is charging for
longer than expected. We begin by introducing the types of uncertainty
encountered by MRSs, including uncertainty over action outcomes
puterman1994mdp , a robot’s current state kaelbling1998planning , and the
duration and start time of robot actions boyan2001exact ; street2022context .
Next, we review modelling formalisms which capture these sources of
uncertainty. We then describe how formal multi-robot models have been used to
support advances in the application of planning, RL, model checking, and
simulation techniques to MRSs.

##  2 Uncertainty in Multi-Robot Systems

In this section, we outline the common forms and sources of uncertainty
experienced by MRSs.

Outcome Uncertainty. Robot uncertainty is most commonly captured over discrete
action outcomes puterman1994mdp , such as whether a grasp action is executed
successfully. Stochastic outcomes can occur due to robot navigation failure
ma2017multi , battery depletion tomy2020battery , or stochastic features of
the environment such as hazards tihanyi2021multi , resources
de2018preallocation , and doors deng2017approximate .

Partial Observability. In some MRSs, robots only partially observe the
environment, which prevents them from knowing each other’s states. This is
often caused by limited communication and sensing capabilities, such as
imperfect localisation vanegas2017uav , limited network range
capitan2013decentralized , or object occlusion hubmann2019pomdp . Under
partial observability, robots form a _belief_ over the true state of the
environment and other robots using possibly noisy observations obtained from
sensors.

Temporal Uncertainty. Sources of temporal uncertainty affect the duration and
start time of robot actions during execution street2021congestion ;
zhang2017multirobot ; boyan2001exact . Temporal uncertainty occurs in almost
any robot environment, where action durations are affected by environmental
disturbances, such as unknown obstacles or adverse weather conditions. For
example, a mobile robot’s tire may slip on a carpet while navigating through
an office, slowing it down. Further, robots may have to wait for stochastic
temporal processes in the environment, such as order arrival in a fulfilment
centre, before beginning task execution claes2017decentralised .

The Effect of Robot Interactions. A particularly relevant driver of
uncertainty in MRSs is the fact robots typically share resources, such as
space or access to a charging station, and must interact with each other
street2022context . For example, when multiple mobile robots navigate in the
same physical space simultaneously, they may experience _congestion_ , which
increases uncertainty over action duration street2021congestion .
Alternatively, a robot manipulator may be more likely to fail a grasp if
another robot is nearby, restricting its movement.

##  3 Formal Multi-Robot Models

In this section, we review modelling formalisms for MRSs, which we summarise
in Table 1. At their foundation, each of these models consists of _states_ ,
which describe a snapshot of the MRS and environment, and _transitions_
between states, which define the system dynamics.

###  3.1 Classical Multi-Robot Models

_Joint transition systems (JTSs)_ model MRSs with deterministic dynamics
baier2008principles ; gujarathi2022mt ; ulusoy2013optimality ;
kloetzer2011multi ; kantaros2020stylus . JTS states are often factored into
local states for each robot, e.g. their location and battery level, and a
shared set of global state features, such as whether doors in the environment
are open. JTSs are fully deterministic, and so fail to capture the stochastic
dynamics of real robot environments. _Multi-agent Markov decision processes
(MMDPs)_ are a natural extension of JTSs to stochastic domains
boutilier1996planning . Similar to JTSs, MMDPs capture robots in a joint state
and action space, but MMDP actions have probabilistic outcomes. MMDPs are a
common formalism for MRSs, and have been used to model drone fleets
choudhury2022scalable , warehouse robots claes2017decentralised , and human-
robot teams unhelkar2020semi . MMDPs and JTSs assume synchronous execution,
i.e. robots execute their actions in lockstep, and all actions have the same
duration. Further, the joint state and action spaces yield an exponential
blow-up in the number of robots being modelled. In practice, robot action
durations are inherently continuous and uncertain, where robot interactions
contribute towards this uncertainty street2021congestion ; street2022context ;
zhang2017multirobot ; messias2013gsmdps ; de2015intention . Thus, to
accurately capture multi-robot behaviour, we require formalisms which model
asynchronous multi-robot execution and uncertainty over action duration. One
approach for explicitly doing this is to use continuous-time Markov models,
which we discuss later in this section.

###  3.2 Avoiding the Exponential Scalability of Joint Models

The number of MMDP or JTS states and actions increase exponentially in the
number of robots boutilier1996planning , which makes optimal solutions for
planning kolobov2012planning , RL sutton2018reinforcement , and model checking
baier2008principles  intractable. This can be improved by making different
assumptions which simplify the model. In fact, there has been a significant
research effort to identify realistic assumptions for specific multi-robot
problems. _Transition-independent MMDPs (TI-MMDPs)_ scharpff2016solving  and
_constrained MMDPs (CMMDPs)_ de2021constrained  assume the transition dynamics
of each robot are independent, but couple the MRS through rewards and shared
resources, respectively. _Team MMDPs_ faruq2018simultaneous  also treat the
transition dynamics independently, modelling robots sequentially in the
context of simultaneous task allocation and planning problems. Transition
independence assumptions allow for weakly-coupled models that operate outside
of the joint state and action space and reduce the model size, thus
facilitating the use of more efficient solution methods. However, in cases
where execution-time robot interactions affect the outcome and duration of
robot actions, the transition-independent models above are unable to
accurately reflect the MRS.

For many multi-robot problems, robots can act independently for the majority
of execution, as interactions are sparse. For example, two robots conducting a
handover can ignore each other until they are close. _Interaction-driven
Markov games (IDMGs)_ spaan2008interaction  and _decentralised sparse
interaction MDPs (Dec-SIMDPs)_ melo2011decentralized ; melo2013heuristic
exploit this to reduce the space complexity whilst still accounting for
execution-time interactions. IDMGs and Dec-SIMDPs are equivalent, and capture
an MRS using an independent MDP per robot, and a set of interaction MMDPs,
which define joint MRS behaviour in interaction areas, such as near a doorway.
Though interaction MMDPs are joint models, they are significantly smaller than
the full MMDP, as they are defined over only a small fraction of the full MMDP
state space. However, these models are only useful when interactions are
localised to a small, fixed part of the environment. If this does not hold,
they become equivalent to the full MMDP.

Finally, a commonly used approach to avoid the use of joint models while still
considering robot dependencies and execution-time interactions is to model the
MRS as a set of single-robot models that are extended to include some
knowledge of the other robots. In claes2015effective ; claes2017decentralised
, _spatial task allocation problems (SPATAPs)_ are modelled using single-robot
models which aggregate the response of the other robots. The aggregate
response is represented as a distribution which predicts whether any robot is
present at a given location. This is computed by combining individual
distributions over each robot’s location, and allows robots to predict which
tasks will be handled by other robots during planning. A similar approach is
taken in street2021congestion , where an MRS is modelled using single-robot
_time-varying Markov automata (TVMA)_ which capture the probabilistic effects
of congestion caused by the other robots. In this context, congestion is
represented as a distribution over the number of robots present in each area
of the environment, and distributions of navigation duration under the
presence of a specific number of robots are obtained from real-world multi-
robot navigation data. To solve multi-robot planning problems,
zhang2017multirobot  augment single-robot models with a cost function which
captures the effects of robot interactions. This cost function is then
adjusted iteratively during planning to encourage robot collaboration.

###  3.3 Partially Observable Multi-Robot Models

Partially observable MDPs (POMDPs) are widely used to model partially
observable problems, where robots make observations which update their belief
over their current state kaelbling1998planning . _Decentralised POMDPs (Dec-
POMDPs)_ extend POMDPs to multi-robot settings bernstein2002complexity , where
each robot has its own set of local observations. Dec-POMDPs have been used
for warehouse robotics amato2015planning , cooperative package delivery
omidshafiei2017decentralized , and teams of unmanned aerial vehicles
floriano2019planning . If the combined local observations of each robot
uniquely identify the joint state, Dec-POMDPs are reduced to Dec-MDPs, which
are easier to solve bernstein2002complexity . However, these are still joint
models, and optimal solvers for both Dec-POMDPs and Dec-MDPs have even higher
time complexity than MMDP solvers bernstein2002complexity . To reduce the
space complexity related to the joint modelling in Dec-POMDPs,
oliehoek2012influence ; oliehoek2021sufficient  consider decoupling them into
local POMDPs for each robot. For each of these local POMDPs, they compute a
distribution which captures how external state factors influence its local
state. These external state factors include the states of the other robots.
This is then used to marginalise out the external state factors to construct
single-robot POMDPs. This influence-based abstraction produces smaller models.
However, computing influence distributions is intractable in general
oliehoek2021sufficient .

Another class of relevant POMDP-based models are _macro action Dec-POMDPs
(MacDec-POMDPs)_ amato2019modeling  and _decentralised partially observable
semi-MDPs (Dec-POSMDPs)_ omidshafiei2017decentralized , which consider macro
actions which execute a series of primitive low-level actions, such as moving
one grid cell forward. This hierarchical paradigm is based on the options
framework sutton1999between  for MDPs and has two main benefits. First, it
reduces model size by leveraging existing behaviour such as navigation, and
modelling behaviour at the macro action level, rather than each time step.
Second, the use of temporally extended actions seamlessly enables asynchronous
action execution. Each MacDec-POMDP and Dec-POSMDP has an underlying Dec-POMDP
which captures the low-level actions that form the macro actions. For MacDec-
POMDPs, the underlying Dec-POMDP and the policies for each macro action are
assumed to be known amato2018decision . MacDec-POMDP policies can then be
evaluated by unrolling the macro actions on the low-level Dec-POMDP. Unlike
MacDec-POMDPs, Dec-POSMDPs capture macro actions using distributions over
their completion time, where Dec-POSMDP policies can be evaluated through
simulation.

###  3.4 Continuous-Time Multi-Robot Models

Several models have been proposed to take into account uncertainty over action
duration in the context of MRSs which are evolving asynchronously. These make
use of continuous-time distributions which capture the stochasticity in robot
action durations. _Continuous-time MDPs (CTMDPs)_ extend MDPs to include
durative transitions represented as exponential delays guo2009continuous , and
have been used to model multi-robot data collection problems yin2011continuous
. To model asynchronous multi-robot execution, CTMDPs can be defined over a
joint state and action space, similar to MMDPs. Thus, as with MMDPs, they
scale exponentially in the number of robots. To mitigate this,
yin2011continuous  constructs single-robot CTMDPs assuming transition
independence, similar to scharpff2016solving ; de2021constrained . The
duration of each action in a CTMDP is modelled with a single exponential
distribution. This is a convenience which allows for simpler solution
approaches which exploit the memoryless property of the exponential
distribution, but limits the accuracy with which we can capture robot action
durations.

Many multi-robot models can capture _heterogeneous_ MRSs (see Table 1), where
robots have different capabilities and resource usage etc. This is often
achieved using local action spaces or reward functions for each robot.
_Generalised stochastic Petri nets (GSPNs)_ balbo2007introduction  are a
modelling formalism for _homogeneous_ MRSs, i.e. the robots are identical,
where robots are represented _anonymously_ as tokens. Further, as in CTMDPs,
durations are restricted to exponentials. GSPNs remain exponential in the team
size, but robot anonymity provides a practical reduction in the number of
states. GSPNs have been used to model teams of football robots Costelha2012 ,
autonomous haulers mansouri2019multi , and monitoring robots azevedo2020iros .
_Generalised semi-MDPs (GSMDPs)_ can capture concurrent execution and
stochastic durations, and have been applied to MRSs in younes2004solving ;
messias2013gsmdps , but are complex to define and hard to solve, as GSMDPs
allow for arbitrary duration distributions. _Multi-robot Markov automata
(MRMA)_ street2022context  also allow for arbitrary duration distributions to
capture asynchronous multi-robot execution in continuous time. Markov automata
(MA) extend MDPs and CTMDPs by explicitly separating instantaneous robot
action choice and the duration of robot actions eisentraut2010probabilistic .
MRMA are joint models, where robot action durations are represented as phase-
type distributions (PTDs), which are sequences of exponentials capable of
capturing any nonnegative distribution to an arbitrary level of precision
buchholz2014input . In an MRMA, there is a different duration distribution for
each spatiotemporal situation an action may be executed under, referred to as
the _context_ , which captures the effects of robot interactions on action
execution. By separating robot decision making from action duration, robot
interactions can be detected at the instant an action is triggered by
analysing the joint MRMA state. MRMA are connected to other continuous-time
multi-robot models. First, GSPN semantics can be described with an MA
eisentraut2013petrinets . Second, a standard solution for GSMDPs involves
converting all duration distributions into PTDs buchholz2014input , which
produces a model similar to an MRMA younes2004solving . However, MRMA are
simpler to define, and can be solved directly hatefi2012model , as all
durations are exponentials/PTDs by definition.

Table 1: A summary of multi-robot modelling formalisms. Model |  Stochastic Outcomes |  Partial Observability |  Temporal Uncertainty |  Continuous Time |  Transition Independence |  Asynchronous Execution |  Allows for Heterogeneous Teams
---|---|---|---|---|---|---|---
JTS baier2008principles  | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓
MMDP boutilier1996planning  | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓
TI-MMDP scharpff2016solving  | ✓ | ✗ | ✗ | ✗ | ✓ | ✗ | ✓
CMMDP de2021constrained  | ✓ | ✗ | ✗ | ✗ | ✓ | ✗ | ✓
Team MMDP faruq2018simultaneous  | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓
Dec-SIMDP/IDMG melo2011decentralized ; spaan2008interaction  | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓
SPATAP Model claes2015effective  | ✓ | ✗ | ✗ | ✗ | ✓ | ✗ | ✓
TVMA per Robot street2021congestion  | ✓ | ✗ | ✓ | ✗ | ✗ | ✓ | ✓
Dec-POMDP bernstein2002complexity  | ✓ | ✓ | ✗ | ✗ | ✗ | ✗ | ✓
MacDec-POMDP amato2019modeling  | ✓ | ✓ | ✓ | ✗ | ✗ | ✓ | ✓
Dec-POSMDP omidshafiei2017decentralized  | ✓ | ✓ | ✓ | ✗ | ✗ | ✓ | ✓
CTMDP guo2009continuous  | ✓ | ✗ | ✓ | ✓ | ✗ | ✓ | ✓
GSPN balbo2007introduction  | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✗
GSMDP younes2004solving  | ✓ | ✗ | ✓ | ✓ | ✗ | ✓ | ✓
MRMA street2022context  | ✓ | ✗ | ✓ | ✓ | ✗ | ✓ | ✓

##  4 Model Applications

Table 2: Applications of the models in Table 1 for multi-robot/multi-agent problems. Model | Planning |  Reinforcement Learning |  Model Checking |  Simulation
---|---|---|---|---
JTS baier2008principles  | gujarathi2022mt ; ulusoy2013optimality ; kloetzer2011multi ; kantaros2020stylus  | - | gujarathi2022mt ; ulusoy2013optimality ; kloetzer2011multi ; kantaros2020stylus  | -
MMDP boutilier1996planning  | boutilier1996planning ; choudhury2022scalable ; NIKOU201710766 ; wongpiromsarn2013incremental  | melcer2022shield ; yang2020multi  | NIKOU201710766 ; wongpiromsarn2013incremental  | -
TI-MMDP scharpff2016solving  | scharpff2016solving  | - | - | -
CMMDP de2021constrained  | dolgov2006resource ; de2017bounding ; de2020risk ; agrawal2016scalable ; de2018preallocation ; 2023AAAI_gautier ; 2023AAMAS_gautier  | lu2021decentralized ; he2022robust  | - | -
Team MMDP faruq2018simultaneous  | faruq2018simultaneous  | - | faruq2018simultaneous  | -
Dec-SIMDP/IDMG melo2011decentralized ; spaan2008interaction  | melo2011decentralized ; melo2013heuristic ; spaan2008interaction  | ganguly2022decentralized ; kujirai2019greedy  | - | -
SPATAP Model claes2015effective  | claes2015effective ; claes2017decentralised  | - | - | -
TVMA per Robot street2021congestion  | street2021congestion  | - | - | -
Dec-POMDP bernstein2002complexity  | floriano2019planning ; omidshafiei2017scalable ; floriano2021hybrid ; lauri2020multi  | rashid2018qmix ; xiao2021local ; jiang2021multi ; lyu2020likelihood ; omidshafiei2019learning ; peng2021facmac ; pan2021regularized ; gupta2021uneven ; willemsen2021mambpo  | - | -
MacDec-POMDP amato2019modeling  | amato2014planning ; amato2015planning ; amato2016policy ; amato2019modeling ; hoang2018near  | xiao2020macro ; xiao2020learning ; liu2017learning ; xiao2022asynchronous  | - | -
Dec-POSMDP omidshafiei2017decentralized  | omidshafiei2017decentralized ; omidshafiei2017scalable ; omidshafiei2017semantic  | - | - | -
CTMDP guo2009continuous  | yin2011continuous ; jia2015continuous  | - | - | -
GSPN balbo2007introduction  | mansouri2019multi ; azevedo2020iros ; azevedo2021petri ; chen2011assembly  | - | - | Costelha2012 ; chen2011assembly
GSMDP younes2004solving  | messias2013gsmdps  | - | - | -
MRMA street2022context  | - | - | - | street2022context

In this section, we discuss how the multi-robot models in Table 1 have been
solved and analysed for multi-robot planning, RL, model checking, and
simulation. We summarise this discussion in Table 2. Note that in Table 2 we
do not list foundational works which apply to more general models, such as
heuristic search approaches for MDPs which can be applied to MMDPs
kolobov2012planning , or MA model checking techniques which can be applied to
MRMA hatefi2012model .

###  4.1 Planning

Multi-robot planning techniques synthesise robot behaviour given a formal
model of the system. Many multi-robot models can be solved with standard
techniques. MMDPs can be solved exactly using MDP solvers such as value or
policy iteration bellman1966dynamic ; howard1960dynamic . However, these
methods solve for all states, making them intractable for joint multi-robot
models. Heuristic and sampling-based methods such as labelled real-time
dynamic programming bonet2003labeled  or Monte-Carlo tree search
kocsis2006bandit  improve upon the limited scalability of exact solvers by
restricting search to promising areas of the state space. Despite reducing the
explored states, heuristic algorithms are slow to converge on large models,
but often provide anytime behaviour such that valid solutions are synthesised
quickly, and improved with time. The poor scalability of MMDP planning
motivates planning on simplified models. For TI-MMDPs scharpff2016solving ,
transition independence allows for compact representations of reward
dependencies in conditional return graphs, which admits efficient solutions.
For Dec-SIMDPs and IDMGs, the single-robot MDPs and interaction MMDPs can be
solved separately using standard solvers such as value iteration
spaan2008interaction . Similarly, the SPATAP models in claes2015effective  are
single-robot MDPs which capture the effects of the other robots, and can be
solved separately. CMMDP approaches typically exploit the fact that only the
resource constraint couples the agents to scale to larger problems. Planning
for CMMDPs has considered a range of constraints over resource consumption,
such as bounding its worst-case dolgov2006resource , considering a chance-
constraint de2017bounding ; 2023AAAI_gautier , and bounding its conditional
value at risk 2023AAMAS_gautier .

MMDPs can be solved tractably if they are sufficiently small. Therefore, in
NIKOU201710766  robots are grouped into clusters based on robot dependencies,
and each cluster is solved as a separate MMDP. Similarly, in
wongpiromsarn2013incremental  robots are incrementally added to an MMDP to
control scalability.

Recent work choudhury2022scalable  has begun to address the poor scalability
of MMDP planning. There, an anytime planner for MMDPs based on Monte Carlo
tree search is presented, where robot dependencies are exploited to decompose
the value function into a set of factors from which the optimal joint action
can be computed. This approach scales to previously intractable problems.

Solution methods for continuous-time multi-robot models differ depending on
the objective. To solve CTMDPs for time-abstract objectives, such as expected
untimed reward, MDP solvers are applied to an embedded time-abstract MDP. For
timed objectives, MDP solvers are instead applied to a uniformised MDP, where
each state has the same expected sojourn time kakumanu1977relation ;
younes2004solving ; butkova2017long . Similarly, GSPNs can be converted to an
MDP mansouri2019multi  or an MA azevedo2020iros  dependent on the objective
and solved with standard techniques. For MRMA, we can plan using MA solution
methods hatefi2012model .

Dec-POMDPs can be solved centrally to synthesise local policies for
decentralised execution, which map from local action-observation histories to
actions floriano2019planning ; omidshafiei2017scalable ; floriano2021hybrid ;
lauri2020multi . With this, local Dec-POMDP policies are robust to
communication limitations and unreliable sensors. Dec-POMDP solutions can be
adapted to MacDec-POMDPs and Dec-POSMDPs to synthesise policies over macro
actions. In amato2014planning , the space of macro-action policies is searched
exhaustively, where efficient simulators improve the scalability of policy
evaluation amato2015planning . This approach scales poorly, which is addressed
in amato2016policy , where a heuristic search method optimises finite state
controllers for each robot. However, MacDec-POMDP and Dec-POSMDP solutions
have not been shown to scale beyond teams of around four robots
amato2019modeling ; omidshafiei2017decentralized .

###  4.2 Reinforcement Learning (RL)

An alternative approach to policy synthesis is RL sutton2018reinforcement .
Planners synthesise behaviour using a model of the system, whereas RL
approaches learn behaviour using data sampled from the environment
kolobov2012planning ; sutton2018reinforcement . Multi-robot RL problems are
formulated assuming an underlying multi-robot model which is unknown prior to
training. Fully observable, centralised problems can be formulated as an MMDP
melcer2022shield ; yang2020multi  and solved using standard RL techniques such
as deep Q-learning mnih2015human . However, these techniques do not scale to
multi-robot problems due to the exponential increase in the state and action
space yang2020multi ; rashid2018qmix . In many settings, decentralised
policies are required due to limited communication or partial observability
rashid2018qmix ; xiao2021local . Here, multi-robot RL can be formulated as a
Dec-POMDP and solved under the paradigm of centralised training with
decentralised execution oliehoek2008optimal , which allows additional state
information not available during execution to be used during training, such as
the joint state. One example of this paradigm is QMix rashid2018qmix , which
uses a mixing network to estimate the joint Q value from single-robot Q
values. RL techniques for Dec-POMDPs are still slow to converge however, and
so MacDec-POMDPs can be used to exploit existing behaviours and improve the
efficiency of learning xiao2020macro ; xiao2020learning ; liu2017learning ;
xiao2022asynchronous .

###  4.3 Model Checking

Model checking techniques evaluate the behaviour induced by robot policies by
systematically checking if a property is satisfied in a formal robot model
baier2008principles . Properties are often specified with temporal logics such
as linear temporal logic (LTL) or continuous stochastic logic (CSL). Similar
to planning, many of the multi-robot models in Table 1 can be verified using
techniques for more general models. For example, LTL formulae can be verified
on JTSs and MMDPs using techniques for transition systems and MDPs
baier2008principles . However, exact LTL model checking approaches compute a
product of the model and an automaton that captures the LTL formula, which
significantly increases the state space, making them unsuitable for multi-
robot problems. MRMA can be model checked against CSL formulae using model
checking techniques for MA hatefi2012model . This also applies to GSPNs, which
can be represented as an MA with identical semantics eisentraut2013petrinets .
Similar CSL model checking techniques are available for CTMDPs
buchholz2011model .

Model checking and planning are often combined to synthesise guaranteed multi-
robot behaviour. For LTL specifications, we can plan over a joint product
automaton, however this quickly becomes intractable. To overcome this,
faruq2018simultaneous  concatenate single robot product automata through
switch transitions in a team MMDP to reduce the state space. For MMDPs, in
wongpiromsarn2013incremental  robots are added incrementally to a product
automaton until the full problem is solved, or a fixed computational budget is
exceeded. Alternatively, in kantaros2020stylus  the product automaton is
explored incrementally through sampling for MRSs modelled as a JTS. Combined
planning and model checking techniques have been used for multi-robot data
gathering gujarathi2022mt ; ulusoy2013optimality , monitoring
kloetzer2011multi , and mobility-on-demand wongpiromsarn2013incremental .

Statistical model checking (SMC) techniques evaluate properties by sampling
through a model given a set of robot policies, which avoids enumerating the
state space legay2010statistical , and bridges the gap between model checking
and simulation techniques, which we discuss later in this section. In
herd2015quantitative , SMC is used to evaluate quantitative properties of an
MRS. SMC techniques can be applied to many of the models in Table 1. For
example, we can use SMC techniques for MA butkova2021modest  to evaluate
bounded or unbounded properties on an MRMA. A drawback of SMC is a possible
failure to explore states reached with low probability, which can render SMC
unsuitable for safety critical systems butkova2021modest .

###  4.4 Simulation

Simulators evaluate multi-robot behaviour by executing a set of robot policies
in an abstracted environment model. Using formal multi-robot models, we can
create a discrete-event simulator (DES) by sampling stochastic outcomes and
durations, and resolving non-determinism using robot policies. DESs mitigate
the complexity of physics-based simulators such as Gazebo koenig2004design  by
abstracting away low-level robot dynamics bakker2013rams , allowing
simulations to run magnitudes faster than real time. GSPNs, or variants
thereof, have been used to simulate teams of football robots Costelha2012  and
human-robot manufacturing teams chen2011assembly , respectively. In
street2022context , a DES called CAMAS (context-aware multi-agent simulator)
samples through an MRMA to evaluate task-level metrics of multi-robot
performance under the effects of robot interactions, such as the time to
complete a set of tasks.

##  5 Conclusions

In this paper, we reviewed modelling approaches for capturing the task-level
behaviour of MRSs. We focused on stochastic models of multi-robot execution,
and introduced the different types of uncertainty encountered by MRSs.
Further, we discussed how these models have been used for multi-robot
planning, RL, model checking, and simulation. Recent research has focused on
constructing models which accurately capture the effects of uncertainty and
robot interactions, or constructing models small enough to be solved
efficiently. These two objectives are opposing, as to accurately capture
multi-robot execution, we often require joint models which are frequently
intractable to solve or analyse. Therefore, future research should focus on
developing smaller multi-robot models which still accurately capture
uncertainty and robot interactions. This may be achieved by identifying
realistic assumptions over the sources of uncertainty and robot interactions,
such as interactions only occurring in small portions of the state space.
Exploiting these assumptions allows for smaller models which can be solved
efficiently without sacrificing model accuracy. An alternative avenue for
research is to exploit the structure of multi-robot problems, such as factored
state spaces and dependencies between robots, to develop scalable solution
methods for multi-robot models.

Acknowledgments Charlie Street and Masoumeh Mansouri are UK participants in
Horizon Europe Project CONVINCE, and supported by UKRI grant number 10042096.
Bruno Lacerda is supported by the EPSRC Programme Grant ‘From Sensing to
Collaboration’ (EP/V000748/1).

## Declarations

Conflict of Interest The authors declare no competing interests. Human and
Animal Rights and Informed Consent This article does not contain any studies
with human or animal subjects performed by any of the authors.

## Important References

In this section, we highlight recently published papers of particular
interest.

### Important

  * •

de2021constrained : This paper provides a comprehensive taxonomy of CMMDP
problems and solutions, and is an effective starting point for new researchers
in the area.

  * •

oliehoek2021sufficient : This paper formalises influence-based abstraction for
decomposing Dec-POMDPs into single-robot models without sacrificing task
performance.

### Very Important

  * •

street2022context : This paper introduces MRMA, the first formulation to
explicitly capture the effects of execution-time robot interactions on action
duration, as well as CAMAS, which samples through an MRMA to evaluate task-
level metrics of multi-robot performance.

  * •

amato2019modeling : This paper presents MacDec-POMDPs, and extends three Dec-
POMDP solvers to handle macro actions. Further, this paper demonstrates how
planning with macro actions can scale to previously intractable Dec-POMDP
problems.

  * •

rashid2018qmix : This paper presents QMix, a state of the art reinforcement
learning approach for multi-robot problems formulated as a Dec-POMDP.

  * •

choudhury2022scalable : This paper presents a state of the art anytime planner
for MMDPs based on Monte Carlo tree search which can solve previously
intractable problems.

## References

  *   * (1) Iocchi L, Nardi D, Salerno M.  Reactivity and Deliberation: A Survey on Multi-Robot Systems.  In: Proceedings of the Workshop on Balancing Reactivity and Social Deliberation in Multi-Agent Systems. Springer; 2000. p. 9–32.
  * (2) Yan Z, Jouandeau N, Cherif AA.  A Survey and Analysis of Multi-Robot Coordination.  International Journal of Advanced Robotic Systems. 2013;10(12):399.
  * (3) Ocado Group.: What is an Ocado CFC?  Available from: https://www.ocadogroup.com/about-us/what-we-do/automated-ocado-customer-fulfilment-centre.
  * (4) Khan MW, Das GP, Hanheide M, Cielniak G.  Incorporating Spatial Constraints into a Bayesian Tracking Framework for Improved Localisation in Agricultural Environments.  In: Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2020. p. 2440–2445.
  * (5) Robotics 24/7 Staff.: AutoX Passes 1000 Vehicle Milestone for Its RoboTaxi Fleet, the Largest in China.  Available from: https://www.robotics247.com/article/autox_passes_1000_robotaxi_fleet_milestone_expands_san_francisco_testing.
  * (6) Boutilier C.  Planning, Learning and Coordination in Multiagent Decision Processes.  In: Proceedings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge (TARK); 1996. p. 195–210.
  * (7) Buşoniu L, Babuška R, De Schutter B.  Multi-Agent Reinforcement Learning: An Overview.  Innovations in Multi-Agent Systems and Applications-1. 2010;p. 183–221.
  * (8) Herd B, Miles S, McBurney P, Luck M.  Quantitative Analysis of Multiagent Systems through Statistical Model Checking.  In: Proceedings of the International Workshop on Engineering Multi-Agent Systems. Springer; 2015. p. 109–130.
  * (9) Damas B, Lima P.  Stochastic Discrete Event Model of a Multi-Robot Team Playing an Adversarial Game.  In: Proceedings of the IFAC/EURON Symposium on Intelligent Autonomous Vehicles. vol. 37. Elsevier; 2004. p. 974–979.
  * (10) Baier C, Katoen JP.  Principles of Model Checking.  MIT Press; 2008.
  * (11) Puterman ML.  Markov Decision Processes: Discrete Stochastic Dynamic Programming.  John Wiley & Sons, Inc.; 1994.
  * (12) Kaelbling LP, Littman ML, Cassandra AR.  Planning and Acting in Partially Observable Stochastic Domains.  Artificial Intelligence. 1998;101(1-2):99–134.
  * (13) Boyan JA, Littman ML.  Exact Solutions to Time-Dependent MDPs.  In: Proceedings of Advances in Neural Information Processing Systems (NIPS). MIT Press; 2000. p. 1026–1032.
  * (14) Street C, Lacerda B, Staniaszek M, Mühlig M, Hawes N.  Context-Aware Modelling for Multi-Robot Systems Under Uncertainty.  In: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS); 2022. .
  * (15) Ma H, Kumar TS, Koenig S.  Multi-Agent Path Finding with Delay Probabilities.  In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence; 2017. p. 3605–3612.
  * (16) Tomy M, Lacerda B, Hawes N, Wyatt JL.  Battery Charge Scheduling in Long-Life Autonomous Mobile Robots via Multi-Objective Decision Making Under Uncertainty.  Robotics and Autonomous Systems. 2020;133:103629.
  * (17) Tihanyi D, Lu Y, Karaca O, Kamgarpour M.  Multi-Robot Task Allocation for Safe Planning under Dynamic Uncertainties.  arXiv preprint arXiv:210301840. 2021;.
  * (18) de Nijs F, Spaan M, de Weerdt M.  Preallocation and Planning Under Stochastic Resource Constraints.  In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 32; 2018. .
  * (19) Deng K, Chen Y, Belta C.  An Approximate Dynamic Programming Approach to Multiagent Persistent Monitoring in Stochastic Environments with Temporal Logic Constraints.  IEEE Transactions on Automatic Control. 2017;62(9):4549–4563.
  * (20) Vanegas F, Campbell D, Roy N, Gaston KJ, Gonzalez F.  UAV Tracking and Following a Ground Target Under Motion and Localisation Uncertainty.  In: Proceedings of the IEEE Aerospace Conference. IEEE; 2017. p. 1–10.
  * (21) Capitan J, Spaan MT, Merino L, Ollero A.  Decentralized Multi-Robot Cooperation with Auctioned POMDPs.  The International Journal of Robotics Research. 2013;32(6):650–671.
  * (22) Hubmann C, Quetschlich N, Schulz J, Bernhard J, Althoff D, Stiller C.  A POMDP Maneuver Planner for Occlusions in Urban Scenarios.  In: Proceedings of the IEEE Intelligent Vehicles Symposium (IV). IEEE; 2019. p. 2172–2179.
  * (23) Street C, Pütz S, Mühlig M, Hawes N, Lacerda B.  Congestion-Aware Policy Synthesis for Multirobot Systems.  IEEE Transactions on Robotics. 2022;38(1).
  * (24) Zhang S, Jiang Y, Sharon G, Stone P.  Multirobot Symbolic Planning Under Temporal Uncertainty.  In: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). International Foundation for Autonomous Agents and Multiagent Systems; 2017. p. 501–510.
  * (25) Claes D, Oliehoek F, Baier H, Tuyls K.  Decentralised Online Planning for Multi-Robot Warehouse Commissioning.  In: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). International Foundation for Autonomous Agents and Multiagent Systems; 2017. p. 492–500.
  * (26) Gujarathi D, Saha I.  MT*: Multi-Robot Path Planning for Temporal Logic Specifications.  In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2022. p. 13692–13699.
  * (27) Ulusoy A, Smith SL, Ding XC, Belta C, Rus D.  Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints.  The International Journal of Robotics Research. 2013;32(8):889–911.
  * (28) Kloetzer M, Ding XC, Belta C.  Multi-Robot Deployment from LTL Specifications with Reduced Communication.  In: Proceedings of the IEEE Conference on Decision and Control and European Control Conference. IEEE; 2011. p. 4867–4872.
  * (29) Kantaros Y, Zavlanos MM.  STyLuS*: A Temporal Logic Optimal Control Synthesis Algorithm for Large-Scale Multi-Robot Systems.  The International Journal of Robotics Research. 2020;39(7):812–836.
  * (30) Choudhury S, Gupta JK, Morales P, Kochenderfer MJ.  Scalable Online Planning for Multi-Agent MDPs.  Journal of Artificial Intelligence Research. 2022;73:821–846.
  * (31) Unhelkar VV, Li S, Shah JA.  Semi-Supervised Learning of Decision-Making Models for Human-Robot Collaboration.  In: Proceedings of the Conference on Robot Learning. PMLR; 2020. p. 192–203.
  * (32) Messias JV, Spaan M, Lima P.  GSMDPs for Multi-Robot Sequential Decision-Making.  In: Proceedings of the 27th AAAI Conference on Artificial Intelligence; 2013. p. 1408–1414.
  * (33) de Weerdt MM, Stein S, Gerding EH, Robu V, Jennings NR.  Intention Aware Routing of Electric Vehicles.  IEEE Transactions on Intelligent Transportation Systems. 2015;17(5):1472–1482.
  * (34) Mausam, Kolobov A.  Planning with Markov Decision Processes: An AI Perspective.  Morgan & Claypool Publishers; 2012.
  * (35) Sutton RS, Barto AG.  Reinforcement learning: An Introduction.  MIT press; 2018.
  * (36) Scharpff J, Roijers D, Oliehoek F, Spaan M, de Weerdt M.  Solving Transition-Independent Multi-Agent MDPs with Sparse Interactions.  In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 30; 2016. .
  * (37) De Nijs F, Walraven E, De Weerdt M, Spaan M.  Constrained Multiagent Markov Decision Processes: A Taxonomy of Problems and Algorithms.  Journal of Artificial Intelligence Research. 2021;70:955–1001.
  * (38) Faruq F, Parker D, Lacerda B, Hawes N.  Simultaneous Task Allocation and Planning Under Uncertainty.  In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2018. p. 3559–3564.
  * (39) Spaan MTJ, Melo FS.  Interaction-Driven Markov Games for Decentralized Multiagent Planning Under Uncertainty.  In: Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS); 2008. p. 525–532.
  * (40) Melo FS, Veloso M.  Decentralized MDPs with Sparse Interactions.  Artificial Intelligence. 2011;175(11):1757–1789.
  * (41) Melo FS, Veloso M.  Heuristic Planning for Decentralized MDPs with Sparse Interactions.  In: Distributed Autonomous Robotic Systems. Springer; 2013. p. 329–343.
  * (42) Claes D, Robbel P, Oliehoek F, Tuyls K, Hennes D, Van der Hoek W.  Effective Approximations for Multi-Robot Coordination in Spatially Distributed Tasks.  In: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). International Foundation for Autonomous Agents and Multiagent Systems; 2015. p. 881–890.
  * (43) Bernstein DS, Givan R, Immerman N, Zilberstein S.  The Complexity of Decentralized Control of Markov Decision Processes.  Mathematics of Operations Research. 2002;27(4):819–840.
  * (44) Amato C, Konidaris G, Cruz G, Maynor CA, How JP, Kaelbling LP.  Planning for Decentralized Control of Multiple Robots Under Uncertainty.  In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). IEEE; 2015. p. 1241–1248.
  * (45) Omidshafiei S, Agha-Mohammadi AA, Amato C, Liu SY, How JP, Vian J.  Decentralized Control of Multi-Robot Partially Observable Markov Decision Processes using Belief Space Macro-Actions.  The International Journal of Robotics Research. 2017;36(2):231–258.
  * (46) Floriano B, Borges GA, Ferreira H.  Planning for Decentralized Formation Flight of UAV Fleets in Uncertain Environments with Dec-POMDP.  In: Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS). IEEE; 2019. p. 563–568.
  * (47) Oliehoek F, Witwicki S, Kaelbling L.  Influence-Based Abstraction for Multiagent Systems.  In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 26; 2012. p. 1422–1428.
  * (48) Oliehoek F, Witwicki S, Kaelbling L.  A Sufficient Statistic for Influence in Structured Multiagent Environments.  Journal of Artificial Intelligence Research. 2021;70:789–870.
  * (49) Amato C, Konidaris G, Kaelbling LP, How JP.  Modeling and Planning with Macro-Actions in Decentralized POMDPs.  Journal of Artificial Intelligence Research. 2019;64:817–859.
  * (50) Sutton RS, Precup D, Singh S.  Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning.  Artificial Intelligence. 1999;112(1-2):181–211.
  * (51) Amato C.  Decision-Making Under Uncertainty in Multi-Agent and Multi-Robot Systems: Planning and Learning.  In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI); 2018. p. 5662–5666.
  * (52) Guo X, Hernández-Lerma O.  Continuous-Time Markov Decision Processes: Theory and Applications.  Springer-Verlag Berlin Heidelberg; 2009.
  * (53) Yin Z, Tambe M.  Continuous Time Planning for Multiagent Teams with Temporal Constraints.  In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence; 2011. .
  * (54) Balbo G.  Introduction to Generalized Stochastic Petri Nets.  In: Proceedings of the International School on Formal Methods for the Design of Computer, Communication and Software Systems. Springer; 2007. p. 83–131.
  * (55) Costelha H, Lima P.  Robot Task Plan Representation by Petri Nets; Modelling, Identification, Analysis and Execution.  Autonomous Robots. 2012;33(4):337–360.
  * (56) Mansouri M, Lacerda B, Hawes N, Pecora F.  Multi-Robot Planning Under Uncertain Travel Times and Safety Constraints.  In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI); 2019. p. 478–484.
  * (57) Azevedo C, Lacerda B, Hawes N, Lima P.  Long-Run Multi-Robot Planning under Uncertain Action Durations for Persistent Tasks.  In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2020. p. 4323–4328.
  * (58) Younes HL, Simmons RG.  Solving Generalized Semi-Markov Decision Processes using Continuous Phase-Type Distributions.  In: Proceedings of the 19th AAAI Conference on Artificial Intelligence; 2004. p. 742–747.
  * (59) Eisentraut C, Hermanns H, Zhang L.  On Probabilistic Automata in Continuous Time.  In: Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science. IEEE; 2010. p. 342–351.
  * (60) Buchholz P, Kriege J, Felko I.  Input Modeling with Phase-Type Distributions and Markov Models: Theory and Applications.  Springer; 2014.
  * (61) Eisentraut C, Hermanns H, Katoen JP, Zhang L.  A Semantics for Every GSPN.  In: Proceedings of the 34th International Conference on Applications and Theory of Petri Nets and Concurrency (Petri Nets). Springer; 2013. .
  * (62) Hatefi H, Hermanns H.  Model Checking Algorithms for Markov Automata.  Electronic Communications of the EASST. 2012;53.
  * (63) Probabilistic Plan Synthesis for Coupled Multi-Agent Systems.  IFAC-PapersOnLine. 2017;50(1):10766–10771.
  * (64) Wongpiromsarn T, Ulusoy A, Belta C, Frazzoli E, Rus D.  Incremental Synthesis of Control Policies for Heterogeneous Multi-Agent Systems with Linear Temporal Logic Specifications.  In: Proceedings of the IEEE International Conference on Robotics and Automation. IEEE; 2013. p. 5011–5018.
  * (65) Melcer D, Amato C, Tripakis S.  Shield Decentralization for Safe Multi-Agent Reinforcement Learning.  In: Proceedings of the Conference on Neural Information Processing Systems (NeurIPS); 2022. .
  * (66) Yang Y, Juntao L, Lingling P.  Multi-Robot Path Planning Based on a Deep Reinforcement Learning DQN Algorithm.  CAAI Transactions on Intelligence Technology. 2020;5(3):177–183.
  * (67) Dolgov DA, Durfee EH.  Resource Allocation Among Agents with MDP-Induced Preferences.  Journal of Artificial Intelligence Research. 2006;27:505–549.
  * (68) De Nijs F, Walraven E, de Weerdt M, Spaan M.  Bounding the Probability of Resource Constraint Violations in Multi-Agent MDPs.  In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 31; 2017. .
  * (69) de Nijs F, Stuckey PJ.  Risk-Aware Conditional Replanning for Globally Constrained Multi-Agent Sequential Decision Making.  In: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS); 2020. p. 303–311.
  * (70) Agrawal P, Varakantham P, Yeoh W.  Scalable Greedy Algorithms for Task/Resource Constrained Multi-Agent Stochastic Planning.  In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press; 2016. .
  * (71) Gautier A, Lacerda B, Hawes N, Wooldridge M.  Multi-Unit Auctions for Allocating Chance-Constrained Resources.  In: Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI); 2023. .
  * (72) Gautier A, Rigter M, Lacerda B, Hawes N, Wooldridge M.  Risk-Constrained Planning for Multi-Agent Systems with Shared Resources.  In: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS); 2023. .
  * (73) Lu S, Zhang K, Chen T, Başar T, Horesh L.  Decentralized Policy Gradient Descent Ascent for Safe Multi-Agent Reinforcement Learning.  In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 35; 2021. p. 8767–8775.
  * (74) He S, Wang Y, Han S, Zou S, Miao F.  A Robust and Constrained Multi-Agent Reinforcement Learning Framework for Electric Vehicle AMoD Systems.  arXiv preprint arXiv:220908230. 2022;.
  * (75) Ganguly KK, Asad M, Sakib K.  Decentralized Self-Adaptation in the Presence of Partial Knowledge with Reduced Coordination Overhead.  International Journal of Information Technology and Computer Science (IJITCS). 2022;14(1).
  * (76) Kujirai T, Yokota T.  Greedy Action Selection and Pessimistic Q-Value Updating in Multi-Agent Reinforcement Learning with Sparse Interaction.  SICE Journal of Control, Measurement, and System Integration. 2019;12(3):76–84.
  * (77) Omidshafiei S, Amato C, Liu M, Everett M, How JP, Vian J.  Scalable Accelerated Decentralized Multi-Robot Policy Search in Continuous Observation Spaces.  In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). IEEE; 2017. p. 863–870.
  * (78) Floriano BR, Borges GA, Ferreira HC, Ishihara JY.  Hybrid Dec-POMDP/PID Guidance System for Formation Flight of Multiple UAVs.  Journal of Intelligent & Robotic Systems. 2021;101:1–20.
  * (79) Lauri M, Oliehoek F.  Multi-Agent Active Perception with Prediction Rewards.  Proceedings of the Conference on Neural Information Processing Systems (NeurIPS). 2020;33:13651–13661.
  * (80) Rashid T, Samvelyan M, Schroeder C, Farquhar G, Foerster J, Whiteson S.  QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning.  In: Proceedings of the International Conference on Machine Learning. PMLR; 2018. p. 4295–4304.
  * (81) Xiao Y, Lyu X, Amato C.  Local Advantage Actor-Critic for Robust Multi-Agent Deep Reinforcement Learning.  In: Proceedings of the International Symposium on Multi-Robot and Multi-Agent Systems (MRS). IEEE; 2021. p. 155–163.
  * (82) Jiang S, Amato C.  Multi-Agent Reinforcement Learning with Directed Exploration and Selective Memory Reuse.  In: Proceedings of the Annual ACM Symposium on Applied Computing; 2021\. p. 777–784.
  * (83) Lyu X, Amato C.  Likelihood Quantile Networks for Coordinating Multi-Agent Reinforcement Learning.  In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS); 2020. p. 798–806.
  * (84) Omidshafiei S, Kim DK, Liu M, Tesauro G, Riemer M, Amato C, et al.  Learning to Teach in Cooperative Multiagent Reinforcement Learning.  In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 33; 2019. p. 6128–6136.
  * (85) Peng B, Rashid T, Schroeder de Witt C, Kamienny PA, Torr P, Böhmer W, et al.  Facmac: Factored Multi-Agent Centralised Policy Gradients.  In: Proceedings of the Conference on Neural Information Processing Systems (NeurIPS). vol. 34; 2021. p. 12208–12221.
  * (86) Pan L, Rashid T, Peng B, Huang L, Whiteson S.  Regularized Softmax Deep Multi-Agent Q-Learning.  In: Proceedings of the Conference on Neural Information Processing Systems (NeurIPS). vol. 34; 2021. p. 1365–1377.
  * (87) Gupta T, Mahajan A, Peng B, Böhmer W, Whiteson S.  UneVEn: Universal Value Exploration for Multi-Agent Reinforcement Learning.  In: Proceedings of the International Conference on Machine Learning. PMLR; 2021. p. 3930–3941.
  * (88) Willemsen D, Coppola M, de Croon GC.  MAMBPO: Sample-Efficient Multi-Robot Reinforcement Learning Using Learned World Models.  In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2021. p. 5635–5640.
  * (89) Amato C, Konidaris GD, Kaelbling LP.  Planning with Macro-Actions in Decentralized POMDPs.  In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS). International Foundation for Autonomous Agents and Multiagent Systems; 2014. p. 1273–1280.
  * (90) Amato C, Konidaris G, Anders A, Cruz G, How JP, Kaelbling LP.  Policy Search for Multi-Robot Coordination Under Uncertainty.  The International Journal of Robotics Research. 2016;35(14):1760–1778.
  * (91) Hoang TN, Xiao Y, Sivakumar K, Amato C, Howl JP.  Near-Optimal Adversarial Policy Switching for Decentralized Asynchronous Multi-Agent Systems.  In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). IEEE; 2018. p. 6373–6380.
  * (92) Xiao Y, Hoffman J, Amato C.  Macro-Action-Based Deep Multi-Agent Reinforcement Learning.  In: Proceedings of the Conference on Robot Learning. PMLR; 2020. p. 1146–1161.
  * (93) Xiao Y, Hoffman J, Xia T, Amato C.  Learning Multi-Robot Decentralized Macro-Action-Based Policies via a Centralized Q-Net.  In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). IEEE; 2020. p. 10695–10701.
  * (94) Liu M, Sivakumar K, Omidshafiei S, Amato C, How JP.  Learning for Multi-Robot Cooperation in Partially Observable Stochastic Environments with Macro-Actions.  In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2017. p. 1853–1860.
  * (95) Xiao Y, Tan W, Amato C.  Asynchronous Actor-Critic for Multi-Agent Reinforcement Learning.  In: Proceedings of the Conference on Neural Information Processing Systems (NeurIPS); 2022. .
  * (96) Omidshafiei S, Liu SY, Everett M, Lopez BT, Amato C, Liu M, et al.  Semantic-Level Decentralized Multi-Robot Decision-Making Using Probabilistic Macro-Observations.  In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). IEEE; 2017. p. 871–878.
  * (97) Jia S, Wang X, Shen L.  A Continuous-Time Markov Decision Process-Based Method with Application in a Pursuit-Evasion Example.  IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2015;46(9):1215–1225.
  * (98) Azevedo C, Matos A, Lima PU, Avendaño J.  Petri Net Toolbox for Multi-Robot Planning Under Uncertainty.  Applied Sciences. 2021;11(24):12087.
  * (99) Chen F, Sekiyama K, Huang J, Sun B, Sasaki H, Fukuda T.  An Assembly Strategy Scheduling Method for Human and Robot Coordinated Cell Manufacturing.  International Journal of Intelligent Computing and Cybernetics. 2011;.
  * (100) Bellman R.  Dynamic Programming.  Science. 1966;153(3731):34–37.
  * (101) Howard RA.  Dynamic Programming and Markov Processes.  John Wiley; 1960.
  * (102) Bonet B, Geffner H.  Labeled RTDP: Improving the Convergence of Real-Time Dynamic Programming.  In: Proceedings of the Thirteenth International Conference on Automated Planning and Scheduling (ICAPS); 2003. p. 12–21.
  * (103) Kocsis L, Szepesvári C.  Bandit Based Monte-Carlo Planning.  In: Proceedings of the European Conference on Machine Learning. Springer; 2006. p. 282–293.
  * (104) Kakumanu P.  Relation Between Continuous and Discrete Time Markovian Decision Problems.  Naval Research Logistics Quarterly. 1977;24(3):431–439.
  * (105) Butkova Y, Wimmer R, Hermanns H.  Long-Run Rewards for Markov Automata.  In: Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). Springer; 2017\. p. 188–203.
  * (106) Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, et al.  Human-Level Control Through Deep Reinforcement Learning.  Nature. 2015;518(7540):529–533.
  * (107) Oliehoek FA, Spaan MT, Vlassis N.  Optimal and Approximate Q-Value Functions for Decentralized POMDPs.  Journal of Artificial Intelligence Research. 2008;32:289–353.
  * (108) Buchholz P, Hahn EM, Hermanns H, Zhang L.  Model Checking Algorithms for CTMDPs.  In: Proceedings of the International Conference on Computer Aided Verification (CAV). Springer; 2011. p. 225–242.
  * (109) Legay A, Delahaye B, Bensalem S.  Statistical Model Checking: An Overview.  In: Proceedings of the International Conference on Runtime Verification; 2010. p. 122–135.
  * (110) Butkova Y, Hartmanns A, Hermanns H.  A Modest Approach to Markov Automata.  ACM Transactions on Modeling and Computer Simulation (TOMACS). 2021;31(3):1–34.
  * (111) Koenig N, Howard A.  Design and Use Paradigms for Gazebo, an Open-Source Multi-Robot Simulator.  In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Sendai, Japan; 2004. p. 2149–2154.
  * (112) Bakker T, Ward GL, Patibandla ST, Klenke RH.  RAMS: A Fast, Low-Fidelity, Multiple Agent Discrete-Event Simulator.  In: Proceedings of the Summer Computer Simulation Conference (SCSC); 2013\. p. 1–10.