Alfred Bruckstein

GUY FOUX Foux

Michael Heymann

An algorithm for navigating a polygonal-robot, capable of translational motion in an unknown environment is described. The environment contains stationary polygonal obstacles and is bounded by polygonal walls, all of which are initially unknown to the robot. The environment is learned during the navigation process, by use of a sonar device, and new knowledge is integrated with previously acquired information. A partial map of the environment is thus obtained. The map contains parts of the obstacles that were "seen" by the robot, and the free-space between them. The obstacles in the map are transformed into a new set of enlarged polygonal obstacles. This enables treating the robot as a point instead of a polygon. The navigation problem is thus reduced to point navigation among unknown polygonal obstacles. A navigation graph is built from the transformed obstacles in the map. This graph is a partial visibility graph of the enlarged obstacles. A search is conducted on the graph for a path to the destination. The path is piecewise linear, and at its corners the robot stops, scans its environment, and updates the map, the enlarged obstacles, and the planned path. The algorithm is proved to converge to the desired destination in a finite number of steps provided a path to the destination exists. If such a path does not exist, then the navigation process terminates in a finite number of steps with the conclusion that the destination is unreachable. Application of the navigation scheme to two special cases of deteriorated polygons is also discussed: these are the case of a point robot and the case of a disk. In both cases the algorithm is shown to converge or terminate in a finite number of steps.

Two-Dimensional Robot Navigation Among Unknown Stationary Polygonal Obstacles

Michael Breuß

Petros Maragos

Stefanie Wuhrer

This book presents recent advances in the field of shape analysis. Written by experts in the fields of continuous-scale shape analysis, discrete shape analysis and sparsity, and numerical computing who hail from different communities, it provides a unique view of the topic from a broad range of perspectives. Over the last decade, it has become increasingly affordable to digitize shape information at high resolution. Yet analyzing and processing this data remains challenging because of the large amount of data involved, and because modern applications such as human-computer interaction require real-time processing. Meeting these challenges requires interdisciplinary approaches that combine concepts from a variety of research areas, including numerical computing, differential geometry, deformable shape modeling, sparse data representation, and machine learning. On the algorithmic side, many shape analysis tasks are modeled using partial differential equations, which can be solved using tools from the field of numerical computing. The fields of differential geometry and deformable shape modeling have recently begun to influence shape analysis methods. Furthermore, tools from the field of sparse representations, which aim to describe input data using a compressible representation with respect to a set of carefully selected basic elements, have the potential to significantly reduce the amount of data that needs to be processed in shape analysis tasks. The related field of machine learning offers similar potential. The goal of the Dagstuhl Seminar on New Perspectives in Shape Analysis held in February 2014 was to address these challenges with the help of the latest tools related to geometric, algorithmic and numerical concepts and to bring together researchers at the forefront of shape analysis who can work together to identify open problems and novel solutions. The book resulting from this seminar will appeal to researchers in the field of shape analysis, image and vision, from those who want to become more familiar with the field, to experts interested in learning about the latest advances.​

Alfred Bruckstein

About

Books

Join the club