Project

Statement of Problem

NUMACK is an Embodied Conversational Agent that interacts with humans by answering questions and giving directions around the Northwestern University campus. He uses speech recognition and head-tracking to understand a question, determines the answer, and uses speech and gesture in his response. One aspect of the NUMACK project is content planning. Content planning is this: Once NUMACK understands the question asked of him, i.e. “how do I get from A to B”, he needs to come up with the appropriate route from A to B.

Previous Research

Route planners such as Mapquest, Microsoft AutoRoute Great Britain, and Microsoft Streets and Trips automatically generate a map showing the route from A to B. However, these route maps are often more difficult to use then hand drawn maps because they do not distinguish between essential and extraneous information, and therefore lack clarity. We know that while a description of a route is sufficient when it only includes road names and turn directions, usability increases with extra information, for example, local landmarks along the route (Agrawala and Stolte, Rendering Effective Route Maps: Improving Usability Through Generalization). But to the best of my knowledge, no one has created a program which generates the route from A to B and includes key landmark objects to indicate how far one is or where to turn.

My Approach

I plan to set up a database using prolog that includes some possible A’s and B’s (places that routes can start and end from), and that also includes other key landmarks on campus (for instance, no one’s going to ask how to get to or from ‘the big tree’, but perhaps a route should still include ‘the big tree’ as a landmark). Then I’ll define a set of rules, including one that is a route finder using the A* algorithm, which will return an appropriate route including landmarks, from A to B.

On the first iteration of the project, Chelsea and I will go through the videotaped data of subjects giving directions for a few specific routes at Northwestern University. Landmarks that the subjects widely use will be noted as key landmarks for those routes. Those specific routes and landmarks will be added to the database. When that is set up, I’ll code the route so that when A and B are put into the program, the route and landmarks that are returned match with the routes and landmarks described by the subject data. This iteration is useful in terms of programming because it will figure out the way the information will look and be passed into and out of the program.

After studying the videotapes, we will try to determine a theory about picking routes and key landmarks based on the empirical data supplied by the videotaped subjects. Do subjects describe how to get from A to B using the shortest route, the popular route, or the most accessible route, etc. What kinds of patterns are seen in the key landmarks picked, etc. The second iteration of coding relies on our having theories about routes and landmarks.

On the second iteration of the project, more A’s and B’s will be added to the database, as will appropriate key landmarks--picked according to the patterns we found in the subjects. After that, I need to create an algorithm that chooses the ‘best’ of the possible routes. What we determine by our theory—possibly most accessible, shortest, or most popular path, will be given lower path weights, and I’ll implement the A* algorithm in that context.

Once the route exists, the program should pick useful key landmarks at each of the turns on the route. Perhaps the program should also pick key landmarks to mark nearing the end of a long straight path on the route. These landmarks will be returned with the route to help describe the route.

The End Goal

The product will be program written in prolog that takes two arguments, points A and B, and returns a set of points and directions describing how to get from A to B, which includes landmark indications marking where to turn and progress on a straight path.