The same shortest path, and why they cannot fly it together#
SLOP3969 · Week 9 · Same place, not the same search state
Two drones, two shortest paths#
Symbolic corridor model · smaller times for hand calculation
A’s shortest route to #13 goes through the corridor. B’s shortest route home goes through the corridor. Each one is the answer week 2 would give.
Each route is legal. Together they are not.#
| Drone | Wants the corridor | From the plan |
|---|---|---|
| B | [0, 6) | entered from G at 0, out at 6 |
| A | [3, 5) | at P at 3, across by 5 |
Overlap test: max(0, 3) = 3 is less than min(6, 5) = 5. They are in the corridor at the
same time. Neither plan is wrong on its own.
What a conflict is#
- A resource with an id: this corridor, both directions.
- Each use is a half-open interval
[start, end). - Two uses conflict when
max(s1, s2)is less thanmin(e1, e2).
Not “did they collide in this frame”. The whole interval, or nothing.
A path is places. A trajectory is places with times.#
Week 2 searched over place. That answered “which way”.
This week the state is (place, time). (P, 3) and (P, 4) are two different states,
because the future is different from each of them.
The bug that deletes waiting#
An implementation that remembers visited[P] refuses (P, 4), (P, 5), (P, 6) — it has
“been to P”. It reports no path.
With time in the state the legal sequence is:
(P, 3) → (P, 4) → (P, 5) → (P, 6) → (G, 8)
Wait three ticks, cross in two.
Waiting is not free#
- Waiting is allowed only at waiting points. P is one.
- On the ground it costs time. In the air it costs time and energy, and it occupies the waiting point.
- A at P is in the air. Three ticks of hover come off the same budget week 4 checked.
Time in the state does not solve energy. The engine keeps both.
The reservation table#
| Resource | Drone | Interval | Result |
|---|---|---|---|
| corridor | B | [0, 6) | held |
| corridor | A | [3, 5) | refused: overlaps B |
| corridor | A | [6, 8) | granted |
A route is a proposal. A reservation is a commitment. The table is what the second drone plans against.
Three ways to arrange it#
| Arrangement | Corridor | A’s delivery | Cost |
|---|---|---|---|
| both depart as planned | conflict [3, 5) | — | not a plan |
| B first, A waits at P | A [6, 8) | 3 ticks later | 3 ticks of hover |
| A detours around the block | none | 5 ticks later | longer flight |
The first one is the one the two shortest paths give you.
Which one is right?#
Week 5 fixed the objective: total lateness first, then the time every drone is back, then energy. In this symbolic arrival-time comparison, waiting adds 3 ticks and the detour adds 5. A full objective comparison must also include the return leg and energy.
Changing the promised time or adding a third drone may change which complete plan is preferred. That is why the choice is computed, not assumed.
Next week: search in time#
- A* again, over
(place, phase, time), under the reservations already committed. - Drones planned one at a time, in a priority order; each commits a full round trip.
- What it guarantees: a route checked against the reservations already committed, within the search limits. What it does not: the best plan for all of them together.
A single shortest route does not make a plan that can be flown together.#
Tutorial 9: mark the conflict, write the reservation query, and show the visited bug on
(P, 3) yourself.