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 ( cu RL) 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.