IEEE Transactions on Systems Man and Cybernetics Systems · 2017 · 29 citations · 22 references
ComputingComputer ScienceRobotics EngineeringMobile RoboticsPath PlanningRoboticsCollision DetectionObstacle AvoidanceRobot Motion PlanningTrajectory GenerationCoverage Path PlanningCoverage PlanningGraham ScanInput-output TransformationOutput TransformationRobot Path PlanningRobotic Path PlanningTrajectory Planning
In this paper, we proposed a coverage path (CP) planning approach for a mobile robot moving in a dynamically changing environment. Our family of algorithms begins by finding the first path around the center of interior obstacles/disks of a given target region (TR) through the Graham scan algorithm. The first path is then used as a foundational path to generate a collision free, first order differentiable, and observable CP through a complete set of input and output transformation algorithms which together form the rainbow CP planning approach. The last algorithm of the rainbow CP planning approach finds a sufficient number of observation points on the CP needed to observe the TR. The novelty of our rainbow CP planning approach is that it partitions the TR into different shapes with different properties needed to obtain complete coverage while achieving first order path differentiability. The main technical contributions of the proposed approach is to provide a holistic solution that segments any TR, uses triangulation to determine the line of sights and observation points, and computes the collision-free CP within a quadratic runtime. The proposed method can be readily generalized to address problems of higher dimensions, and it is scalable with respect to the size of TR and the number of robots. Computer simulations are used to illustrate the effectiveness and correctness of the proposed approach.
22
Computational geometry algorithms library
Pierre Alliez, Andreas Fabri, Efi Fogel · 2008 · 389 citations
Finding minimal enclosing boxes
Joseph O’Rourke · International Journal of Parallel Programming · 1985 · 235 citations