This assignment allows students to gain experience with defining AI search problems and implementing uninformed and informed search algorithms. Students define the search problems for navigating a subway system, requiring them to define the goal test, cost function, and successor function. Students then implement breadth-first search, depth-first search, and A* search. Finally, the assignment requires students to implement a problem in a completely different domain (the 8-puzzle) in order to demonstrate that the search algorithms will work so long as the problem is correctly defined. Students are given data files for the Boston “T” and London “Tube” systems, including functions to parse these data files and build appropriate data structures. This allows students to focus on the search aspects of the problem, rather than implementing the required graph data structures from the raw data.
This assignment was developed for an upper-level AI class where search is the first major topic covered. We announce the assignment as we shift from uninformed search to informed search, allowing two to three weeks to complete the assignment. The assignment contains starter code for both Python and Java. We include both because most of our students have experience in both languages and we want to encourage them to use their preferred language. Adopters could offer support in only one of the two languages without impacting the merits or content of the
assignment.
As noted above, faculty adopting this assignment may want to change the subway systems used to be more relevant to their students. The Boston subway system was chosen because it is one that our students are somewhat likely to have used themselves. It is also good for debugging, since the hub-and-spoke nature of the system means that there are few paths between any given pair of stations. In contrast, the London system is more complex and has many paths available. Faculty considering replacing either network should consider the new network’s complexity when deciding which network to remove. Adopters should also note that building the data sets for both systems required compiling data from multiple sources; the same would likely be true for any other desired transit network. The readme file in the data folder cites the sources for both datasets.
This assignment uses Meaningful and Relevant Content. Navigating an unfamiliar transportation system, or more broadly, an unfamiliar city, is a real problem. Students have personal experience using navigation software (e.g. Google Maps). While they likely have used it more for driving directions, faculty can point out that Google provides public transit directions for most major cities, Boston and London included. Navigating a known network is a classic AI problem, and applying uninformed and informed search algorithms to the challenge of navigating a subway system is an example that is readily clear and meaningful to students.
To make this assignment more meaningful to their own students, faculty may want to adopt other transportation networks besides Boston and London. Changing at least one of the subway systems to one that is closer to your school would add meaning to the content. For schools located some distance from a subway system, a small bus system (even an on-campus bus system) would be a reasonable substitute for the Boston network