Open Access Open Access  Restricted Access Subscription Access

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

Walaaeldin Ghadiry, Youmin Zhang


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.

Full Text:



Fabio Pasqualetti, Antonio Franchi and Francesco Bullo, “On cooperative

patrolling: optimal trajectories, complexity analysis, and approximation algorithms,” IEEE Trans. Robot., vol. 28, no. 3, pp. 592-606, 2012.

Fierro, J. Clark and R., “Mobile robotic sensors for perimeter detection and tracking,” ISA Trans., vol. 46, no. 1, pp. 313, 2007.

D. B. Kingston, R. W. Beard, and R. S. Holt, “Decentralized perimeter surveillance using a team of UAVs,” IEEE Trans. Robot., vol. 24, no. 6, pp. 1394-1404, 2008.

S. Susca, S. Martnez, and F.Bullo, “Monitoring environmental boundaries with a robotic sensor network,” IEEE Trans. Control Syst. Technol., vol. 16, no. 2, pp. 288-296, 2008.

Y. Elmaliach, A. Shiloni, and G. A. Kaminka, “A realistic model of frequency-based multi-robot polyline patrolling,” Auton. Agents, Estoril, Portugal, 2008.

Bektas, Tolga, “The multiple traveling salesman problem: an overview of formulations and solution procedures,” The International Journal of Management Science, pp. 209-219, 2006.

Svestka JA, Huckfeldt VE, “Computational experience with an msalesman traveling salesman algorithm,” Management Science, pp. 790-

, 1973.

Angel RD, Caudle WL, Noonan R, Whinston A, “Computer assisted school bus scheduling,” Management Science, pp. 279-288, 1972.

B. Brummit, A. Stentz,“Dynamic mission planning for multiple mobile robots,”IEEE International Conference on Robotics and Automation, 1996.

Brummit B, Stentz A., “GRAMMPS: a generalized mission planner for multiple mobile robots,” IEEE international conference on robotics and automation, 1998.

Yu Z, Jinhai L, Guochang G, Rubo Z, Haiyan Y, “An implementation of evolutionary computation for path planning of cooperative mobile robots,” The forth world congress on intelligent control and automation, 2002.

J.L. Ryan, T.G. Bailey, J.T. Moore, W.B. Carlton,“Reactive tabu search in unmanned aerial reconnaissance simulations,” The 1998 winter simulation conference, 1998.

Fabio Pasqualetti, Joseph W. Durham, and Francesco Bullo, “Cooperative patrolling via weighted tours: performance analysis and distributed algorithms,” IEEE Trans. On Robotics, vol. 16, pp. 1181-1188 , 2012.

David Portugal, Rui P. Rocha, “Distributed multi-robot patrol: a scalable and fault-tolerant framework,” Robotics and Autonomous Systems, vol. 61, pp. 1572-1587 , 2013.

Imdat Kara, Tolga Bektas, “Integer linear programming formulations of multiple salesman problems and its variations,” European Journal of

Operational Research, pp. 1449-1458, 2006.

MOSEK 7.0 Optimization Software, 2009.



  • There are currently no refbacks.