Assignment 2: PBL — Path Planning for a Warehouse Delivery Robot

Comparative Study of A*, RRT*, and PRM

Component: Assignment 2 of 3 (7 % of 20 % Assignment component) CLO: CLO2 (C5) Released: Week 7 — 25 May 2026 Due: Week 9 — 16 June 2026, 23:59 MYTType: Individual Problem-Based Learning

Industry Challenge

Client: Automated Logistics Solutions (ALS) — Warehouse Automation Division

Context: ALS operates a $40\times 30$ m warehouse with eight workstations and a fixed layout of storage racks, charging docks, and traffic lanes. A fleet of ArbiterROS-compatible differential-drive robots shuttles parts between workstations, but the current system uses a hand-coded waypoint graph that breaks whenever the layout changes. ALS wants an automatic path planner that:

1. Computes collision-free paths between any pair of workstations.
2. Is fast enough to run online ($<200$ ms on a Raspberry Pi 4B).
3. Produces paths smooth enough for the robot’s Pure Pursuit controller to follow without excessive corner cutting.
4. Can re-plan in $<500$ ms when a forklift temporarily blocks a corridor.

Industry context: This scenario mirrors real deployments such as the Hyundai Atlas humanoid (2026), which operates autonomous warehouse navigation on a SLAM $\to$ map $\to$ path-planning stack architecturally identical to what ALS requires. The $<200$ ms replanning constraint is analogous to a production-line cycle-time requirement — not just an academic threshold.

Your mission: as ALS’s consulting robotics engineer, compare three classical planners (A*, RRT*, PRM) on the warehouse map, pick one for deployment, and extend it to handle dynamic obstacles.

Learning Objectives

• Implement or adapt A*, RRT*, and PRM path planners in MATLAB or Python
• Benchmark planners using quantitative metrics: path length, planning time, memory footprint, smoothness
• Justify an engineering decision using measured data rather than intuition
• Extend a planner to handle dynamic obstacles through replanning or local reactive behaviour
• Communicate the full engineering process in a structured technical report

Part 1 — Problem Setup (15 %)

1. Use the occupancy grid supplied with this assignment
   (Assessments/20261/starter-kits/A2/A2-warehouse-map.png, 0.05 m/cell). The eight workstation locations are in A2-map-metadata.yaml; pick five workstation pairs as your benchmark set.
2. Robot model — differential-drive, footprint radius 0.22 m, matching the MobileRobotPhysics defaults used by ArbiterROS (frontend/lib/Robot/MobileRobotPhysics.js). Inflate the map by the footprint before planning (the starter kit’s inflate() does this for you).
3. Baseline — record the straight-line distance between each pair.
4. Non-holonomic note: A* and PRM produce geometric paths that ignore the constraint $\dot{x}\sin \theta -\dot{y}\cos \theta =0$ derived in Assignment 1. Note in your report whether each planner you implement (a) produces a kinematically feasible path, (b) relies on the Pure Pursuit controller in Lab 3 to absorb the infeasibility, or (c) uses a motion primitive (RRT* with Dubins/Reeds–Shepp) that respects it.

Part 2 — Implementation (30 %)

Implement (or adapt open-source implementations, with citations) the three classical planners on the inflated map:

Your code must accept the start pose, goal pose, and map as inputs and return a path as a list of $(x,y)$ points plus a planning-time measurement. The starter kit’s Planner base class shows the exact interface.

Part 3 — Benchmarking (25 %)

Run each planner on your five start-goal pairs. Record:

Produce a comparison table and at least two plots: one bar chart of timings and one scatter of length vs. smoothness per planner.

Part 4 — Engineering Decision (20 %)

Pick one planner for ALS to deploy. Defend the choice with your measured data, referencing the four ALS requirements. Explain what you would not pick and why.

Part 5 — Dynamic-Obstacle Extension (10 %)

Extend your chosen planner to handle the “forklift blocks a corridor” scenario. Two acceptable approaches:

• Option A (global replan): detect blockage, invalidate affected cells, rerun the planner, publish the new path. Report the replan time.
• Option B (local reactive): keep the global path, run a local DWA/VFH-like avoidance on top of it. Reference Module-4/4.4-Navigation Fundamentals.pdf.

State which option you chose and why.

Deliverables

File name format: MEC781-A2-<StudentID>-<Surname>.{pdf,zip,mp4,csv}

Report sections required:

1. Executive summary ($\frac{1}{2}$ page)
2. Problem statement and map setup
3. Planner implementation notes (one subsection per planner)
4. Benchmark results (tables + plots)
5. Engineering decision and justification
6. Dynamic-obstacle extension
7. Implementation considerations (CPU, memory, sensor needs)
8. References (IEEE style)

Evaluation Criteria

Difficulty split: C3–C4 = 2 marks (29 %), C5–C6 = 5 marks (71 %) .

Resources

• Module-4/4.2-Path Planning Algorithms.pdf
• Module-4/4.3-Trajectory Control.pdf
• Module-4/4.4-Navigation Fundamentals.pdf
• Starter kit: Assessments/20261/starter-kits/A2/ (map PNG, metadata YAML, Python skeleton)
• Karaman & Frazzoli, Sampling-based Algorithms for Optimal Motion Planning, 2011
• Kavraki et al., Probabilistic Roadmaps for Path Planning, 1996

Practical Guidance

• Time management: Lab 3 is released in the same week this assignment is due (Week 9). Plan to complete the code and benchmarking by Week 8 and use Week 9 only for the report and video.
• Do not reinvent PRM / RRT* from scratch unless you have time to spare. OMPL or Python networkx + scipy.spatial work fine — cite whatever you use.
• For A*, the octile heuristic on an 8-connected grid is the right default.
• Profile your planners on the Pi 4B if you have access to one; otherwise measure on your laptop and report the hardware. The $<200$ ms target is calibrated to Pi 4B performance — include your CPU model in the report so results can be contextualised.
• Start the dynamic-obstacle extension early — it’s the piece most students underestimate.
• Video demo checklist (3-min recording must cover): (1) the map with the inflated obstacles visible, (2) one planner running on at least two start-goal pairs, (3) the dynamic-obstacle scenario with the robot replanning or reacting, and (4) a brief terminal/console view showing planning-time output. Videos that do not show all four elements cannot earn full marks.

Questions

Office hours Monday 10:00–12:00 and Wednesday 14:00–16:00, or email haniframli@uitm.edu.my.