High-level multi-robot coordination in a shared workspace for pick-and-place operations using MILP optimization and heuristic for conflict resolution

Efficient coordination of multiple robots in shared workspaces for pick-and-place operations poses significant challenges due to spatial and temporal conflicts. This paper presents a high-level multi-robot coordination framework specifically targeting scenarios with overlapping targets and tightly constrained environments, validated across 240 instances with 100% collision-free success. We propose two complementary approaches: (i) a Mixed-Integer Linear Programming (MILP) model that jointly optimizes task allocation, sequencing, and motion coordination , and (ii) a scalable heuristic, Detect-and-Pause, that decomposes the problem into MILP-based allocation, SPT rule-based sequencing, and iterative conflict resolution. Both methods leverage a voxel-based occupancy matrix discretizing the shared workspace, enabling fine-grained spatial tracking and effective conflict detection through strategic pause insertion without modifying geometric paths. Extensive ROS-Gazebo simulations demonstrate clear performance trade-offs. The MILP model proves optimality for 55% of 4-object instances but 0% for 6+ objects due to exponential complexity growth. The heuristic achieves 732 ×–2232 ×speedup (solving in 0.45–5 s versus up to 1 h for MILP) while maintaining solution quality within 12–30% of MILP solutions. The validated SPT sequencing rule yields 6.5–15.6% makespan improvement over alternatives, and the shortest-trajectory pause strategy delivers 60% computational efficiency gain. With fine-grained discretization, robots operate simultaneously 89.4% of the time, confirming effective workspace utilization. These results demonstrate that combining discrete optimization with validated heuristic rules offers scalable, collision-free coordination for industrial multi-robot applications. • Designed an occupancy matrix-based approach to track robot workspace occupation and resolve conflicts iteratively. • Proposed a Full MILP model for optimal multi-robot task allocation, sequencing, and motion coordination. • Developed a MILP-based heuristic, Detect-and-Pause, for efficient multi-robot task allocation and motion coordination. • Implemented three conflict resolution strategies, including full MILP optimization, partial MILP optimization, and heuristic-based coordination. • Validated the proposed methodology through ROS-Gazebo simulations, demonstrating significant reductions in makespan and collision risks.