An Iterative Approach for Heterogeneous Multi-Agent Route Planning with Resource Transportation Uncertainty and Temporal Logic Goals
Gustavo A. Cardona, Kaier Liang, Cristian-Ioan Vasile · 2025
Read An Iterative Approach for Heterogeneous Multi-Agent Route Planning with Resource Transportation Uncertainty and Temporal Logic Goals by Gustavo A. Cardona, Kaier Liang, Cristian-Ioan Vasile (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-19429.txt.
Introduction
Gustavo Cardona, Kaier Liang, and Cristian-Ioan Vasile present a 2025 iterative planner for robot teams facing unknown resource maps. The robots differ in capability and must carry out missions written in a formal logic that encodes place, timing, skill, and resource demands. Nobody knows where the resources are or how much exists at the start. The algorithm alternates: robots explore to learn the resource landscape, then act to satisfy the mission as far as current knowledge allows.
Each loop refines the plan as new data arrives. Simulated case studies show the team coordinating sensibly despite the uncertainty. The authors frame the balance of exploring and doing as the heart of planning under ignorance. The method targets warehouses, disaster zones, and other shifting workplaces.
Catalog record
| CREATOR | Gustavo A. Cardona, Kaier Liang, Cristian-Ioan Vasile |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-19429
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Iterative Approach for Heterogeneous Multi-Agent Route Planning with Resource Transportation Uncertainty and Temporal Logic Goals Gustavo A. Cardona, Kaier Liang, Cristian-Ioan Vasile Abstract This paper presents an iterative approach for heterogeneous multi-agent route planning in environments with unknown resource distributions. We focus on a team of robots with diverse capabilities tasked with executing missions specified using Capability Temporal Logic (CaTL), a formal framework built on Signal Temporal Logic to handle spatial, temporal, capability, and resource constraints. The key challenge arises from the uncertainty in the initial distribution and quantity of resources in the environment. To address this, we introduce an iterative algorithm that dynamically balances exploration and task fulfillment. Robots are guided to explore the environment, identifying resource locations and quantities while progressively refining their understanding of the resource landscape. At the same time, they aim to maximally satisfy the mission objectives based on the current information, adapting their strategies as new data is uncovered. This approach provides a robust solution for planning in dynamic, resource-constrained environments, enabling efficient coordination of heterogeneous teams even under conditions of uncertainty. Our method’s effectiveness and performance are demonstrated through simulated case studies. I Introduction Using diverse multi-robot systems with unique capabilities is becoming increasingly crucial for complex real-world tasks like disaster response, autonomous construction, and planetary exploration [ 1 , 2 , 3 , 4 ] . In such scenarios, combining the specialized skills of different robots can greatly enhance task efficiency, resilience, and robustness. By working together, robots with expertise in areas like aerial surveillance, manipulation, or drilling can achieve mission goals that would be unattainable for uniform systems [ 5 , 6 , 7 , 8 ] . This varied range of capabilities enables flexible task assignments, allowing robots to capitalize on their strengths and overcome challenges such as environmental uncertainty and time limitations [ 9 , 10 , 11 ] . As missions grow in complexity, establishing formal frameworks that account for the diverse nature of robot capabilities and task coordination becomes essential to ensure system effectiveness and scalability. In recent years, temporal logic has emerged as a powerful formalism for specifying and planning tasks in multi-robot systems, enabling the expression of complex spatial, temporal, and logical constraints. Linear Temporal Logic (LTL) has been widely used for coordinating robots by specifying task order, but its lack of explicit time constraints makes it less suitable for time-sensitive missions [ 12 , 13 , 14 ] . Signal Temporal Logic (STL) addresses this limitation by allowing reasoning over both explicit time and task execution [ 15 , 16 , 17 , 18 , 19 ] . Capability Temporal Logic (CaTL) [ 20 , 21 , 22 ] , a syntactic extension of STL, was developed to handle heterogeneous robots by incorporating their diverse capabilities into task specifications. CaTL was later extended in [ 23 ] to model resource transportation, enabling the planning of both agent actions and the movement of divisible and indivisible resources. However, none of these previous approaches can effectively address uncertainties arising from the environment, task execution, or robot actions, which can compromise mission feasibility. Fig. 1 : Example of heterogeneous robot planning on a planetary exploration mission. Two robot classes are looking for ice and minerals. Uncertainty in such types of problems with multi-robot systems has been addressed by introducing probabilistic temporal logics [ 24 , 25 , 26 ] , which incorporate probabilities into task specifications to account for unpredictable events. Additionally, chance constraints have been used to handle uncertainties in perception and robot travel time, allowing robots to make decisions that maximize the likelihood of task success within acceptable risk levels [ 27 , 28 , 29 ] . This paper addresses the problem of planning for CaTL specifications in environments where the distribution and quantity of resources are initially unknown. We propose an iterative algorithm that balances exploration for resource discovery to maximally satisfy the mission based on the available information. Furthermore, we account for uncertainty in resource detection due to sensor limitations and implement a progressive refinement of the resource distribution belief, enhancing the accuracy of the system’s understanding over time and ensuring robust task planning even when facing incomplete information or variable conditions. The main contributions of this work are, 1. We propose a heterogeneous multi-robot route planning problem for tasks requesting specific capabilities and resources while considering unknown resource distribution in the environment. We impose robots to discover resources and estimate their amount depending on the agent’s capability. 2. We propose an iterative algorithm approach that combines partial mission satisfaction with current knowledge of resource distribution and the progressive refinement of resource distribution belief. 3. We extend the MILP-encoding of CaTL [ 23 ] , to encourage agents to explore the environment while simultaneously satisfying the mission from up to date information about resource distribution. 4. We evaluate the time performance of our planning approach in practical scenarios, such as planetary exploration. By varying the environment size and the number of agents, we aim to gain insights into the problem’s characteristics and its application in real-world situations. Notation: Let \mathbb{Z} , \mathbb{R} , and \mathbb{B} denote the sets of integers, real numbers, and binary values, respectively. The sets of integers and real numbers greater than or equal to a are denoted by \mathbb{Z}_{\geq a} and \mathbb{R}_{\geq a} , respectively. For any set \mathcal{S} , 2^{\mathcal{S}} represents its power set, and |\mathcal{S}| denotes its cardinality. The notation x\sim\mathcal{X} indicates that the random variable x is drawn from the probability distribution \mathcal{X} . For a set \mathcal{S}\subseteq\mathbb{R} and a scalar \alpha\in\mathbb{R} , \alpha+\mathcal{S} denotes the set \{\alpha+x\mid x\in\mathcal{S}\} . The empty set is represented by \emptyset . Let [{a{\mathrel{{.}{.}}\penalty}b}]=\mathbb{Z}\cap[a,b] represent the set of integers between a and b (inclusive). For a range I=[{a{\mathrel{{.}{.}}\penalty}b}] , we use \underline{I}=a and \bar{I}=b to refer to the lower and upper bounds, respectively. II Problem Formulation Here, we introduce a route planning problem for heterogeneous multi-robot teams operating in environments with an unknown distribution of resources. The robots are tasked with fulfilling missions specified using Capability Temporal Logic (CaTL) [ 20 , 21 ] , which incorporates tasks requesting specific agent capabilities and then extended in [ 23 ] to accommodate resource constraints. Depending on their class, the robots are equipped with sensors of varying accuracy and range to explore and identify resource locations. The accuracy of each sensor determines the team’s confidence in estimating the quantity of resources within a sensed area, influencing decision-making during the mission. We extend the CaTL framework in [ 23 ] to accommodate this dynamic resource discovery process, allowing the team to refine its understanding of resource availability while optimizing the route planning for resource transportation and capabilities of agents. Moreover, the robot is required to perform the mission repeatedly, e.g., daily. We formalize the problem as an optimal route planning problem, where robots must efficiently explore the environment to gain more information about resources and maximize task satisfaction over the mission iterations. The following example illustrates the problem class addressed in this paper, where resources are needed at specific locations in the environment for tasks to be completed by agents with diverse capabilities. Example 1 . In the scenario shown in