The ability of living creatures to navigate their environment is one of the great mysteries of life. Humans, even from an early age, can acquire data about their surroundings, determine whether objects are movable or fixed, and identify open space, separate static and non-static objects, and move towards another location with minimal effort, in infinitesimal time spans. Over extended time periods humans can recall the location of objects and duplicate navigation tasks based purely on relative positioning of landmarks. Our ability to emulate this complex process in autonomous vehicles remains incomplete, despite significant research efforts over the past half century.
Autonomous vehicles rely on a variety of electronic sensors to acquire data about their environment; the challenge is to transform that data into information supporting the objective of navigation. Historically, much of the sensor data was limited to the two dimensional (2D) instance; recent technological developments such as Laser Ranging and 3D Sonar are extending data collection to full three dimensional (3D) acquisition.
The objective of this dissertation is the development of an algorithm to support the transformation of 3D ranging data into a navigation solution within unknown environments, and in the presence of dynamically moving objects. The algorithm reflects one of the very first attempts to leverage the 3D ranging technology for the purpose of autonomous navigation, and provides a system which enables the ability to complete the following objectives:
• Separation of static and non-static elements in the environment
• Navigation based upon the range measurements of static elements
This research extends the body of knowledge in three primary topics.
1) The first is the development of a general method to identify n features in an initial data set from m features in a subsequent data set, given that both data sets are acquired via 3D ranging sensors. Accomplishing this objective, particularly with respect to 2D datasets, has long been a difficult proposition when attempting to link overlapping data sets.
2) Secondly, an innovative methodology to segment a set of discrete 3D range measurements is presented.
3) Finally, the research develops a methodology to support navigation in environments previously infeasible for autonomous vehicles due to lack of position updates. This problem is well known in the navigation field; while Global Positioning Systems (GPS) provide excellent positional information, their signals can become unavailable in a wide variety of conditions. Current research in robotic manipulation rarely addresses the concept of operations within an unknown environment, and virtually never attempts navigation in the presence of non-static objects. The ability to extend the navigation solution beyond these limitations extends the possibilities for autonomous navigation and advances the field of navigation. The current algorithm cannot provide a navigation solution for an indefinite time period; it can extend the feasible extent of navigation without benefit of GPS positioning.
While this research could not possibly claim to solve the problem of autonomous navigation, it represents an important step towards the vision of developing a machine to emulate cognitive navigation.