RCSPP - Resource-Constrained Search

OOSPP, OMSPP and MOSPP Under a Resource Budget

Motivation
  1. Real agents carry a limited resource: battery, fuel or supplies.
  2. Moving drains it, and an empty agent is stuck.
  3. The resource is recharged only at chargers, placed at a few fixed locations.
  4. The shortest path may be infeasible: the agent runs out on the way.
  5. The purpose is to find the shortest feasible path: it may detour through a charger.
A truck runs out of battery on the straight path from S to G; a longer path around a row of obstacles passes a charger and reaches G.
Figure 1: Shortest Path vs Shortest Feasible Path.

Let’s examine our OOSPP, OMSPP and MOSPP algorithms in the RCSPP setting.

Definition

Problem

  1. Graph: nodes VV; a move from vv to a successor v′v' costs w(v,v′)≥0w(v, v') \ge 0.
  2. Start and goal: nodes S,G∈VS, G \in V.
  3. Chargers: nodes C⊆VC \subseteq V where the agent gains resource.
  4. Resource left: rleft∈R={0,1,…,rmax}r_{\mathrm{left}}\in R = \{0, 1, \dots, r_{\max}\}, carried by the agent.
  5. State: (v,rleft)∈V×R(v, r_{\mathrm{left}}) \in V \times R — the agent is at node vv with rleftr_{\mathrm{left}} left.
  6. Start state: (S,rstart)(S, r_{\mathrm{start}}); Goal states: (G,rleft)(G, r_{\mathrm{left}}).
  7. Task: a minimum-cost feasible path from SS to GG — the resource never drops below 00.

Move Rule

  1. Node delta: entering vv changes the resource by rΔ(v)r_{\Delta}(v).
  2. At a charger, the agent gains resource: v∈Cv \in C, rΔ(v)=rcharge(v)≥0r_{\Delta}(v) = r_{\mathrm{charge}}(v) \ge 0.
  3. At any other node, the agent loses resource: v∉Cv \notin C, rΔ(v)=rdrain(v)≤0r_{\Delta}(v) = r_{\mathrm{drain}}(v) \le 0.
  4. Successor (v,rleft)→(v′,rleft′)(v, r_{\mathrm{left}}) \to (v', r'_{\mathrm{left}}): rleft′=min⁡(rleft+rΔ(v′),rmax)r'_{\mathrm{left}}= \min(r_{\mathrm{left}}+ r_{\Delta}(v'),\, r_{\max}).
    The resource never exceeds its capacity rmaxr_{\max}.
  5. Prune: rleft=0r_{\mathrm{left}}= 0 or rleft′<0r'_{\mathrm{left}}< 0 ⇒\Rightarrow no successor.
    An empty agent cannot move; a negative resource is invalid.
A graph from S to G: the shortest path runs empty at A and is pruned; a longer path charges at B first, clamped to r_max, and reaches G. A holds two states. Legend: all w = 1, edge label = r_delta, battery = r_left, bolt = charger.
Figure 2: An RCSPP Instance.
Dominance

Why We Need It

  1. Up to rmaxr_{\max} RCSPP states of a node are redundant.
    Less rleftr_{\mathrm{left}} at no lower gg ⇒\Rightarrow another takes all its paths, at no higher cost.
  2. Plain search keeps redundant states.
    It never compares two RCSPP states of one node.
  3. Comparing two RCSPP states needs gg and rleftr_{\mathrm{left}} together: a label ℓ=(v,g,rleft)\ell = (v, g, r_{\mathrm{left}}).
    More rleftr_{\mathrm{left}} at a higher gg is a trade-off (neither is better): both kept.
  4. Redundant labels waste memory and runtime.
Node A as a box of its labels, r_max = 3, all with g = 1 and r_left 3 to 0. (A, 1, 3) is kept; (A, 1, 2), (A, 1, 1) and (A, 1, 0) are redundant: less r_left.
Figure 4: Kept and Redundant Labels at One Node.
Dominance

Label ℓ1\ell_1 dominates label ℓ2≠ℓ1\ell_2 \ne \ell_1 if

v(ℓ1)=v(ℓ2),g(ℓ1)≤g(ℓ2),rleft(ℓ1)≥rleft(ℓ2).\begin{aligned} v(\ell_1) &= v(\ell_2), \\ g(\ell_1) &\le g(\ell_2), \\ r_{\mathrm{left}}(\ell_1) &\ge r_{\mathrm{left}}(\ell_2). \end{aligned}

If ℓ1\ell_1 dominates ℓ2\ell_2, then ℓ2\ell_2 is pruned.

No optimal (cheapest) path is lost.
The move rule is monotone (more rleftr_{\mathrm{left}} never hurts).
So ℓ1\ell_1 can take every path ℓ2\ell_2 can, at no higher cost.

Kept
ℓ1\ell_1 vs ℓ2\ell_2 r1>r2r_1 > r_2 r1=r2r_1 = r_2 r1<r2r_1 < r_2
g1<g2g_1 < g_2 ℓ1\ell_1 ℓ1\ell_1 both
g1=g2g_1 = g_2 ℓ1\ell_1 ℓ1\ell_1 ℓ2\ell_2
g1>g2g_1 > g_2 both ℓ2\ell_2 ℓ2\ell_2
Table 1: Which Label Is Kept.
ℓ1bothbothℓ2grleftℓ2

Figure 5: Table 1 on the Plane.
ℓ2\ell_2 fixed; hover or tap to move ℓ1\ell_1.

Who Prunes Whom, and When

  1. Two labels of the same node vv can take part in a dominance check: ℓ1\ell_1 and ℓ2\ell_2.
  2. ℓ1\ell_1 (the dominating label) must be an expanded label (in CLOSED).
  3. ℓ2\ell_2 (the label being checked) is checked only at two points:
    When generated (before OPEN).
    When popped from OPEN as the best.
  4. We call a dominated ℓ2\ell_2 pruned, as in a search tree.
    It is never expanded, so it has no children (its branch is cut off).
  5. Only rleftr_{\mathrm{left}} needs a check: same-node labels are expanded in non-decreasing gg.
    Same node ⇒\Rightarrow same hh ⇒\Rightarrow the ff order is the gg order (rleftr_{\mathrm{left}} only breaks ties).
  6. One threshold per node is enough: rbest[v]r_{\mathrm{best}}[v], the highest rleftr_{\mathrm{left}} expanded at vv.
  7. Tie-break: among equal gg, the higher rleftr_{\mathrm{left}} pops first.
    So ℓ1\ell_1 is expanded before ℓ2\ell_2, even at equal gg.
  8. Note: OPEN can hold labels dominated by labels in CLOSED.
    It happens when ℓ2\ell_2 was generated before ℓ1\ell_1 was expanded.
  9. There is an option, not tested yet: let ℓ1\ell_1 be in OPEN too.
    It saves memory but adds checks.
Flow of a label l2 at node v: generated, checked (dominated? yes: prune), enters OPEN, popped as the best, checked again (yes: prune), else enters CLOSED. Both checks compare l2 with l1, a label in CLOSED.
Figure 6: The Two Dominance Checks.
Setup

Grid

  1. Grid: the nodes VV are free cells (not obstacles); |V||V| is their number.
  2. 4-connected: a move goes up, down, left or right.
  3. A*’s hh: the Manhattan distance to GG.
  4. Unit weight: w(v,v′)=1w(v, v') = 1 ⇒\Rightarrow a path’s cost is its number of steps.
  5. Unit drain: rdrain(v)=−1r_{\mathrm{drain}}(v) = -1 for every v∉Cv \notin C.
  6. 25 maps in 5 domains, from the MovingAI benchmark.

Berlin_2_1024, its window enlarged

Cities
Berlin_2_1024

ost100d, its window enlarged

Games
ost100d

maze512-16-5, its window enlarged

Mazes
maze512-16-5

random512-20-2, its window enlarged

Random
random512-20-2

32room_002, its window enlarged

Rooms
32room_002

Figure 7: One Map per Domain.
Below each map: its window, enlarged.
Legend: free, obstacle.

Capacity

  1. rstart=rmax=rcharger_{\mathrm{start}} = r_{\max} = r_{\mathrm{charge}}: set equal, for simplicity.
  2. The agent starts full.
  3. Each charger refills it to full.
Nine cells in a row: S, three cells, a charger, three cells, G; r_max = 4. The resource is full at S, then three quarters, half, a quarter, full again at the charger, then down to empty at G.
Figure 8: Start Full, Refill to Full.

Chargers

  1. |V|/rmax|V| / r_{\max} random chargers.
  2. The smallest rmaxr_{\max} has all the chargers; a larger one keeps |V|/rmax|V| / r_{\max} of them.
One open map of 120 cells, drawn five times in a row, for r_max = 10, 20, 30, 40 and 50, with |C| = 12, 6, 4, 3 and 2 chargers, as filled circles; each larger r_max keeps some of the previous ones.
Figure 9: Fewer Chargers for a Larger Capacity.
One open map of 120 cells.
Metrics

Feasibility

Feasibility: Rate of feasible instances.

Three small maps, r_max = 4. (a) G is 3 moves from S: feasible in SPP and RCSPP. (b) G is 5 moves away, no charger: the agent is empty after 4, feasible in SPP only. (c) G is sealed in a pocket: feasible in neither.
Figure 10: Three Kinds of Pairs.
Feasibility: SPP 2/3, RCSPP 1/3.

The metrics below use feasible instances only.

Cost and States

  1. Cost ratio: cRCSPP*/cSPP*c^*_{\mathrm{RCSPP}} / c^*_{\mathrm{SPP}} (≥ 1: every RCSPP path is an SPP path).
  2. Longer-path rate: Rate of instances with cost ratio > 1.
Two small maps, r_max = 4, G 5 moves from S. (a) The charger is on the straight path: SPP and RCSPP both cost 5, cost ratio 1. (b) The charger is one row below: SPP goes straight, cost 5; RCSPP detours through the charger, cost 7, cost ratio 1.4.
Figure 11: Cost Ratio of Two Feasible Pairs.
Longer-path rate: 1/2.
  1. States per node: Expanded states / expanded nodes.
    SPP: always 1 (one state per node). RCSPP: up to rmax+1r_{\max} + 1 (one per rleftr_{\mathrm{left}}, 0 to rmaxr_{\max}).

Search Effort

RCSPP / SPP (same algorithm, SS and GG).

  1. Expansions: number of expanded states.
  2. Memory: peak number of slots.
    |CLOSED|+|OPEN||\mathrm{CLOSED}| + |\mathrm{OPEN}| (one slot per state).
  3. Runtime: cumulative wall-clock in seconds.
OOSPP
Setup

Sweep

  1. rmaxr_{\max} = 10, 20, 30, 40, 50 moves.
  2. 2 random charger placements (seeds 0 and 1).

Pairs

  1. 20 random pairs per map: a start and a goal drawn uniformly over its free cells.
  2. No trivial pair: each is at least 100 apart (Manhattan).
    Distance ≥ 100 > every rmaxr_{\max} ⇒\Rightarrow each pair needs a charger.
  3. Infeasible pairs stay: a pair infeasible at one rmaxr_{\max} may be feasible at another.

Algorithms

  1. SPP: BFS and A*.
  2. RCSPP: BFS and A*, both with dominance.

Instances

  1. SPP: 500 instances: 25 maps × 20 pairs.
  2. RCSPP: 5,000 instances: 500 pairs × 5 capacities × 2 placements.
Feasibility
Figure 12: Feasible Pairs by Capacity.
Feasible Pairs
rmax SPP RCSPP
10 99.0% 82.4%
20 99.0% 87.7%
30 99.0% 89.4%
40 99.0% 88.9%
50 99.0% 89.8%
Table 2: Feasible Pairs by Capacity.

Reasons

RCSPP
▲ Capacity ⇒\Rightarrow ▲ Crossable gap between chargers ⇒\Rightarrow ▲ Feasible pairs.

Figure 13: Feasible Cells in a Corridor, by Capacity.
Legend: feasible, infeasible, charger, obstacle.
Cost
Figure 14: Longer-Path Rate by Capacity.
Longer-Path Rate
rmax %
10 76.3
20 60.3
30 50.1
40 42.4
50 38.4
Table 3: Longer-Path Rate by Capacity.

Reasons

RCSPP
▲ Capacity ⇒\Rightarrow ▼ Forced charger stops ⇒\Rightarrow ▼ Longer paths.

Cost Ratio
Figure 15: Cost Ratio of Longer Paths by Capacity.
Cost Ratio
rmax Mean Max
10 1.044× 1.331×
20 1.021× 1.109×
30 1.017× 1.098×
40 1.013× 1.058×
50 1.011× 1.063×
Table 4: Cost Ratio of Longer Paths by Capacity.

Reasons

RCSPP
▲ Capacity ⇒\Rightarrow ▼ Forced charger stops ⇒\Rightarrow ▼ Extra steps per longer path (mean 23 → 9).

States per Node
Figure 16: States per Node by Capacity.
Each point: the mean over feasible pairs and both placements.
States per Node
rmax BFS A*
10 2.12 1.67
20 2.53 1.85
30 2.75 1.93
40 2.88 1.97
50 2.97 2.00
Table 5: States per Node by Capacity.
Each point: the mean over feasible pairs and both placements.

Reasons

BFS, A*
Dominance ⇒\Rightarrow A new state of vv needs more rleftr_{\mathrm{left}} than rbest[v]r_{\mathrm{best}}[v] ⇒\Rightarrow Few states per node.

Expansions
Figure 17: Expansions Ratio by Capacity.
1. Each point: the mean over feasible pairs and both placements.
2. (*) Crossover point by linear interpolation.
Ratio to SPP
rmax BFS A*
10 2.10× 4.81×
20 2.52× 3.68×
30 2.74× 3.04×
40 2.87× 2.80×
50 2.96× 2.62×
Table 6: Expansions Ratio by Capacity.
1. Each point: the mean over feasible pairs and both placements.
2. (*) Crossover point by linear interpolation.

Reasons

BFS
No hh ⇒\Rightarrow About the same nodes as SPP ⇒\Rightarrow Ratio ≈\approx states per node.

A*
▼ Capacity ⇒\Rightarrow ▲ Detours (c*>hc^* > h) ⇒\Rightarrow ▲ Band to expand.

At rmaxr_{\max} = 10, a few pairs lift A*’s mean: its median is 2.07×.

Memory
Figure 18: Memory Ratio by Capacity.
Each point: the mean over feasible pairs and both placements.
Ratio to SPP
rmax BFS A*
10 2.10× 4.24×
20 2.52× 3.74×
30 2.75× 3.29×
40 2.87× 3.11×
50 2.96× 3.01×
Table 7: Memory Ratio by Capacity.
Each point: the mean over feasible pairs and both placements.
Runtime
Figure 19: Runtime Ratio by Capacity.
Each point: the mean over feasible pairs and both placements.
Ratio to SPP
rmax BFS A*
10 3.57× 7.91×
20 4.24× 6.30×
30 4.63× 5.86×
40 4.86× 5.11×
50 5.02× 5.06×
Table 8: Runtime Ratio by Capacity.
Each point: the mean over feasible pairs and both placements.
By Domain
Figure 20: Pairs by Domain, at rmaxr_{\max} = 30.
Legend: Feasible (of all pairs), Longer (of the feasible ones).
Pairs (%) Cost Ratio Expansions Ratio
Domain Feasible Longer Mean BFS A*
Cities 96.0 28.1 1.003× 2.97× 3.75×
Games 99.0 30.8 1.004× 2.75× 2.32×
Mazes 52.0 95.2 1.016× 2.62× 2.01×
Random 100.0 53.0 1.012× 2.67× 4.15×
Rooms 100.0 64.0 1.010× 2.65× 2.47×
Table 9: Domains at rmaxr_{\max} = 30.

Reasons

Mazes
One corridor per route ⇒\Rightarrow No way around a stretch without a charger ⇒\Rightarrow Lost pairs, longer paths.

The other domains
Many routes ⇒\Rightarrow One passes a charger in time ⇒\Rightarrow 0% of the lost pairs (feasible in SPP, not in RCSPP).

By Distance
Figure 21: Pairs by Distance, at rmaxr_{\max} = 30.
1. Each point: one fifth of the pairs, at its mean distance.
2. √|V||V|: about the map’s width.
3. Legend: Feasible (of all pairs), Longer (of the feasible ones).

Reasons

The farthest fifth
62% Cities (open maps) ⇒\Rightarrow Many routes ⇒\Rightarrow Fewer longer paths.

Placement
Figure 22: Expansions Ratio by Capacity and Charger Placement.
Solid: seed 0; dashed: seed 1.
(*) Crossover point by linear interpolation: seed 0 below, seed 1 above.
Feasible (%) Cost Ratio A* Expansions BFS Expansions
rmax Seed 0 Seed 1 Seed 0 Seed 1 Seed 0 Seed 1 Seed 0 Seed 1
10 83.4 81.4 1.034× 1.034× 4.76× 4.86× 2.10× 2.09×
20 87.4 88.0 1.013× 1.012× 3.96× 3.40× 2.52× 2.52×
30 89.2 89.6 1.009× 1.008× 3.05× 3.03× 2.74× 2.74×
40 88.0 89.8 1.006× 1.006× 2.82× 2.78× 2.87× 2.88×
50 89.0 90.6 1.005× 1.004× 2.49× 2.74× 2.96× 2.96×
Table 10: Results by Capacity and Charger Placement.

Reasons

Each pair
Other chargers ⇒\Rightarrow Other detours ⇒\Rightarrow Its cost may change; the means hold (94–100% keep their verdict, 29–57% their cost).