Planning strategy based on visibility graph and traveling salesman problem with time window constraints

Abstract

This paper addresses the problem of planning the motion of a mobile robot that has to visit some points of interest, each point having a specific time interval in which it can be reached. The robot is omnidirectional and it evolves with constant speed in an environment cluttered with polygonal obstacles. In the case of no obstacles, the problem would be a Travelling Salesman Problem with Time Window (TSPTW) constraints. Our solution is innovative by enabling obstacles for TSPTW scenarios, and it accomplishes this by coupling visibility graphs, graph reduction and mathematical programming. The method first constructs a visibility graph based on the obstacles and points to be visited, and then it maps this graph to another graph whose nodes correspond only to robot’s initial position and points of interest. Finally, a TSPTW problem is solved on the reduced graph by using a Mixed Integer Linear Programming (MILP) mathematical formulation, and the solution is projected to the initial environment. The solution development is accompanied by illustrative numerical simulations.