Walking around Dubrovnik

This pair of assignments was developed for a cross-listed (undergrad + MS-level) Intro to AI taught as part of a semester-long study abroad in Dubrovnik, Croatia. The city is built on a large hill (and some smaller ones), such that many so-called "streets" are in fact stairs. As such, the time it takes to walk a path in one direction may be significantly different than in the other direction. This inspired the development of an A* assignment for pedestrians. In particular, developing a cost function and appropriate (admissible) heuristic given that cost function require a bit of care.

Lab 1:When assigned, students were given about three weeks for the first assignment. The goal of this assignment is to write an A* path planner that uses appropriate cost function and heuristics for pedestrians in an urban, hilly environment. Students are given a little starter code (and could easily be given more to be able to spend time focusing on the AI aspects, though my students enjoyed the diversion of playing with the GUI).

Lab 2 prep:To prepare for lab 2, students were given the assignment to start collecting data (that is, going for walks and timing themselves). They had several weeks to do this. Credit was given as part of lab 2 for collecting sufficient quantities of unique data.

Lab 2: For the second assignment, students were again given about three weeks from the time the material was covered in class. In this assignment, students use the data collected by walking around to modify the planner's cost functions, using different types of regression.

Localization:To localize this assignment to another setting, you will need to generate two data files: an OpenStreetMap XML of the routes, and an elevation map.

• For the routes, go to openstreetmap.org and search for the location you are interested in. Click on the "Export" button and you will get an XML file that can be used. The provided starter code will extract the "ways" (streets as well as pedestrian routes). Since Dubrovnik is on the coast, I chose to also extract the coast nodes solely for graphics purposes.

• For the elevation, you have a couple of options.

  • The HGT file (elevations as simple binary integer data) provided here is from the SRTM data set. This could be obtained from earthexplorer.usgs.gov and is available for most of the world. Look under the Data Sets tab for Digital Elevation -> SRTM -> SRTM Void Filled. Currently this appears to have the same data only in other formats - if you download the BIL format and unzip it, there will be a .bil which contains the same form of data but in little-endian format!
  • Alternately, the National Elevation Data set contains higher-resolution data over the US (~10 m per pixel instead of ~30 m). This can be downloaded from this viewer by checking Elevation Products -> 1/3 arc-second DEM. This data is in a variety of proprietary formats but can read with the open-source gdal utility (or simply converted to a format of your choice for student consumption with the gdal_translate utility within). If you use this, you will have to change the EPIX constant in the solution file to reflect the higher resolution (this constant is the number of pixels per degree of latitude/longitude).

The student data used as the data set for part 2 was collected via a web form with trivial PHP inside - if you choose to collect data this way you will need to be able to put it on a web server with appropriate permissions. Otherwise, any survey tool should be able to serve the same purpose easily enough (the provided form does no input validation in any case).