Parallel path planning in unknown terrains

Erwin A. Prassler; Evangelos E. Milios

doi:10.1117/12.25449

1 March 1991 Parallel path planning in unknown terrains

Erwin A. Prassler, Evangelos E. Milios

Proceedings Volume 1388, Mobile Robots V; (1991) https://doi.org/10.1117/12.25449
Event: Advances in Intelligent Robotics Systems, 1990, Boston, MA, United States

Abstract

We present a parallel processing approach to path planning in unknown terrains which combines map-based and sensor-based techniques into a real-time capable navigation system. The method is based on massively parallel computations in a grid of simple processing elements denoted as cells. In the course of a relaxation process a potential distribution is created in the grid which exhibits a monotonous slope from a start cell to the cell corresponding to the robot''s goal position. A shortest path is determined by means of a gradient descent criterion which settles on the steepest descent in the potential distribution. Like high-level path planning algorithms our approach is capable of planning shortest paths through an arbitrarily cluttered large-scale terrain on the basis of its current internal map. Sequentially implemented its complexity is in the order of efficient classical path planning algorithms. Unlike these algorithms however the method is also highly responsive to new obstacles encountered in the terrain. By continuing the planning process during the robot''s locomotion information about previously unknown obstacles immediately affects further path planning without a need to interrupt the ongoing planning process. New obstacles cause distortions of the potential distribution which let the robot find proper detours. By ensuring a monotonous slope in the overall distribution we avoid local minimum effects which may trap a robot in the proximity of an obstacle configuration before it has reached its goal. 1 Until the recent past research on path planning in the presence of obstacles can be assigned to two major categories: map-based high-level planning approaches and sensor-based low-level conLrol approaches. In work such as 12 path planning is treated as a high-level planning task. Assuming that an (accnrae) precompiled map of the terrain is available high-level path planners provide paths which guarantee a collision-free locomotion through an arbitrary ensemble of known obstacles. An essential advantage of high-level path planning is the property of compleleness: path planning does not terminate until a satisfactory path is found provided there exists one. To base a navigation system which is supposed to guide a robot through an unknown terrain solely on mapbased high-level planning is not advisable for obvious reasons however. By refering to a precompiled map such a system would have severe problems to cope with situations where the real world has changed and deviates from the robot''s map. This goes back to a basic architectural principle which clearly separates the planning task from the execution of a plan and provides only a limited feed back from execution to planning. The interaction with the real world is the concern of the low-level conirol part of the system whose task is limited to the execution of elementary operations guiding the robot along the precisely specified path. The performance of the overall navigation system is bound by

Citation Download Citation

Erwin A. Prassler and Evangelos E. Milios "Parallel path planning in unknown terrains", Proc. SPIE 1388, Mobile Robots V, (1 March 1991); https://doi.org/10.1117/12.25449

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available