Eventually Optimal and Scalable Multi-Agent Planning for Block Cave Mining
Christopher Leet, Paolo Forte, Uwe Köckemann, Henrik Andreasson, Sven Koenig
AI summary
Problem
Coordinating autonomous vehicle fleets in block cave mines to maximize ore throughput while satisfying strict draw ratio constraints is hindered by tightly coupled planning components and complex tunnel maneuvering, leaving a gap for scalable, optimal solutions.
Approach
The authors introduce SAMM, an eventually optimal solver that jointly optimizes task assignment, scheduling, and path planning via mixed-integer linear programming, and SAMMS, a scalable variant that decomposes planning into shorter, seamlessly concatenated subcycles.
Key results
- Formalization of the Block Cave Mining problem with draw ratio constraints
- Development of SAMM, an eventually optimal MILP-based cyclic planner
- Introduction of SAMMS, a scalable subcycle-decomposition solver with asymptotic feasibility guarantees
- Experimental validation on realistic benchmarks showing near-optimal throughput and effective scaling to large fleets
Why it matters
Provides a practical, scalable planning framework that enables safe and efficient automation of large-scale underground mining operations.
Abstract
Automation in underground mining has the po- tential to significantly enhance safety, operational efficiency, and sustainability. However, effectively coordinating fleets of autonomous vehicles in dynamic mine environments introduces substantial challenges in both optimization and motion plan- ning. To address these challenges, we introduce and formalize the Block Cave Mining (BCM) problem, which focuses on computing a transport plan that maximizes ore throughput while satisfying draw ratio constraints. To solve this problem, we propose SAMM, an eventually optimal anytime solver that jointly integrates task assignment, scheduling, and path planning via a mixed-integer linear programming formulation. To improve scalability, we also introduce SAMMS, a variant of SAMM that trades optimality guarantees for efficiency by decomposing the problem into shorter planning subcycles. Ex- perimental evaluations using realistic industrial mine scenarios demonstrate that SAMMS achieves near-optimal throughput and scales effectively to larger fleets and mine layouts.