Eventually Optimal and Scalable Multi-Agent Planning for Block Cave Mining

I. INTRODUCTION

• Block cave mining needs a transport plan that maximizes extraction while respecting drawbell-specific fractions of total ore extraction.The problem also couples assignment, scheduling, and path planning for indefinite operation, with vehicle maneuvering constrained by narrow tunnels.Source: §I · p. 1
• SAMM models task assignment, scheduling, and path planning in one MILP, producing cyclic plans and deciding the optimal agent count for a cycle.The cycle can be repeated because the team begins and ends in the same configuration.Source: §I · p. 1
• SAMMS replaces one long cycle with concatenated subcycles, each serving a subset of drawbells and returning to the same state.It selects new subcycles online and is proved asymptotically feasible, with draw rates approaching their targets as execution continues.Source: §I · p. 2

II. RELATED WORK

• Existing MAPF methods often assume grid movement and precomputed assignments and schedules, whereas SAMM jointly optimizes those decisions and agent count.These assumptions do not match BCM’s constrained navigation and continuous execution requirements.Source: §II · p. 2
• Prior scheduling heuristics cannot guarantee globally optimal schedules, while cited exact production methods neither generate optimal transport plans nor scale.The paper also notes that MILP-based MAPF approaches typically have limited scalability.Source: §II · p. 2, §I · p. 2

A. Mine

• A mine contains drawbells with coupled extraction rates, and each drawbell must contribute a fixed fraction of total extraction.The mine’s draw-ratio configuration records those fractions.Source: A. Mine · p. 2
• The Constant Time Roadmap is a directed pose graph whose edges represent moves between poses in one timestep.The roadmap must be strongly connected, and each drawbell and crusher must be accessible from at least one pose.Source: A. Mine · p. 2

B. Agents

• Agents transport ore by waiting, moving, picking it up from an accessible drawbell, and depositing it at an accessible crusher.The actions operate at poses where the relevant drawbell or crusher can be serviced.Source: B. Agents · pp. 2–3
• Each agent carries a one-unit-capacity shovel, and pickup and deposit actions take specified numbers of timesteps.An agent remains at its pose until either action is complete; its state records pose and whether its shovel is empty or full.Source: B. Agents · p. 3

C. Collision

• Pose and edge conflict sets encode which simultaneous occupancies and movements would cause collisions.Agents may not occupy poses in the same conflict set or traverse edges in the same conflict set during the same timestep.Source: C. Collision · p. 3

D. Transport Plan

• A cyclic transport plan runs for a finite cycle and matches each agent’s end state to a starting state under an agent permutation.The cycle can then be repeated indefinitely by relabeling agents according to that permutation.Source: D. Transport Plan · p. 3
• A cyclic plan is valid only if agents can realize it through wait, move, pickup, and deposit actions without pose or edge conflicts.The plan must also satisfy the stated correspondence between its starting and ending agent states.Source: D. Transport Plan · p. 3

E. The Block Cave Mining (BCM) Problem

• BCM formalizes transport planning as maximizing throughput over valid cyclic plans for a mine instance with a specified draw-ratio configuration.The instance comprises a constant-time roadmap, drawbells, crushers, and draw ratios.Source: E. The Block Cave Mining (BCM) Problem · p. 3

IV. BLOCK CAVE MINE BENCHMARKS

• Benchmark drawbell tunnels are narrow, dead-end routes where opposing paths cannot pass, and agents must reverse to reach some drawbells.The benchmark layout also includes a main tunnel and crusher tunnels; Fig. 2 marks turning poses in orange.Source: §IV · p. 3, Figure 2 · p. 4
• The benchmark generator varies the number and density of drawbell tunnels, drawbells per tunnel, and crusher tunnels.Source: §IV · p. 4

V. THE SIMPLE ANYTIME MINE MAPF SOLVER

• SAMM is introduced as an anytime BCM solver; it finds fixed-cycle solutions by running FLIMM at progressively larger cycle lengths.The solver section states that SAMM is eventually optimal.Source: §V · p. 4

A. The Fixed Length ILP-based Mine MAPF Solver

• FLIMM’s ILP represents agent occupancy, movement, ore pickups, and deposits over poses, shovel states, and timesteps, with an objective to maximize ore removal.With the reference draw rate fixed, maximizing this rate is equivalent to maximizing the pickup rate.Source: A. The Fixed Length ILP-based Mine… · p. 4
• An empty-shovel agent may move, wait, or pick up ore; a full-shovel agent may move, wait, or deposit ore at an accessible crusher.Source: A. The Fixed Length ILP-based Mine… · p. 4
• Pickup and deposit actions lasting multiple timesteps are modeled with required waits before or after the action.The passages note that both durations are usually one timestep in the evaluations.Source: A. The Fixed Length ILP-based Mine… · p. 4
• The next-state constraint places an empty-shovel agent at a pose if it moved there empty or deposited ore there on the preceding timestep.Source: A. The Fixed Length ILP-based Mine… · p. 4
• Collision constraints limit simultaneous occupancy of conflicting poses and traversal of conflicting edges, while the draw-ratio constraint enforces relative draw rates.Source: A. The Fixed Length ILP-based Mine… · p. 5
• CONVFLIMM converts solved variables into agent trajectories and maps terminal states to initial states to form the agent permutation.Source: A. The Fixed Length ILP-based Mine… · p. 5
• SAMM repeatedly solves FLIMM at increasing cycle lengths, converts each solution to a plan, and retains the best-throughput plan found before timeout.If the timer expires while FLIMM is running, it returns NULL.Source: A. The Fixed Length ILP-based Mine… · p. 5

B. The Simple Anytime Mine MAPF (SAMM) solver

• SAMM iteratively runs FLIMM at progressively increasing cycle lengths until the timer expires, then returns the best plan found.If time expires during a FLIMM call, that call returns NULL.Source: B. The Simple Anytime Mine MAPF (SAMM)… · p. 5
• SAMM is eventually optimal because increasing cycle lengths eventually reaches the optimal plan’s cycle length, where FLIMM finds the fixed-length optimum.Source: B. The Simple Anytime Mine MAPF (SAMM)… · p. 5
• The evaluations initialize SAMM at cycle length T = 6 because very short cycles are typically impractical.Source: B. The Simple Anytime Mine MAPF (SAMM)… · p. 5

C. Accelerating SAMM

• Complex draw ratios may require long cycles, while FLIMM’s worst-case runtime grows exponentially with cycle length.Source: C. Accelerating SAMM · p. 6
• FDR-FLIMM relaxes the constraint requiring each drawbell’s rate to match its target rate during planning.Source: C. Accelerating SAMM · p. 6
• At execution time, FDR-FLIMM skips a pickup when it would push a drawbell’s average extraction rate above its target, replacing it with wait actions.Source: C. Accelerating SAMM · p. 6
• FDR-FLIMM’s fixed-cycle throughput is no worse than FLIMM’s because relaxing a constraint preserves FLIMM’s feasible solutions while allowing additional ones.FDR-SAMM is also eventually optimal, as stated for the corresponding variant.Source: C. Accelerating SAMM · p. 6

VI. SAMM WITH SUBCYCLES

• SAMMS replaces a single long cycle serving every drawbell with a sequence of subcycles, selecting the next subcycle online whenever one completes.The ILP complexity of constructing a cyclic plan grows exponentially with cycle length.Source: §VI · p. 6
• SAMMS partitions drawbells into families, builds a reference subcycle for the family containing the reference drawbell, then generates subcycles for the other families.Each drawbell belongs to exactly one family.Source: §VI · p. 6
• Each subcycle uses the reference subcycle’s number of agents and starts and ends with those agents in the same state.This shared boundary state allows the subcycles to be composed in any order.Source: §VI · pp. 6–7
• For each reduced family, REDUCEBCM selects a highest-draw-rate reference drawbell and rescales draw ratios relative to that reference.It expresses each drawbell’s ratio as rj/ρi, where ρi is the reference drawbell’s ratio relative to the original reference.Source: §VI · p. 7
• Nonreference subcycles use FS-SAMM, whose FS-FLIMM variant constrains the agents’ initial state to match the reference state.FS-SAMM replaces SAMM’s FLIMM call with FS-FLIMM.Source: §VI · pp. 6–7
• COMPOSESUBCYCLES adjusts subcycle execution frequencies to meet draw ratios; violations converge to zero at O(1/n) as n subcycles execute.Exact execution ratios can be difficult to achieve when the target ratios are not simple.Source: §VI · p. 7

A. Analysis

• After L COMPOSESUBCYCLES loops, each drawbell’s draw rate is within O(1/L) of its target draw rate.The theorem states this asymptotic-feasibility guarantee for any BCM instance.Source: A. Analysis · p. 7
• A drawbell’s realized ratio to the reference drawbell is proportional to its family’s realized execution ratio, so it converges to the target at the same rate.The analysis applies this relation to drawbells in a nonreference family.Source: A. Analysis · p. 7
• After L loops, each subcycle ξk has been executed exactly ⌊ηk · L⌋ times, so its realized execution ratio approaches ηk at O(1/L).The reference subcycle has execution ratio η1 = 1.Source: A. Analysis · p. 7

VII. EXPERIMENTAL RESULTS

• The evaluation measures solution quality as throughput and also compares computational time across mine scenarios.The table caption identifies SAMM-versus-SAMMS throughput and runtime across scenarios.Source: §VII · p. 7, Table I · p. 8
• The solvers were tested on five scenarios, with a 60-second time limit per experiment and termination after two FLIMM runs without improvement.Pickup and deposit times were each set to one timestep.Source: §VII · p. 7
• Experiments ran on an Intel Core Ultra 9 275HX × 24 CPU, NVIDIA GeForce RTX 5080 Laptop GPU, and 32 GiB RAM.The system ran Ubuntu 24.04.3 LTS.Source: §VII · p. 8

A. Results.

• An order of magnitude faster runtimes were achieved by SAMMS than SAMM through decomposition into smaller, independent subproblems.SAMM did not scale to the two larger scenarios.Source: A. Results · p. 8
• SAMMS solved 5/5 runs in each scenario except scenarios 5 and 7, where it solved 4/5 runs.The evaluation ran each solver five times per scenario.Source: A. Results · p. 8
• Throughput remained relatively low even with many crushers because maneuvering agents into and out of crushers occupied them for extended periods.A deposit action itself took only one timestep.Source: A. Results · p. 8

• SAMM jointly solves task assignment, scheduling, and path planning via MILP as an eventually optimal anytime solver.Source: §VIII · p. 8
• SAMMS decomposes planning into shorter subcycles, trading optimality for computational efficiency to address MILP scalability limits.Source: §VIII · p. 8
• Experiments on real-world mine scenarios demonstrate that SAMMS can be applied to industrial-scale BCM instances.Source: §VIII · p. 8