Adaptive path finding for moving objects

Abstract

Finding the fastest route in dynamic transportation networks aids navigation service considerably. Existing approaches are either too complex or incapable or handling complex circumstances wherein both the location or a mobile user and the traffic conditions change incessantly over time. In this paper, we propose an incremental search approach based on a variation of A*-Lifelong Planning A* (LPA*) to derive a dynamic fastest path, which continually adapts to the real-time traffic condition while making use of the previous search result. Our experimental results reveal that the proposed approach is a significant improvement over a conventional approach also using the A* algorithm. © Springer-Verlag Berlin Heidelberg 2005.