Patrolling Strategy Using Heterogeneous Multi Agents in Urban Environments Using Visibility Clustering

Oren Gal, Yerach Doytsher

Abstract


In this paper, we study the Visible Trajectories Planning for Patrolling application using heterogeneous multi agents in 3D urban environments. Our concept is based on a spatial clustering method using visibility analysis of the 3D visibility problem from viewpoints in 3D urban environments, defined as locations. We consider two kinds of agents, with different kinematic and perception capabilities. Using a simplified version of Traveling Salesman Problem (TSP), we formulate the problem as one of patrolling strategy, with upper boundary optimal performances. We present a combination of relative deadline UniPartition approaches based on visibility clusters. These key features allow new planning for an optimal patrolling strategy for heterogeneous agents in urban environments. We demonstrate our patrolling strategy method in simulations using Autonomous Navigation and Virtual Environment Laboratory (ANVEL) test bed environment.

Keywords


Autonomous Navigation; Spatial Clustering; ANVEL;

Full Text:

PDF

References


N. Agmon, D. Urieli and P. Stone. Multiagent Patrol Generalized to Complex Environmental Conditions. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco, California, 2011.

N. Basilico, N. Gatti, and F. Amigoni. Developing a deterministic patrolling strategy for security agents. In proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology- Vol. 2, pages 565-573. IEEE computer Society, 2009.

Y. Chevaleyre. 2004. Theoretical analysis of the multi-agent patrolling problem. In Proc. of IAT’04.

R. Wendolsky, S. Scheuerer. A Cluster Based Scatter Search Heuristic for the Vehicle Routing Problem. University of Regensburg Discussion Papers in Economics No. 415, November 2006.

Siegwart, R. and Nourbakhsh, I.R., Introduction to Autonomous Mobile Robots, The MIT Press, 2004.

Choset, H., and others, Principles of Robot Motion; Theory, Algorithms, and Implementation, The MIT Press, 2005.

Ross, I.M., Lecture Notes in Control and Optimization, Naval Postgraduate School, Monterey, CA, 2007.

Lewis, L.R., Rapid Motion Planning and Autonomous Obstacle Avoidance for Unmanned Vehicles, Master's Thesis, Naval Postgraduate School, Monterey, CA, December 2006

H. Plantinga, and R. Dyer, Visibility, Occlusion, and Aspect Graph, The International Journal of Computer Vision, 5,137-160, (1990)

Y. Doytsher, and B. Shmutter, Digital Elevation Model of Dead Ground, Symposium on Mapping and Geographic Information Systems (Commission IV of the International Society for Photogrammetry and Remote Sensing), Athens, Georgia, USA, (1994)

F. Durand, 3D Visibility: Analytical Study and Applications, PhD thesis, Universite Joseph Fourier, Grenoble, France, 1999

W.R. Franklin, Siting Observers on Terrain, in Proc. of 10th International Symposium on Spatial Data Handling. Springer-Verlag, pp. 109–120, (2002)

J. Wang, G.J. Robinson, and K. White, A Fast Solution to Local Viewshed Computation Using Grid-based Digital Elevation Models, Photogrammetric Engineering & Remote Sensing, 62, 1157-1164, (1996)

J. Wang, G.J. Robinson, and K. White, Generating Viewsheds without Using Sightlines, Photogrammetric Engineering & Remote Sensing, 66, 87-90, (2000)

C. Ratti, The Lineage of Line: Space Syntax Parameters from the Analysis of Urban DEMs', Environment and Planning B: Planning and Design, 32,547-566, (2005)

L. De Floriani, and P. Magillo, Visibility Algorithms on Triangulated Terrain Models, International Journal of Geographic Information Systems, 8, 13-41, (1994)

B. Nadler, G. Fibich, S. Lev-Yehudi, and D. Cohen-Or, A Qualitative and Quantitative Visibility Analysis in Urban Scenes, Computers & Graphics, 5, 655-666, (1999)

S.M. LaValle, Planning Algorithms. Cambridge,U.K.:Cambridge Univ. Pr., (2006)

A. Gordon, Classification (2nd ed.), London: Chapman and Hall/CRC Press, 1999.

T. Schelhorn, D. Sullivan, M. Haklay, "STREETS: An agent-based pedestrian model," http://www.casa.ucl.ac.uk/streets.pdf. , 1999, [accessed February 2014].

ANVEL: http://anvelsim.com/

O.Gal, Y. Doytsher. "Spatial Visibility Clustering Analysis in Urban Environments Based on Pedestrians' Mobility Datasets", Int. Conf. of GeoProcessing 2014, pp. 38-44, Spain.




DOI: http://dx.doi.org/10.5281%2F13913173

Refbacks

  • There are currently no refbacks.


Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.