Implementations of graph search, Markov-decision processes, Dubins/Reeds-Shepp curves, collision checking, convex optimization, driving games, and sequential-convex-programming (SCvx) trajectory planning, from the ETH PDM4AR course (Autumn 2025) — taught by Prof. Emilio Frazzoli's Institute for Dynamic Systems and Control.
Group project ex13 — Sequential Convex Programming (SCvx) for spaceship docking. The planner trades fuel against obstacle avoidance under non-convex 6-DoF dynamics, iteratively linearising around the current trajectory and solving a trust-region QP until it converges.
pdm4ar-coursework/
├── docs/
│ ├── images/ # Hero plots
│ └── media/ # Demo animations from the course evaluator
└── exercises/
├── individual-ex01-12/ # Solo exercises (Federico) — ex01 through ex12
├── group-ex13-spacecraft-docking/ # Group: SCvx for spaceship docking
└── group-ex14-multi-agent-goal-collection/ # Group final project
Each exercise's source code lives under src/pdm4ar/exercises/<exNN>/. The other directories in each sub-repo are the shared course framework (test harness, simulator, evaluator HTML report generator).
| Ex | Topic | Algorithm / approach | Type | Result |
|---|---|---|---|---|
| 01 | Set & graph basics | Union-find, set ops | Solo | — |
| 02 | Uninformed search | BFS, DFS, iterative deepening | Solo |  |
| 03 | Informed search | Uniform-cost search, A*, heuristics | Solo |  |
| 04 | MDPs | Value & Policy Iteration, Bellman backups | Solo |  |
| 05 | Steering curves | Dubins & Reeds-Shepp paths | Solo |  |
| 06 | Collision checking | AABB / triangle / convex-polygon primitives, optimised variants | Solo | — |
| 07 | Convex optimisation | LP / QP formulations | Solo | — |
| 08 | Driving games | Game-theoretic agent vs. other drivers | Solo | — |
| 09 | Rocket explorer | SCvx-style trajectory optimisation with rocket dynamics | Solo | — |
| 10 | Driving scenarios | Custom test scenario + agent | Solo | — |
| 11 | Spaceship | SCvx solo warm-up for ex13 | Solo | — |
| 12 | Driving agent | Final solo driving exercise | Solo | — |
| 13 | Spaceship docking | Sequential convex programming with non-convex dynamics + obstacle constraints | Group |  |
| 14 | Multi-agent goal collection | Goal-assignment + per-agent trajectory planning | Group |  |
Inline GIFs of the official course evaluator runs are embedded in the Highlights section below for Ex 13 and Ex 14. The full-resolution MP4s live under docs/media/.
A* finds the shortest path on actual OpenStreetMap graphs (ETH campus and Milan). The heuristic is straight-line distance; the cost is graph edge weight.
Left: optimal policy (arrows) recovered by policy iteration. Right: value function.
Closed-form shortest paths for car-like vehicles. Dubins assumes forward-only motion; Reeds-Shepp adds reverse, halving distance in tight situations.
The hardest one. A spaceship with non-convex 6-DoF dynamics must dock with a target while respecting thrust limits and avoiding obstacles.
Algorithm: Sequential Convex Programming (SCvx). A trust-region SQP-style scheme for non-convex optimal control:
- Discretise the continuous dynamics with multiple shooting →
discretization.py. - Linearise the dynamics + cost around the current trajectory; solve the resulting convex QP under a trust-region constraint →
planner.py. - Update the trajectory, shrink/grow the trust region based on the predicted-vs-actual cost reduction, repeat until convergence.
Implementation under exercises/group-ex13-spacecraft-docking/src/pdm4ar/exercises/ex13/ — agent.py, planner.py, discretization.py, satellite.py.
Simulated solution on public test config 3:
Converged trajectory with the applied thrust vectors:
Blue dots: SCvx-optimised trajectory. Black curve: actual trajectory when the controller follows the plan in closed loop. Red arrows: thrust vectors applied at each step — note how SCvx concentrates thrust during the sharp curvature changes.
Multiple agents have to collectively visit a set of goal locations, minimising joint travel time. We split the problem into:
- Goal clustering / assignment — each agent gets a subset of goals via a balanced k-means-style partition (
compute_trajectories.py). - Per-agent trajectory planning with collision avoidance, picking the visiting order with a greedy nearest-goal heuristic (
compute_commands.py).
Simulated solution on public test config 3:
Goal-clustering visualisations from the planner:
Each colour is the subset of goals assigned to one agent.
Implementation in exercises/group-ex14-multi-agent-goal-collection/src/pdm4ar/exercises/ex14/.
Each sub-folder is a self-contained Poetry project that mirrors the original course framework. From any of the three exercise folders:
cd exercises/<exercise-folder>
# Set up
poetry install # or `make install`
# Run the evaluation for a specific exercise (replace NN)
make exNN
# or directly:
poetry run python -m pdm4ar.main --exercise NNThis produces an out/NN/ folder with an HTML report containing animations, plots, and pass/fail evaluation.
- Federico Cominelli (@fedecomi04) — all individual exercises 01–12 + group exercises 13 & 14
Group teammates:
- Matteo Cozzi — ex13 and ex14
- Aleks Antonić — ex14
The shared course framework, simulator, and template code under each sub-folder is © the ETH PDM4AR course team and is included here so each exercise is runnable standalone. Only the per-exercise implementations under src/pdm4ar/exercises/exNN/ were written by us.
The exercise-specific implementations are released under the MIT License (see LICENSE). The course framework retains its original license — see the LICENSE file inside each exercise sub-folder.