Optimal Exploration of Terrains with Obstacles

DOI10.1007/978-3-642-13731-0_1zbMATH Open1285.68194arXiv1001.0639OpenAlexW2105687001MaRDI QIDQ3569874FDOQ3569874

Authors: Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel, Andrzej Pelc 

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: A mobile robot represented by a point moving in the plane has to explore an unknown terrain with 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 is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity O(P + D?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 + ?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 T with obstacles is c-fat if R/r ? c, where R is the radius of the smallest disc containing T and r is the radius of the largest disc contained in T .) We also prove a matching lower bound ?(P + A + ?Ak) on the complexity of exploration for limited vision, even if the terrain is known to the robot.

Full work available at URL: https://arxiv.org/abs/1001.0639

Recommendations

• Worst-case optimal exploration of terrains with obstacles
• Online exploration outside a convex obstacle
• Exploring unknown environments with obstacles
• Optimal path finding in direction, location, and time dependent environments
• On the motion of agents across terrain with obstacles
• Optimal any-angle pathfinding in practice
• Path Planning among Movable Obstacles: A Probabilistically Complete Approach
• Performance bounds for planning in unknown terrain

zbMATH Keywords

obstacleexplorationmobile robotpolygon

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Artificial intelligence for robotics (68T40)

Cited In (8)

• On the motion of agents across terrain with obstacles
• Watchman tours for polygons with holes
• Title not available (Why is that?)
• Optimal torus exploration by oblivious robots
• Constructing optimal cyclic tours for planar exploration and obstacle avoidance : A graph theory approach
• Online exploration outside a convex obstacle
• Linear Search with Terrain-Dependent Speeds
• Off-line exploration of rectangular cellular environments with a rectangular obstacle

This page was built for publication: Optimal Exploration of Terrains with Obstacles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569874)