Multi-goal Path Planning Autonomous System for Picking up and Delivery Tasks in Mobile Robotics

摘要

Intelligent service robots are needed in office-like environments to perform common tasks of picking up, and delivering things such as mail, goods, trash recycled paper, etc. These tasks are challenging since robots must avoid static and dynamic obstacles, and mainly robots have to perform path planning considering multiple goals as saving energy. This work proposes an autonomous multi-goal path planning system for picking up or delivering tasks in mobile robotics. The multi-goal path planning method is based on the Lin-Kernighan Heuristics (LKH) algorithm [1], which was modified in order to implement an autonomous system for picking up/delivering tasks using non-Euclidean distances, Hamiltonian paths, and a Pioneer 3DX mobile robot. This work proposes a client - robot system ARMM [2] where many clients request pickup / delivery services, then the robot continuously plan a Hamiltonian path to visit each one of the requested pickup / delivery goals, and return to its base station. To validate the results of this work two well-known metrics were performed [3]: distance traveled and time elapsed. A comparison between the nearest goal, random selection, the LKH with Euclidean distances, and the LKH with non-Euclidean distances algorithms were performed.