RESCUE: Multi-Robot Planning Under Resource Uncertainty and Objective Criticality

Monte Carlo Tree Search (MCTS) is a sampling-based heuristic that incrementally builds a search tree and evaluates actions through simulated outcomes. Combining tree search algorithms and Monte Carlo simulations, it constructs the tree iteratively by simulating action sequences and assessing their results. The process consists of four distinct phases, depicted in Figure 2. In the selection phase, the heuristic selects an expandable and promising node, driving the tree-building process through recursive traversal. An expandable node is a node where at least one child node can be added, meaning all the requirements for at least one action are met, including budget constraints. During the expansion phase, leaf nodes are added to represent possible actions. The simulation phase involves selecting actions based on a rollout policy, which determines the action selection strategy, and evaluating outcomes using predefined criteria, such as an upper bound on expected rewards. A random rollout policy selects actions randomly for this phase. Finally, in the back-propagation phase, the simulation results are propagated back through the tree to update node values.

The algorithm continues these iterations until a computational budget (e.g., time limit or iteration count) is reached, after which the action corresponding to the most promising child of the root node is selected. In our approach, we assume that only one (potentially complex) action is needed to achieve one objective. For example, this action might involve multiple movements followed by data loading to accomplish the objective.

Task Allocation Monte Carlo Tree Search (TA-MCTS) [27] is a variant of MCTS tailored to address task or objective allocation challenges in multi-robot systems. TA-MCTS incorporates two heuristics: the first one partitions robots and objectives into smaller groups to enhance scalability, while the second one generates conflict-free plans for each group. In our work, we revisit and refine the second heuristic, focusing on creating significantly enriched conflict-free plans for groups of robots and objectives.

In its first heuristic, TA-MCTS creates $K$ groups of objectives with the same number of objectives in each one. $K$ depends on the number of objectives to be assigned to each group of $N$ robots. For this partitioning, TA-MCTS uses a modified implementation of K-means called Uniform Distribution K-means, or UD-Kmeans, to classify objectives according to their physical distance from each other. Since the average distance between the objectives is minimized by K-means, the group of robots will remain relatively close to each other. This is important for our reliable communication assumption, as the robots must remain within communication range of the coordinator for our solution to be viable.

To adapt MCTS for a multi-robot scenario, TA-MCTS combines the trees of all robots into a unified single tree, focusing on simulating the best combinations of actions. But, in a single tree MCTS approach, an action can be assigned to multiple nodes. For example, MCTS can evaluate both combinations of $(x_1^1,x_2^2)$ and $(x_2^1,x_1^2)$. Consequently, in a multi-robot tree, the same action might be assigned to nodes belonging to different robots. To address this, TA-MCTS maintains a set of assigned actions, ensuring that each action is allocated to only one robot while preserving the optimization advantages of the multi-tree approach. Moreover, the actions in TA-MCTS consist of moving to a point of interest and delivering a package. However, in their solution, only the cost of moving from one delivery point to another is taken into account as cost of the action. In our approach, we take into account the cost of the whole action, which allows us to differentiate costs between resources (i.e. flight time and energy consumed).

One iteration of TA-MCTS is described in Figure 3. First, robot $R1$ is chosen at random to have its tree expanded. The selection phase shown in Figure 3(a) is executed on the tree representing robot $R1$, and node $A4$ representing the action sequence $\mathbf{(}A1,A4)$ is selected. During the expansion phase, a new node representing action $A5$ is added to the tree, indicating that this iteration will evaluate the reward of robot $R1$ executing the action sequence ${𝒙}^{\mathrm{𝟏}}=(A1,A4,A5)$.To prevent simulating scenarii in which two robots attempt to execute the same action, we build a set of assigned actions ($assigned$) at each iteration that stores the actions already assigned to a robot. The actions in ${𝒙}^{\mathrm{𝟏}}$ are thus added to $assigned$. Subsequently, as shown in Figure 3(b) the iteration proceeds to pick robot $R2$ at random to select its most probable sequence of actions considering that it cannot execute the actions contained in $assigned$. Starting from the root, action $A1$ is ignored and action $A3$ is picked instead. As action $A4$ is in $assigned$, the selection for $R2$ stops, selecting action sequence ${𝒙}^{\mathrm{𝟐}}=(A3)$. The actions in ${𝒙}^{\mathrm{𝟐}}$ are then added to $assigned$. This cycle continues until a sequence of actions is selected for each robot.

Finally, the simulation and backpropagation phases are executed. During the simulation phase shown in Figure 3(c), the sequence of actions for each robot is simulated, and random future actions of robot $R1$ are sampled. The resulting expected reward is stored in the new added node. The backpropagation phase is then executed for robot $R1$ as shown in Figure 3(d), and the assigned actions set is emptied. After the last iteration, the same selection phase is executed to pick the best action sequence for each robot, and the algorithm returns $𝑺$.

Mixed-Criticality Monte Carlo Tree Search ((MC)²TS) [9] incorporates mixed-criticality into MCTS for a single robot. (MC)²TS is an extension of MCTS designed to handle single-robot planning with uncertain action costs and critical objectives using the MC approach. As described in Section 2, to comply with Mixed-Critical System model, each action has two resource costs, one for each criticality mode. In (MC)²TS, it also has two accumulated resource costs.

The accumulated costs for lo-actions are:

while the accumulated costs for hi-actions are:

where $h$ is either the node with the previous hi-action in the tree branch of node $k$ or the root node.

During the plan execution, $\overline{b_k}$ is checked after, and only after, the execution of action $x_k$. If its value surpasses the value of $b_k(\text{lo})$ computed during the planning, then a mode change occurs, and every subsequent lo-action is dropped. The value of $b_k(\text{hi})$ can only be surpassed if there is a failure in the system’s design.

The mode change is thus triggered by surpassing $b_k(\text{lo})$ and the current plan may continue to be executed by ignoring every lo-action. The replanning is triggered only when a predetermined replan horizon is reached. Therefore, a mode change does not trigger a replanning. However, since replanning reallocates every available resource, the system may safely return to lo-mode when executing the new plan.

When configuring rewards, it is crucial to ensure that lo-actions do not monopolize resources to the detriment of hi-actions. Consequently, the reward $r_i$ for performing a hi-action $x_i$ must be higher than the sum of the rewards for performing all lo-actions: .

Our approach, RESCUE, is designed to enhance multi-robot systems by offering improved properties and guarantees, including resilience, robustness, adaptability, and efficiency (see Section 3). It integrates key concepts inspired by (MC)²TS and TA-MCTS.

We considered an active perception scenario on a 100×100 grid-based terrain, where robots can move freely within the field. The area contains 20 randomly distributed objectives, including 5 high-critical and 15 low-critical objectives. A charging station, serving as both the starting point and the safe return location for the robots, is positioned at one corner of the grid. The robots must collaborate to maximize the reward from completed objectives while ensuring a safe return to the charging station.

For the MCTS parameters, we used a random rollout policy and use the Upper Confidence Bound for Trees (UCT) [21] as the selection policy. UCT is a best-first approach that computes an upper confidence bound to estimate the expected reward of a selected node. The computational budget was set to 5000, representing the number of RESCUE iterations, with one node being added to one random tree at each iteration. This value must ideally allow each tree to have its most promising branch completely explored to the same depth as the replan horizon. Since the algorithm usually explores some branches deeper than the others, it is impossible to know the necessary number of iterations prior to the execution. Therefore, we picked an arbitrary value that is higher than the necessary to completely explore each tree to the second layer if each tree is explored the same amount of times. The horizon was set to 5, defining the maximum length of action sequences evaluated during rollouts. The C parameter in UCT, which controls the balance between exploring new paths and exploiting the best-known path, is fixed at 0.5.

In our implementation, the actions considered are reaching an objective point, and retrieving the data from the sensor located at that point. The costs for actions are shown in Table 1. Since their cost is a function of the robot’s position at the beginning of their execution, we give the cost of movement per unit of distance. The total cost for an action is thus the sum of the movement and the data retrieving costs. The energy budget was fixed on 100%. The distance between the previous objective point and the next one was used to compute the cost of a move action.

The costs in time and energy of an action depend on the state of the environment. If the environment is favorable for the mission (e.g., no wind), the costs will be equal to $C(\text{lo})$. However, if the environment is unfavorable (e.g., a strong wind), then the costs will be equal to $C(\text{hi})$. In tests that evaluate performance, we evaluated the results in a favorable environment, as that is the normal state of operation. In tests that evaluate safety, we simulated an unfavorable environment.

The objective function considered was

where $r_i$ is the reward for completing action $x_i$, $t$ is the time consumed from the beginning of the mission until the end of the last action and $B[time]$ is the total time budget available.

The expression $\frac{t}{B[\text{time}]}$ is used to prioritize plans that accomplish the same objectives in a shorter duration. The weight $\frac{r^{\text{lo}}}{10}$ ensures that this value remains lower than the reward for completing an objective.

For RESCUE, we used $b(LO)[time]$ as $t$, as it is the accumulated cost for the optimistic mode of operation. The reward for completing a hi-action grants 0.166, and executing a lo-action provides 0.0104. The idle action does not provide any reward, but its availability is a prerequisite for all other actions. This, before incorporating any action $x_i$ into the tree, we ensure that idle remains executable afterward, ensuring the robot can return to the charging station.

Fifty different random scenarios were generated with different random positions for the 20 objectives. This number is similar to the number of objectives in a group in the TA-MCTS evaluation[27]. The $x$ and $y$ coordinates of each objective was sampled from a uniform distribution between 1 and 99. On each scenario, we ran RESCUE 100 times and evaluated the results. This process was executed with different time budgets, number of robots similar to the ones evaluated in a TA-MCTS group, replan horizons and spreading factors, $\alpha$.

We evaluated the performance of RESCUE when compared to TA-MCTS-R-P. TA-MCTS-R-P ignores mixed-criticality costs and operates with pessimistic costs. We aim to demonstrate how it is more pessimistic than RESCUE.

When considering a favorable environment, the pessimism of TA-MCTS-R-P may cause it to execute fewer actions than RESCUE. Thus, we evaluate the number of objectives achieved by RESCUE compared with that of TA-MCTS-R-P by simulating an environment where actions cost $C(\text{lo})$. The robot fleet used contained 5 robots and replanning was made each 2 actions.

The experimental results are shown in Figure 5. RESCUE outperforms TA-MCTS-R-P in this scenario when the budget is not big enough to accomplish all objectives. This is due to RESCUE having an accumulated cost closer to the execution in a favorable environment, allowing it to explore more action sequences thanks to the previously spared budget. Thus, RESCUE reduces the oversizing of the system.

We evaluated the performance of RESCUE when compared to TA-MCTS-R-O in the situation where both are executed in an unfavorable environment. TA-MCTS-R-O does not consider mixed-criticality mechanisms, and we aim to demonstrate how it is unsafe, unlike RESCUE.

In an unfavorable environment, TA-MCTS-R-O generates plans that exceed the allocated resources for completion. To assess its reliability in worst-case scenarios, we simulate it in an initially favorable environment where conditions deteriorate over time. Additionally, we compare the total number of objectives achieved by RESCUE against TA-MCTS-R-O in these missions. If TA-MCTS-R-O fails to return safely, the simulation is terminated, and the number of successfully achieved objectives is recorded as zero. The robot fleet consists of five robots, with replanning occurring every two actions.

The experimental results are shown in Figure 6. The first graph shows that the lower the resource budget, the more TA-MCTS-R-O fails midway through the execution of the mission, reducing its effectiveness. This can also be observed on the second figure, as the number of objectives achieved is compromised by its unsafety. Thus, RESCUE increases the safety of the system.

To evaluate the benefits of using a fleet instead of a single robot, we ran the previously described scenario with a single robot while varying the time budget. We then repeated the experiment with a fleet of two to five robots and compared the number of objectives reached. As expected, under a tighter budget, a larger fleet was able to achieve more objectives, as shown in Figure 7.

In order to compute the performance gain, which is the ratio of the mission execution time using one robot to the mission execution time with $N$ robots, we allocated enough resources to the robots to complete every objective in the mission and compared the time taken by each fleet to finish. In this configuration, each fleet always completes the same number of objectives – 20 in total. The time budget used was 1000, and replanning was performed every two actions.

The results are shown in Table 2. The performance increases rapidly with the addition of the first robots; however, it does not increase indefinitely. As the number of robots approaches the number of objectives, the fleet completes the mission as quickly as possible, with each robot completing one objective. However, the results show how RESCUE allows a reduction in mission time.

A key question is whether reducing the frequency of replanning significantly degrades performance. This frequency is derived from the replan horizon, which specifies the number of actions completed before a robot initiates a replan. To assess the impact on algorithm performance, we varied the replan horizon and simulated a scenario where replanning time is negligible compared to the mission duration. The simulations involved a fleet of 2 robots operating in an unfavorable environment. The results, presented in Figure 8, show that, as expected, a longer replan horizon reduces mission efficiency.

However, even though it increases the efficiency of the mission, replanning is resource consuming. Therefore, it may be desirable to replan less often to save resources. We simulated the same experiment as before but considering that replanning takes in total 30 units of time (computation and communication included). This time cost for replanning is similar to accomplishing an objective that’s at 10 units of distance in hi-mode. Therefore, it might be preferable to accomplish another objective instead of replanning.

The experimental results are shown in Table 3, frequent replanning can reduce the fleet’s resources to a point where the robots complete fewer objectives. In the time budgets presented in the table, replanning every action performs similar to replanning every 3 actions. In this case, the time saved by not replanning every action was used by the robots to produce better results. Therefore, the replan horizon should be adjusted by considering the replanning time and, more precisely, the communication time.

In this experiment, we demonstrate that our solution minimizes, first, the non-completion of hi-objectives and, second, the non-completion of lo-objectives in the case of a faulty robot. We consider a worst-case scenario in which the hi-objectives are spread in the top-left quarter of the grid, while the lo-objectives are spread in the bottom-right quarter of the grid as shown in Figure 9.

In our first experiment, the fleet consists of two robots. We simulate a configuration where one of the robots fails at the start of the mission and does not reach any of the objectives. The environment is set to be unfavorable (actions cost $C(\text{hi})$). The given budget is 670 time units and the replan is performed every two actions. This amount of resource budget only allows the robots to go to one agglomeration of objectives, cross the map to the other agglomeration, and return to the base. We compare the simulation results using our solution with spreading factors $\alpha =0$ and $\alpha =0.16$, the spreading factor indicating the ability to deviate from the optimum in favor of a better distribution of objectives.

The results are shown in Table 4. The difference in average objectives in the experiment with a faulty robot can be explained by the difference on how each algorithm dispatches the two robots. In the case where $\alpha =0$, RESCUE is more likely to dispatch each robot to a different corner of the map to minimize the total amount of time to finish the mission. The faulty robot may be assigned to either lo or hi-objectives, with the hi-objective assignment being random since all robots start identical. When the faulty robot is assigned to the hi-objectives, the other robot is sent to cross the map to ensure the completion of the hi-objectives after reaching the first replan horizon. The remaining robot is unable to return to the lo-objectives after crossing the map and therefore completes fewer objectives.

In the case where $\alpha =0.16$ however, RESCUE is more likely to send the two robots to complete the hi-objectives first. Indeed, sending the robots together to complete the hi-objectives reduce the difference in the reward accomplished by each robot. Therefore, the loss of one of the robots only causes the remaining robot to take the hi-objectives that are already close to it. This leaves enough resources for the remaining robot to cross the map and execute the lo-objectives before returning.

In our second experiment, we examine a more general case with a fleet of five robots. We assess its performance under both spreading factors, assuming no faults occur, to understand their impact in a fault-free scenario. As shown in Table 4, there is no significant difference between the results for both factors. This demonstrates that, in the general case, the spreading factor $\alpha$ does not affect the fleet’s performance. Therefore, in a random scenario, the spreading factor can mitigate the consequences of a fault without noticeably reducing performance when no faults occur.

These experiments show that RESCUE successfully reduces the consequences of faults while preserving performance under anormal scenario.

Thus, we have successfully shown how RESCUE can reduce the impact of a fault while maintaining performance in normal scenarii.

As path planning is an NP-hard problem in optimization [22], the multi-robot planning version has high computational complexity. This complexity results in a lack of algorithms that are both optimal and computationally efficient [16]. A thorough review of approaches for multi-robot path planning can be found in [1].

A common metaheuristic for multi-robot path planning is Particle Swarm Optimization (PSO), an optimization algorithm based on the social behavior of animals. It initializes the workspace with stochastic particles, each randomly seeking an optimal position and velocity to optimize a fitness function [28]. However, its stochastic foundation does not allow for hard guarantees on the completion of hi-objectives.

The problem of assigning various tasks to a swarm of robots is an active research topic in the artificial intelligence community as well. However, most authors concentrate on global performance in an ideal or slightly disturbed environment, or on robot cooperation for complex tasks. In [12], Galati et al. propose an auction-based allocation system with quick dynamic task reallocations after a perturbation occurs, thus adapting to a dynamic environment. However, they do not guarantee that planned or better hi-objectives will be satisfied, and they require human supervision to validate the plan.

When dealing with possible faults, fault detection becomes a more complex problem. As the robots interact and cooperate, the detection and diagnosis for each robot become more complex in a decentralized system compared to a single-robot system [20]. For fault tolerance, Bramblett et al. propose centralized mission planning based on a genetic algorithm where the robots plan to meet intermittently to check for faults [3]. They also propose a replanning algorithm to handle detected faults. While this solution reduces the effects of faults, it requires the robots to meet periodically and for each to be capable of executing a mission replan. Moreover, it does not consider the criticality of objectives.

Monte-Carlo Tree Search (MCTS) has proven to be pivotal in addressing complex decision-making problems, such as gaming, planning, optimization, and scheduling [18, 5].

Regarding multi-robot plan building, Best et al. proposed a distributed solution called Dec-MCTS [2], where each robot builds its own plan and shares information regarding the probability of its future actions with others. This approach is more tolerant to faults in the ground control station, as the robots are independent. However, it requires the robots to have enough processing power to build their plans and communicate with all other robots. Moreover, if two robots are equally capable of pursuing an objective, there is no guarantee that they will not compete to accomplish the same objective.

D’Urso et al. expanded that idea by proposing a hierarchical approach for coordinating surface vessels [11]. In the studied scenario, vessels had to drop floats and pick them up later to obtain information about an area of the ocean. The authors propose dividing the problem into two parts: finding a set of drop-off and corresponding pick-up actions that observe all the space, and scheduling the found actions to a set of robots. MCTS is used in both parts: a centralized MCTS for deciding the actions, and then Dec-MCTS for assigning the actions to the robots.

To address possible faults in a multi-robot system, Bramblett et al. propose an epistemic replanning mechanism [3]. This approach uses a centralized planner that rewards intermittent rendezvous between the robots to detect possible failures. If a robot fails to meet with another, it adjusts its local plan to compensate for the faulty robot by using a genetic algorithm and MCTS while communicating with other robots to share beliefs about the system. This approach does not enforce a budget for the robots, and uncertainties in the cost of actions are not considered during the MCTS phase.

Mixed-criticality systems (MCS) [29] have been extensively studied in the context of real-time embedded systems, where tasks with different levels of criticality share computational resources. The majority of the research has focused on Real-Time Scheduling [6] and does not address other decision-making algorithms.

A partitioned multiprocessor system closely parallels a multi-robot application, with task allocation on processors being the primary challenge. Lakshmanan et al. [23] adapted a single processor approach using a Compress-on-Overload scheme.

Various research efforts have explored applying the mixed-criticality paradigm to networked systems by assigning criticality levels to communication, such as FlexRay [15] and switched Ethernet [10]. However, in our work, there is no requirement for criticality levels on communication resources.

In the context of distributed IoT systems, JMC [25] is an efficient scheduling framework designed to maximize the performance of lo flows while ensuring the schedulability of hi flows. It uses jitters to evaluate runtime pessimism and trigger criticality mode transitions based on predefined thresholds and policies. The lazy or proactive policies minimize the impact either on the lo or hi flows.

Some studies [26, 19, 30] tackle energy-aware systems and use DVFS or DVFS with EDF-VD scheduling to reduce energy consumption in mixed-criticality systems by degrading low-critical (lo) tasks in high-critical (hi) mode. However, these approaches do not inherently prioritize hi-tasks over lo-tasks and do not consider energy as a primary resource.

(MC)²TS enhances action planning under uncertain costs, reducing overestimations and resource waste [9]. Compared to previous projects, it expands the MC approach beyond execution time to consider energy as a first-class citizen within the system. (MC)²TS also introduces the MC paradigm to MCTS, expanding its traditional use in Real-Time Scheduling. However, it is limited to single robots.