In this project I aim to understand how human reason about navigation and route-planning and use this understanding to build an
interactive intelligent route-planner. It is clear that human reasoning is not only about quantitative reasoning like minimizing distance function
over a graph but takes into account many subject judegements. For example : Consider a city-debutante asking another person for directions to
a caffee. Now the person can either point him directly to the nearest caffee or he might ask him about his preference (type of coffee, type of brand etc.) in case the person thinks of other options. Thus in case of ambiguities the person usually asks question and then tries to resolve the query further. Even when the destination is totally certain there are various ways to plan the route. Some people might suggest routes which have minimum turns, route which have aesthetic beauty, routes which are smaller and some combinations of these qualities. This has been thoroughly investigated in literature, to cite some references [Wiener, Mallot 09], [Bailenson et al 98], [Tversky 93]. These references try to reason human representation in graph-like models and hierarchical-models. Some strategies that are suggested are - road climbing principle, initial segment strategy, distorted representation, persistence hypothesis.
The reason why this problem is interesting is that we need systems which are capable of producing human-like navigations. Most GPS and static-maps like google map rely on minimizing metrics such as euclidean distance or some measure of distance and turns. This results in producing
routes like - Go 5m down on First Avenue, Turn 45degree and walk for 10m. It is evident that these results are insufficient on many measures for reasons already explained. Some straightforward application are in GPS technology, Campuse navigation system, tourist system etc.
In the present project I wish to create a virtual map of IIT Kanpur with important landmarks. I will be experimenting with various representation of this map (graph, hierarchical models) and various methods such as minimizing length (already done), minimizing output length (not yet found in reference), minimizing corners etc. I will demonstrate these concepts empirically by doing a case study on IIT students where I will ask them to describe the route between various landmarks in IIT Kanpur. The algorithm which best matches the empirical data will be used to built a navigation planner for the institute which can be then deployed as an application on android for the institute. If time permits another scope of work can be to train a classifier or regression model where it ranks the route based on various features and output the best route accordingly. Another interesting scope can be to extend this work to infinite route possibilities such as planning routes on a 2D field. In doing so not only we demonstrate the validity of previous concepts but also whether techniques from AI-Machine learning can give us a more refined results.
(Primary references are in bold.)
- [Wiener and Mallot 09] Wiener, J., and Mallot, H. 2003. Fine-to-coarse route planning and navigation in regionalized environments. Spatial Cognition and Computation 3(4):331–358.
- [Tversky 93] Tversky, B. (1993). Cognitive maps, cognitive collages, and spatial mental models.
In A. Frank&I. Campari (Eds.), Spatial Information Theory: A Theoretical
Basis for GIS (COSIT' 93). Vol. 716 in Lecture Notes in Computer Science (pp.
14 - 24). Berlin, Springer.
- Bailenson, J., Shum, M., & Uttal, D. (1998). Road climbing: Principles governing asymmetric route choices on maps. Journal of Environmental Psychology, 18, 251–264.
- [Reitman and Reuter 80 ] Reitmann, J., and Rueter, H. 1980. Organization revealed by recall orders and confirmed by pauses. Cognitive Psychology 12:554–581.
- [Hirtle and Jonides 85] Hirtle, S., and Jonides, J. 1985. Evidence of hierarchies in cognitive maps. Memory & Cognition 13:208–217.