Triangulation-based path planning for patrolling by a mobile robot

Abstract

This paper addresses a systematic coverage planning with a circular sensor mobile robot, having kinematic and dynamic constraints. The static or dynamic objects in the area of interest are also assumed to be circular. Our approach, unlike existing approaches published in literature, allows local and global coverage optimization analytically, in terms of minimal distance-path or energy consumptions [1-9]. Our approach follows six steps. First, given an arbitrary number of statically circular objects in an area of interest, apply the Delaunay Triangulation Method. Second, find the minimum number of visible polygon in each triangle, face, or triangulated-face found in Step One. Third, apply the Novel Circular Waypoint Coverage Placement Algorithm (CWCP) to find the minimum number of waypoints in each face. Fourth, generate a tour by applying the nearest neighbor Traveling Salesman's algorithm (TSP) to link the waypoints found in Step 3. Fifth, apply cublic Spline interpolation to make the tour continuous and differentiable. Sixth, apply the Trajectory Planning Technique to steer the mobile robot from a given arbitrary position and orientation to the desired position and orientation, the waypoints found in Step Three.