A Novel Path Planning Algorithm for Warehouse Robots Based on a Two-Dimensional Grid Model

Abstract

In this paper, the path planning problem of goods transportation is formulated as a traveling salesman problem (TSP). A novel path planning algorithm for warehouse robots based on a two-dimensional (2D) grid model is proposed to solve this type of TSP. Firstly, we simplified the traditional pile type warehouse as a node-based 2D grid model. Then, a new concept called the largest convex polygon (LCP) is introduced to illustrate the shortest path to traverse all goods locations in an ideal condition. Next, the remaining locations are classified by their relationship with LCP and designed path planning rules separately. Finally, we merged the paths of different types of cargo locations to get the final path. The experimental results show that, compared with ant colony optimization (ACO) and genetic algorithm (GA), our proposed algorithm could effectively reduce the computation time and total path length.