File size: 3,346 Bytes
051c46f
 
 
 
 
 
 
 
 
c4c692c
 
051c46f
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
---
license: apache-2.0
tags:
- planning
- robotics
- simulation
- next-lab
---

![passage](https://cdn-uploads.huggingface.co/production/uploads/67d46bc5fe6ad6f6511d6f44/2D4Y52sSLir2ICTIXeu62.png)

# Next Passage

Next Passage routes a robot across a grid floor where **doors open and close on a schedule** and **obstacles patrol
corridors and randomly stall**. The planner searches over space *and time* (with a wait action), so it can wait for a
door or let an obstacle pass, and it replans whenever an obstacle deviates from its prediction. **Simulation only.**

**Space:** https://huggingface.co/spaces/thelamapi/Next-Passage — pick a scenario seed, obstacle density and stall probability; all three planners run in the browser.

## Results (600 test episodes per planner: 100 seeds × 3 densities × 2 stall rates)

| Planner | Arrived | Episodes with a collision | Door closed on robot / episode | Steps ÷ static shortest length | Replans / episode | Search nodes / episode | Python ms / episode |
|---|---:|---:|---:|---:|---:|---:|---:|
| Next Passage (time-aware) | 100.0% | 0.0% | 0.000 | 1.13 | 19.5 | 1438 | 10.9 |
| Static + reactive replanning | 100.0% | 50.0% | 0.173 | 1.26 | 1.7 | 434 | 1.3 |
| Static shortest path | 100.0% | 61.3% | 0.192 | 1.10 | 0.0 | 194 | 0.9 |

On the 600 episodes where every planner arrived, mean arrival steps were
30.8 (time-aware), 34.3 (reactive) and 30.1 (static).
The time-aware planner had 0 unsafe or unfinished episodes out of 600; they are listed in `evaluation.json`.

Share of episodes with any unsafe event (collision or door closing on the robot):

| Condition | Time-aware | Reactive | Static |
|---|---:|---:|---:|
| low/stall=0.1 | 0% | 36% | 53% |
| low/stall=0.25 | 0% | 41% | 48% |
| medium/stall=0.1 | 0% | 64% | 74% |
| medium/stall=0.25 | 0% | 61% | 72% |
| high/stall=0.1 | 0% | 76% | 88% |
| high/stall=0.25 | 0% | 77% | 85% |

![Final states on one high-density test seed](preview.png)

[Replay video](replay.mp4): one unselected test seed with all planners, then a failure case (static planner collision).

## Method
* Grid 21×15, three walls with one open gap and one scheduled door each, pillars, 3/6/10 patrolling obstacles.
* Obstacles advance one cell per step along a back-and-forth loop and stall with probability p. They ignore the robot.
* Time-aware planner: A* over (cell, t) with moves {wait, N, S, E, W}, heuristic = static BFS distance (admissible),
  horizon 160 steps; cells predicted to hold an obstacle at t or t−1 are avoided (covers swaps and single stalls); doors
  are entered only when open on arrival. It replans when an observed obstacle phase differs from its prediction.
* Collisions: robot and obstacle in the same cell after a step, or swapping cells.
* The JavaScript port in the Space reproduces Python exactly (Node parity: 6 cases, 0 mismatches).

## Usage
```bash
python inference.py --seed 20001 --density high --planner timed
python inference.py --selftest
```

## Limitations
* Discrete grid, perfect localisation and perfect knowledge of the door schedule; obstacles are observed exactly.
* Obstacles never react to the robot; real crowds and vehicles do.
* Search effort grows with horizon and obstacle count; a real system would need a time budget per replan.
* Recorded on NVIDIA L4 (Python timing); no physical robot was used.