Robot navigation based on an efficient combination of an extended A* algorithm, bird's eye view and image stitching

Abstract

Robotics combines a lot of different domains with sophisticated challenges such as computer vision, motion control and search algorithms. Search algorithms can be applied to calculate movements. The A∗ algorithm is a well-known and proved search algorithm to find a path within a graph. This paper presents an extended A∗ algorithm that is optimized for robot navigation using a bird's eye view as a map that is dynamically generated by image stitching. The scenario is a robot that moves to a target in an environment containing obstacles. The robot is controlled by a Xilinx Zynq platform that contains an ARM processor and an FPGA. In order to exploit the flexibility of such an architecture, the FPGA is used to execute the most compute-intensive task of the extended A∗ algorithm. This task is responsible for sorting the accessible nodes in the graph. Several environments with different complexity levels are used to evaluate the extended A∗ algorithm. The environment is captured by a Kinect sensor located directly on the robot. In order to dewarp the robot's view, the frames are transformed to a bird's eye view. In addition, a wider viewing range is achieved by image stitching. The evaluation of the extended A∗ algorithm shows a significant improvement in terms of memory utilization. Accordingly, this algorithm is especially practicable for embedded systems since they have often only limited memory resources. Moreover, the overall execution time for several use cases is reduced up to a speed-up of 2.88x.