Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity

Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms

Automated high-density storage systems (warehouses, robotic parking, plant logistics, etc.) require fleets of agents to move through scarce task-critical resources and then park without obstructing future operations. We introduce Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a MAPF variant in which a subset of tasked agents must each visit one of a set of interchangeable pivots (e.g., workstations) before the entire fleet terminates at anonymous stations, one agent per station. We characterize solvability completely: every instance on a 2-edge-connected graph is solvable, and, on arbitrary connected graphs, a structural effective-distance measure relative to the number of unoccupied vertices gives a necessary and sufficient condition. We prove that minimizing station-makespan or station-flowtime is NP-hard already with a single pivot. We present three algorithms, a complete baseline, a SAT-based optimal solver, and Pivot-Prioritized Planning (PPP), the last solving 74-89% of benchmark instances with makespan and flowtime orders of magnitude below the baseline.

Min–Max Regret Task Allocation and Planning of Heterogeneous Multi-Robot System in Partially Known Environments

Efficient task allocation for large-scale Heterogeneous Multi-Robot Systems (HMRS) is critical, yet dealing with complex temporal logic tasks in partially known environment (PKE) remains a computational bottleneck. Existing approaches often struggle to balance exploring uncertain regions and exploiting known resources, while also suffering from exponential computational complexity. To address these issues, this paper presents a robust planning framework that simultaneously handles high-level logical constraints and environmental uncertainty without sacrificing scalability. We formulate the problem as a min-max regret optimization, proposing a Region-Binding Atomic Proposition (RbAP) to capture resource uncertainty within the automaton structure. To solve this, we propose the Extended Planning Decision Tree (E-PDT) equipped with a novel Regret-based Branch-and-Bound (BnB) strategy. Unlike traditional methods that rely on prior probabilities or worst-case analysis, our approach dynamically prunes suboptimal policies, effectively balancing the need for information gathering (exploration) and task completion (exploitation). Theoretical analysis confirms the feasibility and completeness of our approach. Extensive numerical and physical experiments demonstrate that the proposed framework achieves near-linear scalability with respect to the number of robots and types, significantly outperforming MILP-based baselines in both solution quality and computational efficiency. Note to Practitioners—Task allocation for large-scale heterogeneous multi-robot systems is critical in applications like warehouse logistics and disaster response. However, existing planning methods often struggle with environmental uncertainty, relying on unavailable probability data or failing to scale. This work presents a fast, robust planning framework that uses a regret-minimization strategy to balance exploring uncertain areas with completing tasks. Unlike optimization-based approaches that can be computationally prohibitive, our E-PDT method achieves near-linear scalability, coordinating thousands of robots in seconds. This allows practitioners to deploy large robot fleets that adaptively search for resources without needing precise prior knowledge. Current limitations assume a known static map topology with uncertain resource locations; future extensions will address fully dynamic and unknown environments.

Multi-Agent Scheduling for Large-Scale On-Road Testing in Intelligent Transportation Systems

Adaptive Route Planning for Autonomous Logistics Robots in Dynamic Warehouse Environments

The enormous increases in global retail has pushed automation levels to new extremes, with autonomous mobile robots (AMRs) increasingly becoming a centerpiece of modern logistics infrastructure. One of the major challenges faced by traditional multiagorithm design and line models, due to static routing charts or offline algorithmic updates, when it has to be deployed in highly dynamic unpredectable working environment within an intra-logistics setting. This paper offers a resilient, adaptive routing framework for the well-timed delivery of independent logistics robots over uniquely temporary traffic and sudden tangible obstructions. Synthesizing localized real-time sensory perception and distributed topological map updates, the architecture dynamically re-calculates optimal travel trajectories making systemic deadlocks impossible and minimizing idle times drastically. Results from computational evaluations across simulated warehouse layouts with varying spatial complexity show that the adaptive framework improves fleet-wide operational efficiency (by up to 24.3%) in comparison to conventional fixed-path planning configurations and simultaneously leads to lower total energy expenditure. Together these results provide evidence of clinical feasibility for inclusion of decentralized, reactive real-time routing models into heavy-duty industrial automation applications.

Vehicle Routing Problem with Resource-Constrained Pickup and Delivery: A Heuristic-Informed BRKGA with Pattern-Based Analysis

We introduce the Vehicle Routing Problem with Resource-Constrained Pickup and Delivery (VRP-RPD), where agents deploy finite identical resources at customer locations for processing before retrieval and redeployment. Applications include portable medical equipment, tool rental, and disaster relief. Unlike classical pickup-and-delivery variants, VRP-RPD permits different agents to perform dropoff and pickup for the same customer—creating inter-route dependencies absent from standard formulations. We provide a complete mixed-integer linear programming formulation and demonstrate that exact methods are intractable even for small instances. Problems with 16 customers cannot be solved to optimality within two hours of computational time. We develop a Biased Random-Key Genetic Algorithm (BRKGA) with a four-gene-per-customer encoding. Two genes assign dropoff and pickup agents independently, while two priority keys determine sequencing. A simulation decoder guarantees feasibility by deferring operations until resources become available. Experiments on 14 TSPlib-derived benchmarks across five variants of processing time (base, 2X, 5X, 1R10, 1R20) compare four configurations. Warm-start BRKGA achieves 13–67% makespan reduction over the heuristics, with larger gains on higher-resource instances. Ablation tests show warm-start initialization is the primary driver of performance. Friedman tests (p < 0.01) confirm warm-start BRKGA superiority across all instance variants.

Efficient Multi-Robot Cooperative Exploration for Semi-Enclosed Environments Based on Multi-Constraint Consensus

Multi-robot systems enable rapid and scalable environmental exploration by distributing sensing and coverage across multiple robots. However, in semi-enclosed environments with complex connectivity (e.g., office, hospital), existing methods fail to account for local reachability and topological structure, leading to inefficient exploration. In this letter, we propose a cooperative exploration framework for such semi-enclosed environments. The framework first partitions the global mission into spatially continuous task domains using spatial correlation-aware domain fusion (SCADF). These task domains integrate topological relationships and local navigability and align the task geometry with the environment. Task assignment is then performed by a novel multi-constraint consensus-based bundle algorithm (MC-CBBA). MC-CBBA augments the classical CBBA with three constraints: inter-robot workload balance, minimum per-robot workload guarantee, and path cost minimization. A two-stage distributed consensus protocol ensures feasible and balanced allocations. Simulation experiments indicate that the proposed method reduces mission completion time by an average of 36% compared with state-of-the-art methods, while significantly enhancing load balancing and exploration efficiency. Real-world experimental results further demonstrate the robustness and effectiveness of the proposed approach.