Summary A two part assignment based around real-world path planning for pedestrians. In the first part, students implement A* over a map that includes roads/paths as well as elevations. In the second part, students collect actual data through walking around the real world, and the cost model is then learned via regression techniques. The first part can stand alone if desired.
Topics A* search, regression (linear, non-linear, and/or non-parametric)
Audience Introduction to AI
Difficulty Moderately challenging with some time-consuming activities. Assignments were provided 2-3 weeks before due dates for each part, but students did not use all the time given.
Strengths Easy conceptualization of A* search as well as feature-based regression. Uses real-world data sets. When assigned, students voluntarily researched and implemented pedestrian path cost models. Part 2 provides a concrete example of the cost and benefit of data collection at scale. Data collection process promotes collaboration as well as getting students to go outside!
Weaknesses Most interesting in hilly areas. Some data file construction required to implement in a new location.
Dependencies Provided code (a very simple GUI and XML parser) is in Python. Could be re-implemented in any language with these capabilities.
Variants For Part 1: separate planners for drivers and/or bicyclists (who have distinct planning constraints, and also may have to leave their vehicle mid-path to reach the destination). For Part 2: More sophisticated regression techniques. Both variants are specified as the graduate course version in the materials as this was originally given in a cross-listed course.

Files included: