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.