WLAA*: A Time-efficient Method for Path Planning in Warehouse Environments
Maoqing Shi, Pengfei Phil Duan, Tao Yu, Shengwu Xiong · 2021 IEEE International Conference on Robotics and Biomimetics (ROBIO) · 2021
The path planning problem is to find a feasible path between two given locations. Search-based methods, like A* and its variants, have shown effectiveness for solving such problems in some specific environments, for example, in automated warehouses. However, their search time always increases exponentially with the growing number of extra visited nodes, which is inconsistent with the requirements of warehouse applications. To address this issue, we first analyze the generation of extra visited nodes. On this basis, we then propose warehouse-layout-aware A* (WLAA*) that can lessen such generation according to the layout of a warehouse. We also present an algorithm that identifies the layout automatically. Finally, we perform simulation experiments on different instances. Experimental results show that WLAA* is able to effectively reduce the number of extra visited nodes thus speeding up the search.