cuRL: A Generic Framework for Bi-Criteria Optimum Path-Finding Based on Deep Reinforcement Learning

Traditional path-finding studies basically focus on planning the path with the shortest travel distance or the least travel time over city road networks. In recent years, with the increasing needs of diverse routing services in smart cities, the bi-criteria optimum path-finding problem (i.e., minimizing path distance and optimizing extra cost or utility according to users’ preference) has drawn wide attention. For instance, in addition to distance, the previous studies further find routes with more scenery (utility) or less crime risk (cost). However, existing works are scenario-oriented which optimize specific cost or utility, ignoring that the routing planner should be universal to deal with both cost and utility in different real-life scenarios. To fill this gap, this paper proposes a generic bi-criteria optimum path-finding framework (cuRL) based on deep reinforcement learning (DRL). Specifically, we design a novel state representation and reward function for the DRL model of cuRL to overcome the challenges that 1) the cost and utility should be optimized with minimal path distance in a unified manner; 2) the diverse distributions of cost and utility in various scenarios should be well-addressed. Then, a transition preprocessing method is proposed to enable the efficient training of DRL and avoid detours. Finally, simulations are performed to verify the effectiveness of cuRL, where two criteria (i.e., solar radiation and crime risk) are modelled based on the real-world data in downtown New York. Comparing with a set of baseline algorithms, the evaluation results demonstrate the priority of the proposed framework for its generality.

I. Introduction

Path-finding over spatial road networks is one of the most fundamental yet important planning activities in smart cities [1], [2], [3]. Usually, millions of people rely on mobile GPS navigators and online trip platforms such as Google Maps to find paths to desired destinations, where the core path-finding algorithms mainly focus on minimizing the travel distance or travel time (e.g. [4] and [5]). With the increasing needs of diverse routing services and the easy availability of multi-sourced data [6], [7], [8], [9], alternative routing strategies have attracted wide attention during recent years where specific two criteria are considered, including scenery and driving distance [10], [11], crime risk and driving distance [12], [13], [14], quietness and walking distance [15], and so on [16], [17]. This kind of bi-criteria optimum routing strategies plays a significant role in smart mobility and urban routing services. Depending on the application case, the alternative criteria (in addition to the common-used travel distance or travel time) can be regarded as either cost or utility. For instance, the crime risk in “safe” routes and the noise level in “quiet” routes are regarded as cost to be minimized while the scenery score in “beautiful” routes is regarded as utility to be maximized.