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.

This paper introduces an iterative approach to multi-agent route planning under chance constraints. A heterogeneous team of agents with various capabilities is tasked with a Capability Temporal Logic (CaTL) mission, a fragment of Signal Temporal Logic. The agents’ motion is modeled as a finite weighted graph, where the weights represent travel durations. Given the probability distribution over the durations of each edge’s traversal, we want to find paths for all agents such that (a) the specification robustness is maximized, (b) travel time is minimized, and (c) the success probability is maximized. We tackle the problem using an iterative approach. In each stage, it selects edges’ traversal duration and success probabilities and then solves a multi-agent route planning problem. We use an efficient Mixed-Integer Linear Programming (MILP) encoding for the latter. Our method provides a framework for agents to make informed decisions in choosing the most suitable edge attributes (travel durations and success probabilities) that consider agents’ capabilities to perform tasks in the environment. The proposed iterative method leverages graph structure to generate a more efficient search space. The effectiveness of our method is demonstrated through simulated case studies where obtaining the optimal solution would otherwise be computationally expensive. Our approach efficiently explores the solution space, generating better solutions and improving the performance of multi-agent route planning with uncertain travel durations.

Mobility-on-demand systems are transforming the way we think about the transportation of people and goods. Most research effort has been placed on scalability issues for systems with a large number of agents and simple pickup/drop-off demands. In this paper, we consider fair multi-vehicle route planning with streams of complex, temporal logic transportation demands. We consider an approximately envy-free fair allocation of demands to limited-capacity vehicles based on agents' accumulated utility over a finite time horizon, representing for example monetary reward or utilization level. We propose a scalable approach based on the construction of assignment graphs that relate agents to routes and demands, and pose the problem as an Integer Linear Program (ILP). Routes for assignments are computed using automata-based methods for each vehicle and demands sets of size at most the capacity of the vehicle while taking into account their pickup wait time and delay tolerances. In addition, we integrate utility-based weights in the assignment graph and ILP to ensure approximative fair allocation. We demonstrate the computational and operational performance of our methods in ride-sharing case studies over a large environment in mid-Manhattan and Linear Temporal Logic demands with stochastic arrival times. We show that our method significantly decreases the utility deviation between agents and the vacancy rate.