Back to Search
Start Over
Optimal Exploration of Terrains with Obstacles
- Source :
- Lecture Notes in Computer Science ISBN: 9783642137303, Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010, SWAT 2010, Jun 2010, Bergen, Norway. pp.1-12, ⟨10.1007/978-3-642-13731-0_1⟩
- Publication Year :
- 2010
- Publisher :
- Springer Berlin Heidelberg, 2010.
-
Abstract
- International audience; A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q be at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity $O(P+D\sqrt{k})$, where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity $O(P+A+\sqrt{Ak})$, where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains, if one of the parameters A or k is known, or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain ${\mathcal T}$ with obstacles is c-fat if R/r ≤ c, where R is the radius of the smallest disc containing ${\mathcal T}$ and r is the radius of the largest disc contained in ${\mathcal T}$.) We also prove a matching lower bound $\Omega(P+A+\sqrt{Ak})$ on the complexity of exploration for limited vision, even if the terrain is known to the robot.
- Subjects :
- FOS: Computer and information sciences
Convex hull
0209 industrial biotechnology
Matching (graph theory)
Computer science
Terrain
0102 computer and information sciences
02 engineering and technology
Computer Science::Computational Geometry
exploration
mobile robot
01 natural sciences
Computer Science::Robotics
020901 industrial engineering & automation
Computer Science - Data Structures and Algorithms
Data Structures and Algorithms (cs.DS)
Point (geometry)
obstacle
Discrete mathematics
Mobile robot
polygon
Computer Science::Graphics
010201 computation theory & mathematics
Polygon
Trajectory
Robot
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Subjects
Details
- ISBN :
- 978-3-642-13730-3
- ISBNs :
- 9783642137303
- Database :
- OpenAIRE
- Journal :
- Lecture Notes in Computer Science ISBN: 9783642137303, Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010, SWAT 2010, Jun 2010, Bergen, Norway. pp.1-12, ⟨10.1007/978-3-642-13731-0_1⟩
- Accession number :
- edsair.doi.dedup.....94f1949099ab95b62d0dc220cab5366d