A Framework for Energy-Efficient Trajectory Optimization in Patrolling Problem with Non-pre-defined Starting Depot

Abstract

The subject of this paper is to perform energy-efficient trajectory optimization in patrolling problem. Given a certain area in the environment to be monitored, a number of viewpoints are assigned in such a way that if there exists a robot at each viewpoint position to monitor, the union of all these robots sensing footprints covers the whole area to be monitored. Usually the number of robots used is much less than the number of assigned viewpoints which motivates the patrolling problem. In the patrolling problem, all the assigned viewpoints should be visited in a certain sequence to optimize either the overall time or the total traveled distance. Here the overall distance optimization case is considered. Such problem leads to a variant of Traveling Salesmen Problem which is the Single Depot multiple Traveling Salesmen Problem (mTSP). In the literature, several works tackled this problem but always assuming a pre-defined starting depot. The new approach is to obtain the optimum trajectory by minimizing the total traveled distance without pre-defining a certain starting depot. A new algorithm formulation of the problem is introduced. It is assumed that the robot dynamics used are for the two-wheeled mobile robots which enables turning on the spot, so they can move on sharp-edged straight lines, and also they are with no physical constraints. A comparison between the commonly-used pre-defined starting depot method and the new non-pre-defined starting depot method is performed and the efficacy of the new method is presented through simulations.