DEPTH ACTIVE
Runner Up Award — IEPC 2026, first Epistemic Planning track of the International Planning Competition (ICAPS 2026, Dublin)
About
DEPTH (DEL Epistemic Planner with Tier Heuristics) won the Runner Up Award at the first International Epistemic Planning Competition (IEPC 2026) — the inaugural Epistemic Planning track of the International Planning Competition, held at ICAPS 2026 in Dublin on 28 June 2026. Entries were ranked on correctness first, then coverage, then efficiency; DEPTH placed second.
Built in C++17 on top of the plank toolkit and packaged as an Apptainer container, it supports EPDDL specifications across the basic, intermediate, and hard levels. The core algorithm, Epistemic H*, is a two-queue best-first search adapted to Dynamic Epistemic Logic (DEL) — a transposition to the epistemic setting of the H* motion planner originally introduced for Navigation Among Movable Obstacles.
A primary queue (OPEN) advances toward the goal by prioritising successors that strictly improve a coarse but informative tier heuristic, while a secondary queue (INCONS) retains setup actions (announcements, sensing steps, signal-passing) whose effect is invisible to the heuristic but enables later goal-achieving actions; when OPEN is empty, INCONS is flushed back into it, ensuring completeness despite the inadmissible heuristic. Bisimulation contraction is applied to every successor, so logically indistinguishable states are identified regardless of how they were reached. Epistemic H* is proven complete for finite DEL planning tasks.
On the competition sample benchmarks, DEPTH solves Grapevine (32 worlds) in milliseconds where the reference BFS planner exhausts the 60-second timeout.
Built in C++17 on top of the plank toolkit and packaged as an Apptainer container, it supports EPDDL specifications across the basic, intermediate, and hard levels. The core algorithm, Epistemic H*, is a two-queue best-first search adapted to Dynamic Epistemic Logic (DEL) — a transposition to the epistemic setting of the H* motion planner originally introduced for Navigation Among Movable Obstacles.
A primary queue (OPEN) advances toward the goal by prioritising successors that strictly improve a coarse but informative tier heuristic, while a secondary queue (INCONS) retains setup actions (announcements, sensing steps, signal-passing) whose effect is invisible to the heuristic but enables later goal-achieving actions; when OPEN is empty, INCONS is flushed back into it, ensuring completeness despite the inadmissible heuristic. Bisimulation contraction is applied to every successor, so logically indistinguishable states are identified regardless of how they were reached. Epistemic H* is proven complete for finite DEL planning tasks.
On the competition sample benchmarks, DEPTH solves Grapevine (32 worlds) in milliseconds where the reference BFS planner exhausts the 60-second timeout.
Gallery
