Real-Time Graph Construction Algorithm for Probabilistic Predictions in Vehicular Applications

Reducing the energy consumption of vehicles is one of the greatest challenges we are facing in the mobility sector. A major step in this direction has been taken with the introduction of hybrid electric vehicles. Their performance, however, depends strongly on the energy management strategy used, which exploits the additional degree of freedom of the propulsion system and is inevitably limited by the lack of knowledge about the exact future driving conditions. Various attempts are being made to offer predictions, one of which is to exploit recorded travel data. In this paper, we propose an incremental graph construction algorithm that encapsulates this data in a digital representation of the road network and captures the actual travel routes of the vehicle along with the sequences of the specified measurement signals. The algorithm processes each location estimate separately, together with any desired simultaneously recorded measurement signal such as the vehicle speed, and constructs a directed graph in whose vertices the measurement data is stored. The real-time capability of this algorithm allows an up-to-date representation of both the road network and the signals it contains at all times. Whenever the vehicle is driving on an already visited route, we can obtain distance-resolved predictions by traversing the graph in the direction of travel and querying the stored measurement data. We present two techniques to efficiently store and predict this data, i.e., by using frequentist prediction intervals and Gaussian process regression. Our algorithm runs in real time and without any manual initialization, pre-, or post-processing. Verifications both during real operation on a trolley bus in public transportation and by simulation on a publicly available dataset demonstrate that the algorithm is real-time capable, that it consistently captures and predicts the recorded signals, and that it works in practice.