Shared Search Tree-Based Multi-Objective Dynamic Path Planning: An Enhanced D* Lite Approach

Abstract

In order to solve the problem of computational redundancy in multi-objective dynamic path planning with D Lite algorithm, this paper proposes an improved version of D Lite algorithm based on Shared Search Tree, called SST-D Lite. In terms of methods, this new algorithm builds a search tree with a structure of “shared trunk+independent branches”, which enables multiple targets to reuse the extended information of common nodes and reduce repeated calculation from the architectural level. We also set up a static target point lookup table based on hash mapping to reduce the complexity of target authentication to O (1). In addition, a lazy deletion mechanism is designed to maintain the node state in the priority queue and reduce the time complexity from O(N) to O (1). The algorithm also adds a weighted cost mechanism to balance the path length and security risks, and uses Breadth-First Search (BFS) to make a local reset strategy, which can accurately repair the affected areas when encountering dynamic obstacles. The simulation results show that in a complex 200×200 dynamic environment, although SST-D Lite needs a longer initialization time (1256.11 milliseconds), it shows obvious advantages in core dynamic performance indicators. Specifically, the average re-planning time of SST-D Lite is only 11.45 milliseconds, which is about 26% faster than the original D Lite and 67% shorter than the A algorithm. In terms of search efficiency, the total number of nodes expanded by SST-D Lite (3.40× 10) is about 70% of that of D Lite and only 14.7% of that of A. Experiments show that SST-D Lite can effectively filter out redundant search space while maintaining high real-time response capability and engineering practical value, and is suitable for multi-objective planning in dynamic environment.