Motion Planning

Try it: https://bruninlima.github.io/MotionPlanning/

Shortest paths for a polygonal robot that slides (without rotating) among polygonal obstacles. Draw the robot and the obstacles in the browser, place a start and a goal, and watch the robot follow the path. The geometry and planning are written in Rust and run in the browser as WebAssembly.

Using it

Tool	What it does
Start & goal	Tap to place the start, then the goal.
Robot	Tap the robot's corners; tap the first corner (or Finish shape) to close it. Its centre becomes the start.
Obstacle	Same, for a new obstacle.
Edit	Drag corners, obstacles, the robot, the start or the goal. Tap an obstacle to select it, then delete it.

The path updates as you edit. You can also:

• choose what the robot knows before it sets off (the whole map, only where the goal is, or nothing) and a planner for that case, with a seed for the random ones and a vision range for the ones that can see
• watch an exploring robot discover the map: the fog covers whatever it hasn't touched or seen yet
• show the configuration space (red) and the graph or tree the planner explored
• generate a maze sized to the current robot, with the start and goal in opposite corners: either a perfect maze (exactly one route between any two places) or one with extra openings and several routes (a good way to see where random sampling struggles)
• replay the animation, save the canvas as a PNG, or reset the demo scene

It works with a mouse or a finger.

How it works

1. Configuration space. Growing each obstacle by the reflected robot shape (a Minkowski sum) gives the regions where the robot's centre can't go. Non-convex shapes are split into triangles, summed piece by piece and merged with a polygon union, so notches stay open and gaps too narrow for the robot close. The workspace edge becomes one more blocked region.

2. Visibility graph. A shortest path for a point among polygons bends only at convex corners of those regions. The planner connects the start, the goal and those corners wherever they can see each other.

3. A*. The graph is searched with A*, using straight-line distance as the heuristic, and visibility is only tested when an edge could shorten a route. The result is the shortest path, and the planner always finds one when one exists.

4. Random trees, for comparison. RRT grows a tree from the start by sampling random points and stepping towards them, and stops at the first path to the goal. RRT* also picks the cheapest parent for each new node and rewires its neighbours through it, so its path gets close to the shortest one as samples accumulate. Sampling planners like these are what you'd use when the configuration space can't be built exactly, for example a robot that rotates. A grid index keeps their nearest-node queries fast.

5. Exploring robots. Without the map, the robot only learns about obstacles by touching them or seeing them with a ring of range-sensor rays (with real line of sight), and decides as it goes:

   Robot knows	Planner	How it works
   where the goal is	Bug1	touch only; goes round each obstacle it meets, then leaves from the point closest to the goal
   	Bug2	touch only; follows an obstacle until it's back on the start–goal line, closer to the goal
   	TangentBug	vision; heads for the obstacle edge in view that promises the shortest route, follows walls only in dead ends
   	Replanning A*	vision; assumes unseen space is free, plans through what it has seen, replans after every step (the idea behind D* Lite)
   nothing	Wall following	touch only; right hand on the wall; solves any perfect maze, but circles forever around a wall not connected to the others
   	Trémaux	touch only; marks passages and backtracks from dead ends, like solving a maze with chalk; always finds a reachable goal
   	Frontier exploration	vision; always heads for the nearest edge of the unexplored area until the goal comes into view

   Each run reports the distance travelled against the true shortest path: the competitive ratio that sensor-based planners are judged by.

   

   Part way through the same maze: TangentBug (left) knows where the goal is; frontier exploration (right) has to find it. White is what each robot has sensed so far.

All geometric decisions use exact orientation predicates, so collinear and touching cases are handled correctly. The test suite includes property tests: A* is compared with brute-force Dijkstra, the configuration space with a direct overlap test, and RRT* has to land within 1.5% of the true shortest path.

On the demo scene (seed 1 for the random planners, measured in Chromium):

Planner	Path length	Time	Work
Visibility graph + A*	584 px (shortest)	~1 ms	25 graph nodes, 6 expanded
RRT	787 px	~11 ms	862 samples
RRT*	600 px	~115 ms	3,000 samples
Random walk (original)	885,275 px	~75 ms	55,236 random steps

Left to right: visibility graph + A*, RRT, RRT*. Grey lines are what each planner explored.

History

This started as the final project for a Computational Geometry course, by Bruno R. L. Netto and Ricardo T. Figueiredo. The original p5.js version, which used a random walk, is kept in legacy/ and still runs at /legacy/. The rewrite is described in docs/REFACTOR_PLAN.md.

Layout

Path	What
core/	muchan-core: pure Rust, tested with cargo test
core/src/geometry/	exact predicates, segments, polygons, regions, convex hull
core/src/cspace.rs	configuration space: Minkowski sums, decomposition, union
core/src/plan/	visibility graph + A*, RRT and RRT*, random walk
core/src/plan/online/	exploring robots: Bug1/2, TangentBug, replanning A*, wall following, Trémaux, frontier exploration, and their sensing
core/src/maze.rs	maze generator, with optional loops
wasm/	muchan-wasm: WebAssembly bindings
web/	Static frontend: editor, rendering and the wasm glue
legacy/	Original JS implementation

Development

Requires Rust (stable), the wasm32-unknown-unknown target and wasm-pack.

cargo test --workspace                       # run the core tests
wasm-pack build wasm --target web --out-dir ../web/pkg
python3 -m http.server -d web 8000           # open http://localhost:8000

Pushes to master are built and deployed to GitHub Pages by .github/workflows/ci.yml.