Robot navigation in unknown terrains of convex polygonal obstacles using learned visibility graphs
12
Citation
8
Reference
20
Related Paper
Abstract:
The problem of navigating an autonomous mobile robot through an unexplored terrain of obstacles is the focus of this paper. The case when the obstacles are 'known' has been extensively studied in literature. The process of robot navigation in completely unexplored terrains involves both learning the information about the obstacle terrain and path planning. We present an algorithm to navigate a point robot in an unexplored terrain that is arbitrarily populated with disjoint convex polygonal obstacles in the plane. The navigation process is constituted by a number of traversals; each traversal is from an arbitrary source point to an arbitrary destination point. Initially, the terrain is explored using a sensor and the paths of traversal made may be sub-optimal. The visibility graph that models the obstacle terrain is incrementally constructed by integrating the information about the paths traversed so far. At any stage of learning, the partially learnt terrain model is represented as a learned visibility graph, and it is updated after each traversal. The proposed algorithm is proven to yield a convergent solution to each path of traversal. It is also shown that the learned visibility graph converges to the visibility graph with probability one, when the source and destination points are chosen randomly. Ultimately, the availability of the complete visibility graph enables the robot to plan globally optimal paths, and also obviates the further usage of sensors.Keywords:
Visibility graph
Graph traversal
Visibility
Cite
<p align="left">Path planning is an essential task for the navigation of Autonomous Mobile Robot. This is one of the basic problems in robotics. Path planning algorithms are classified as global or local, depending on the knowledge of surrounding environment. In local path planning, the environment is unknown to the robot, and sensors are used to detect the obstacles and to avoid collision. Bug algorithms are one of the frequently used path planning algorithms where a mobile robot moves to the target by detecting the nearest obstacle and avoiding it with limited information about the environment. This proposed Critical-PointBug algorithm, is a new Bug algorithm for path planning of mobile robots. This algorithm tries to minimize traversal of obstacle border by searching few important points on the boundary of obstacle area as a rotation point to goal and end with a complete path from source to goal.</p>
Any-angle path planning
Mobile Robot Navigation
Graph traversal
Start point
Cite
Citations (12)
SUMMARY Finding optimal paths for robot navigation in a known terrain has been studied for some time but, in many important situations, a robot would be required to navigate in completely new or partially explored terrain. We propose a method of robot navigation which requires no pre-learned model, makes maximal use of available information, records and synthesizes information from multiple journeys, and contains concepts of learning that allow for continuous transition from local to global path optimality. The model of the terrain consists of a spatial graph and a Voronoi diagram. Using acquired sensor data, polygonal boundaries containing perceived obstacles shrink to approximate the actual obstacles surfaces, free space for transit is correspondingly enlarged, and additional nodes and edges are recorded based on path intersections and stop points. Navigation planning is gradually accelerated with experience since improved global map information minimizes the need for further sensor data acquisition. Our method currently assumes obstacle locations are unchanging, navigation can be successfully conducted using two-dimensional projections, and sensor information is precise.
Mobile Robot Navigation
Cite
Citations (80)
Obstacle avoidance
Foundation (evidence)
Cite
Citations (0)
The authors consider the problem of terrain model acquisition by a roving point placed in an unknown terrain populated by stationary polyhedral obstacles in two/three dimensions. The motivation for this problem is that after the terrain model is completely acquired, navigation from a source point to a destination point can be achieved along the collision-free paths. This can be done without the usage of sensors by applying the existing techniques for the find-path problem. In the paper, the point robot autonomous machine (PRAM) is used as a simplified abstract model for real-life roving robots. An algorithm is presented that enables PRAM to autonomously acquire the model of an unexplored obstacle terrain composed of an unknown number of polyhedral obstacles in two/three dimensions. In this method, PRAM undertakes a systematic exploration of the obstacle terrain with its sensor that detects all the edges and vertices visible from the present location, and builds the complete obstacle terrain model.< >
Obstacle avoidance
Cite
Citations (53)
This paper addresses a navigation problem for a certain type of simple mobile robot modeled as a point moving in the plane. The only requirement on the robot is that it must be able to translate in a desired direction, with bounded angular error (measured in a global reference frame), until it reaches the nearest obstacle in its motion direction. One straightforward realization of this capability might use a noisy compass and a contact sensor. We present a planning algorithm that enables such a robot to navigate reliably through its environment. The algorithm constructs a directed graph in which each node is labeled with a subset of the environment boundary. Each edge of the graph is labeled with a sequence of actions that can move the robot from any location in one such set to some location in the other set. We use a variety of local planners to generate the edges, including a “corner-finding” technique that allows the robot to travel to and localize itself at a convex vertex of the environment boundary. The algorithm forms complete plans by searching the resulting graph. We have implemented this algorithm and present results from both simulation and a proof-of-concept physical realization.
Mobile Robot Navigation
Compass
Cite
Citations (17)
We present exploration and mapping strategies for a mobile robot moving among a finite collection of convex obstacles in the plane. The obstacles are unknown to the robot, which does not have access to coordinates and cannot measure distances or angles. The robot has a unique sensor, called the gap sensor, that tracks the direction of the depth discontinuities in the robot's visibility region. Furthermore, the robot can only move towards depth discontinuities. As the robot moves, the depth discontinuities split and merge, and these changes are encoded in a Gap Navigation Tree. We present a strategy for this robot that is guaranteed to explore the whole environment, but that cannot decide whether the exploration has been completed. If in addition it is assumed that the robot has access to a pebble, which is an identifiable point that the robot can manipulate, then we prove that the robot can decide (in polynomial time in the number of obstacles) whether the environment has been completely explored. For this, the robot is able to distinguish every obstacle using only the gap sensor and a single pebble. These results are a continuation of our previous work on gap sensing for multiply connected environments, in which we reduce the sensing requirements for the robot by constraining the shape of the obstacles.
Classification of discontinuities
Mobile Robot Navigation
Merge (version control)
Cite
Citations (3)
Cite
Citations (8)
In the implementation of an autonomous mobile robot, the navigation system must be able find an acceptable path through a region of multi-valued traversal costs (as opposed to a binary regime of obstacle avoidance). Information must be efficiently represented, with sufficient information density in the robot's immediate navigation domain, in a manner which facilitates a process of learning the terrain. This paper discusses a decision system built around a "Routing-Engine" employing a cellular-array processor to propagate a wave over an two-dimensional map in which the pointwise traversal costs are represented as pointwise refractive indices. The path returned is the locus of local normals to the wavefront of the first wave, originating at the robot's current location, to reach the goal. This routing-engine is run recursively on a hierarchical stack of maps arranged in linear-spatial registration with the coarsest information resolution in the most global map. The central fovea of each map in the hierarchy is "blown-up" to yield a map more local to the vehicle, with the lowest level map possessing sufficient resolution to maneuver the robot. As the robot moves, its registration in the centre of each map in the stack is maintained by "scrolling" the maps over each other. As this is done, sensed information is propagated through the stack updating the information stored at each level. The system has been implemented successfully in simulation.
Odometry
Mobile Robot Navigation
Cite
Citations (9)
Visibility graph
Visibility
Porting
Rectangle
Graph traversal
Cite
Citations (18)
The research literature has addressed extensively the motion planning problem for one or more robots mobbing through a field of obstacles to a goal. Most of this work assumes that the environment is completely known before the robot begins its traverse. The optimal algorithms in this literature research a state space (e.g., visibility graph, grid cells) using the distance transform or heuristics to find the lowest cost path from the robot's start state to the goal state. Cost can be defined to be distance traveled, energy expended, time exposed o danger, etc. This paper presents the D* algorithm for generating optimal paths for a robot operating with a sensor and a map of the environment. The robot's sensor is able to measure arc costs in the vicinity of the robot, and the known and estimated arc values comprise the map. Thus, the algorithm can be used for any planning presentation, including visibility graphs and grid cell structures. The paper describes the algorithm, illustrates its operation, presents our approach for implementation, and then concludes with a proof of operation.
Visibility
Traverse
Heuristics
Visibility graph
Grid reference
Cite
Citations (0)