- Real agents carry a limited resource: battery, fuel or supplies.
- Moving drains it, and an empty agent is stuck.
- The resource is recharged only at chargers, placed at a few fixed locations.
- The shortest path may be infeasible: the agent runs out on the way.
- The purpose is to find the shortest feasible path: it may detour through a charger.
Let’s examine our OOSPP, OMSPP and MOSPP algorithms in the RCSPP setting.
Problem
- Graph: nodes ; a move from to a successor costs .
- Start and goal: nodes .
- Chargers: nodes where the agent gains resource.
- Resource left: , carried by the agent.
- State: — the agent is at node with left.
- Start state: ; Goal states: .
- Task: a minimum-cost feasible path from to — the resource never drops below .
Move Rule
- Node delta: entering changes the resource by .
- At a charger, the agent gains resource: , .
- At any other node, the agent loses resource: , .
- Successor : .
The resource never exceeds its capacity . - Prune: or no successor.
An empty agent cannot move; a negative resource is invalid.
Plain Search
- Plain search: any SPP search on (BFS, Dijkstra, A*).
“Plain”: the search as is; Dominance improves on it. - A*’s on : an SPP heuristic, blind to : .
Still admissible (never overestimates): an RCSPP path is an SPP path . - OPEN and CLOSED: the states to expand, and the expanded ones.
A step: pop (take a state out of OPEN), then expand it (generate its successors). - Duplicate check by state: one entry per in OPEN or CLOSED.
In OPEN: the lower stays.
In CLOSED: pruned (as in SPP: popped with its lowest expanded once). - A node splits into up to states, one per .
So plain search can expand a node up to times.
Why We Need It
- Up to RCSPP states of a node are redundant.
Less at no lower another takes all its paths, at no higher cost. - Plain search keeps redundant states.
It never compares two RCSPP states of one node. - Comparing two RCSPP states needs and together: a label .
More at a higher is a trade-off (neither is better): both kept. - Redundant labels waste memory and runtime.
Label dominates label if
If dominates , then is pruned.
No optimal (cheapest) path is lost.
The move rule is monotone (more never hurts).
So can take every path can, at no higher cost.
| Kept | |||
|---|---|---|---|
| vs | |||
| both | |||
| both | |||
fixed; hover or tap to move .
Who Prunes Whom, and When
- Two labels of the same node can take part in a dominance check: and .
- (the dominating label) must be an expanded label (in CLOSED).
- (the label being checked) is checked only at two points:
When generated (before OPEN).
When popped from OPEN as the best. - We call a dominated pruned, as in a search tree.
It is never expanded, so it has no children (its branch is cut off). - Only needs a check: same-node labels are expanded in non-decreasing .
Same node same the order is the order ( only breaks ties). - One threshold per node is enough: , the highest expanded at .
- Tie-break: among equal , the higher pops first.
So is expanded before , even at equal . - Note: OPEN can hold labels dominated by labels in CLOSED.
It happens when was generated before was expanded. - There is an option, not tested yet: let be in OPEN too.
It saves memory but adds checks.
Grid
- Grid: the nodes are free cells (not obstacles); is their number.
- 4-connected: a move goes up, down, left or right.
- A*’s : the Manhattan distance to .
- Unit weight: a path’s cost is its number of steps.
- Unit drain: for every .
- 25 maps in 5 domains, from the MovingAI benchmark.
Cities
Berlin_2_1024
Games
ost100d
Mazes
maze512-16-5
Random
random512-20-2
Rooms
32room_002
Below each map: its window, enlarged.
Legend: free, obstacle.
Capacity
- : set equal, for simplicity.
- The agent starts full.
- Each charger refills it to full.
Chargers
- random chargers.
- The smallest has all the chargers; a larger one keeps of them.
One open map of 120 cells.
Feasibility
Feasibility: Rate of feasible instances.
Feasibility: SPP 2/3, RCSPP 1/3.
The metrics below use feasible instances only.
Cost and States
- Cost ratio: (≥ 1: every RCSPP path is an SPP path).
- Longer-path rate: Rate of instances with cost ratio > 1.
Longer-path rate: 1/2.
- States per node: Expanded states / expanded nodes.
SPP: always 1 (one state per node). RCSPP: up to (one per , 0 to ).
Search Effort
RCSPP / SPP (same algorithm, and ).
- Expansions: number of expanded states.
- Memory: peak number of slots.
(one slot per state). - Runtime: cumulative wall-clock in seconds.
Sweep
- = 10, 20, 30, 40, 50 moves.
- 2 random charger placements (seeds 0 and 1).
Pairs
- 20 random pairs per map: a start and a goal drawn uniformly over its free cells.
- No trivial pair: each is at least 100 apart (Manhattan).
Distance ≥ 100 > every each pair needs a charger. - Infeasible pairs stay: a pair infeasible at one may be feasible at another.
Algorithms
- SPP: BFS and A*.
- RCSPP: BFS and A*, both with dominance.
Instances
- SPP: 500 instances: 25 maps × 20 pairs.
- RCSPP: 5,000 instances: 500 pairs × 5 capacities × 2 placements.
| 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% |
Reasons
RCSPP
▲ Capacity ▲ Crossable gap between chargers ▲ Feasible pairs.
Legend: feasible, infeasible, charger, obstacle.
| Longer-Path Rate | |
|---|---|
| rmax | % |
| 10 | 76.3 |
| 20 | 60.3 |
| 30 | 50.1 |
| 40 | 42.4 |
| 50 | 38.4 |
Reasons
RCSPP
▲ Capacity ▼ Forced charger stops ▼ Longer paths.
| 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× |
Reasons
RCSPP
▲ Capacity ▼ Forced charger stops ▼ Extra steps per longer path (mean 23 → 9).
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 |
Each point: the mean over feasible pairs and both placements.
Reasons
BFS, A*
Dominance A new state of needs more than Few states per node.
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× |
1. Each point: the mean over feasible pairs and both placements.
2. (*) Crossover point by linear interpolation.
Reasons
BFS
No About the same nodes as SPP Ratio states per node.
A*
▼ Capacity ▲ Detours () ▲ Band to expand.
At = 10, a few pairs lift A*’s mean: its median is 2.07×.
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× |
Each point: the mean over feasible pairs and both placements.
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× |
Each point: the mean over feasible pairs and both placements.
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× |
Reasons
Mazes
One corridor per route No way around a stretch without a charger Lost pairs, longer paths.
The other domains
Many routes One passes a charger in time 0% of the lost pairs (feasible in SPP, not in RCSPP).
1. Each point: one fifth of the pairs, at its mean distance.
2. √: about the map’s width.
3. Legend: Feasible (of all pairs), Longer (of the feasible ones).
Reasons
The farthest fifth
62% Cities (open maps) Many routes Fewer longer paths.
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× |
Reasons
Each pair
Other chargers Other detours Its cost may change; the means hold (94–100% keep their verdict, 29–57% their cost).