Adaptively Finding Optimal Routes under Principles of Spatial Cognition-A Hierarchical Reinforcement Learning Approach

Weifeng Zhao, Qin Zhang2016 · DOI

Abstract

Way finding research has paid much attention to the selection of optimal routes under principles of spatial cognition. However, the commonly employed implemental approaches suffer inevitably from the contradictions between personalized network modelling and network data sharing. This paper presents one kind of interactive route selection approach based on hierarchical reinforcement learning. In this approach, a complete network model is unnecessary, but the environmental states are automatically perceived by the agent and then mapped into the reward function defining the goal of cognitively optimal routes. The optimal routes corresponding to the policies with maximal cumulative rewards can be found through a two-stage learning process including a pre-learning stage and a real-time learning one. Our experimental results show that the proposed approach learns effectively enough for real-time route selection and ensures found routes close to global optimal ones.

Introduction

Traditional navigation systems typically rely on shortest-path algorithms like Dijkstra’s or A*. While efficient, these methods often overlook the nuances of human spatial cognition. Human "wayfinding" is a complex process where users often prefer routes that are "simplest" or "clearest" rather than strictly shortest. These preferences might include prioritizing main roads, avoiding complex intersections, or following recognizable landmarks.

The challenge in implementing such cognitive principles lies in the subjective nature of these preferences. Traditionally, this required building custom, model-driven networks for every user profile, which hinders data sharing. This paper proposes a model-independent approach, NVD-HRL, which uses hierarchical reinforcement learning (HRL) to adaptively learn cognitively optimal routes based on a personalized reward function.

Methods

The proposed NVD-HRL framework utilizes a two-stage learning process to balance computational efficiency with route quality.

Cognitive Reward Function

Instead of using physical distance as the sole cost metric, the agent navigates based on a reward function derived from five cognitive criteria: landmark significance, turning style, road grade, intersection complexity, and segment length. By assigning specific reward values to different environmental situations, the system defines what constitutes a "cognitively optimal" path.

Table of cognitive criteria and associated reward values used to define the agent's goal.

Hierarchical Architecture

To achieve real-time performance on large urban networks, the system employs a hierarchical structure:

  1. Pre-learning Stage: The network is partitioned using Network Voronoi Diagrams (NVD) centered on "bottleneck" nodes (identified via betweenness centrality). The agent learns high-level "options" or subtasks for moving between these regions.
  2. Real-Time Learning Stage: When a user requests a route, the agent uses Intra-Option Q-learning. By leveraging the pre-learned high-level options, the agent avoids exploring the entire network from scratch, significantly accelerating convergence.

Results

The approach was evaluated using a digital map of the Wuchang District in Wuhan, containing 5,639 nodes and 224 landmarks.

Convergence and Efficiency

The primary advantage of the NVD-HRL approach is its speed. In simulations involving 500 randomly selected origin-destination pairs, the hierarchical agent consistently converged to a solution in under 2 seconds.

Convergence time for the NVD-HRL approach across 500 test route sequences, demonstrating real-time capability.

In comparison, standard "flat" Q-learning (which does not use a hierarchy) often required upwards of 20 seconds for the same routes, making it impractical for interactive navigation.

Route Optimality

Despite the abstraction used in the hierarchy, the quality of the learned routes remained high. Experimental data showed that over 80% of the routes found by NVD-HRL were identical to the globally optimal routes found by the slower flat Q-learning method. Furthermore, over 95% of the routes achieved a cumulative reward within 10% of the global optimum.

Conclusion

NVD-HRL provides a robust framework for finding routes that align with human spatial cognition without the need for manual, personalized network modeling. By combining Network Voronoi Diagrams with hierarchical reinforcement learning, the system achieves the real-time performance necessary for modern navigation applications while maintaining high levels of optimality. Future work will explore integrating dynamic user behavior to further personalize the reward weights.

Summary updated

Abstract

Way finding research has paid much attention to the selection of optimal routes under principles of spatial cognition. However, the commonly employed implemental approaches suffer inevitably from the contradictions between personalized network modelling and network data sharing. This paper presents one kind of interactive route selection approach based on hierarchical reinforcement learning. In this approach, a complete network model is unnecessary, but the environmental states are automatically perceived by the agent and then mapped into the reward function defining the goal of cognitively optimal routes. The optimal routes corresponding to the policies with maximal cumulative rewards can be found through a two-stage learning process including a pre-learning stage and a real-time learning one. Our experimental results show that the proposed approach learns effectively enough for real-time route selection and ensures found routes close to global optimal ones.
BibTeX
@misc{zhao2016adaptively,
  author = {Weifeng Zhao and Qin Zhang},
  title = {{Adaptively Finding Optimal Routes under Principles of Spatial Cognition-A Hierarchical Reinforcement Learning Approach}},
  year = {2016},
  doi = {10.2991/icaita-16.2016.56},
}
Figure