Research On Intelligent Navigation Services With Spatial Cognition

Most navigation systems today realize their functions of route selection and route directions with data-driven approaches, which are always designed upon explicit quantitative models and exact mathematical computations. Although they are considered to be effective to improve economic efficiency of commercial or fleet traffic, the neglect of human cognitive principles in spatial information acquiring, processing and reasoning may lead to some limitations of navigation services in this mode.In recent years, route selection and directions on the basis of cognitive conceptual approaches have been becoming research focuses in the fields of navigation. Relevant studies shows that the integration of spatial cognition principles of human navigation activities into the development of navigation systems can make selected routes in line with the cognitive habits of human wayfinding, and make route directions close to the way of describing routes to others in direction giving. Hence, the effectiveness and acceptability of these navigation systems could be significantly enhanced, while user confidence and satisfaction being increased, user mental workload, attention distraction and navigational uncertainty being reduced. Besides, it is helpful for users to form a cognitive map of the environment in this case.Researches on cognitive navigation have three major characteristics. First, landmarks are generally employed for improving the usability of navigation systems. Second, optimal route selection criteria reflecting the principles of human spatial cognition are frequently considered in the process of route selection. Third, the organization and representation of route information close to the way of human spatial communication are usually adopted in route directions. Although related achievements are abundant, existing researches are still insufficient in the following three aspects.1. It is difficult to extract landmarks from the envrionment in a simple and efficient way, as the representative landmark extraction approaches at present, such as feature significance measuring, spatial data mining and web resources searching, usually need acquisition, processing and maintenance of massive data, such as the visual, structural and cognitive characteristics of spatial features and route descriptive textes.2. The realization of spatial cognition motivated route selection is over-reliant on specific network models. As the diversity of user cognitive preferences leads to different concerned landmarks and different weight coefficients of cognitive criteria, personalized network models need be generated to meet different users when integrating regulations of spatial cognition into weights of road network. This could bring big troubles to the sharing and maintenance of road network data between different users.3. It is hard to seamlessly integrate the a-priori environmental knowledge of users into turn-by-turn route directions. At present, the primary reference objects of turn-by-turn route directions are always the decision points on the route, while the route directions considering user’s a-priori spatial knowledge are usually referred to environmental features with global salient characteristics. As the absence of a route representation framework which could uniformly represent these two kinds of reference objects, turn-by-turn route directions and knowledge based route directions are generally implemented individually or alternately.Against to the above three issues, pertinent solutions are proposed in this thesis. Focused on the approaches of landmark extraction, route selection and route directions, this study mainly includes contents in the following five parts.1. The research background and significance of this thesis are introduced and discussed. Firstly, the necessity of development from traditional model and computation driven navigation systems into cognitive conceptual approach based intelligent navigation systems is pointed out. Then, the research progresses of cognitive navigation, including route selection algorithms, route direction approaches and route information externalization, are reviewed. After the analysis of existing problems in literature, the research objectives and research contents of this thesis are made clear.2. The theoretical foundations of the main research contents in this thesis are summarized. This is specifically shown in the processes of environmental aspectualization according to some cognitive ontologies and cognitive theories related to the human activities of spatial cognition especially navigation. The introduced spatial cognitive ontologies include cognitive conceptual primitives, qualitative spatial relations and spatial reference systems. Related spatial cognitive theories involve spatial chunking, spatial hierarchization and spatial communication.3. An approach of extracting hierarchical landmarks from points of interest (POI) in urban environments is proposed. This approach measures the significance of every POI object from three factors, which are public cognition, spatial distribution and individual characteristic. Based on a significance measure model composed of three vectors corresponding to these three factors, the processes of computing the vector values of a POI are discussed by the methods of questionnaire survey, multi-density spatial clustering and data normalization respectively. At last, the POI objects with relative high significances are treated as landmarks in different levels. Then, the weighted Voronoi diagrams generated from each level of landmarks can reflect the influence area of every landmark and associate the landmarks in the same level and between the sequential levels.4. A complete network model independent, interactive route selection approach using hierarchical reinforcement learning (HRL) is presented. In the learning process, the state transitions of the agent are constrained by the topological structure of streets, each perceived state-action pair of the environment is mapped into a immediate reward function of turning decisions at intersections. In this approach, the route selection criteria for cognitively motivated optimal routes are defined, and optimal route policies with maximal cumulative rewards can be adaptively found through a two-stage network Voronoi diagram based learning process. The first pre-learning stage automatically identifies some nodes in road network as subgoals and constructs corresponding subtasks containing local optimal route policies for achieving the subgoals. The second real-time learning stage focuses on efficiently updating the Q-values of every available state-action pair using predefined policies, and tracing the optimal routes after convergence. Furthermore, this approach can efficiently adapt to permanent or sudden environmental changes.5. A context-adaptive route direction oriented to natural language is proposed for the seamless integration of user’s a-priori spatial knowledge into turn-by-turn route directions. In this approach, a route representation framework and its main implementation procedures are proposed. In the framework, a route is represented as a sequence of uniform temporal and various granular instruction units, which could meet human cognitive habits, may reflect user’s spatial knowledge, and can be processed into route instruction phrases or sentences which are apt to be expressed in natural language. For the implementation of context-adaptive route directions, landmark extraction, various granular instruction unit generation and most appropriate instruction unit sequence selection are introduced, while some contextual factors such as environmental structures, route characteristics and prior knowledge are also considered in these procedures.