Continuing the discussion from Navigation: Are we missing something? Are we making things more complicated than we need to?
Discussion: What is the best and most efficient way to do robot navigation and localization within a particular, bounded, environment?
Axioms:
-
The environment is bounded. That it is not infinite, nor is it huge. (i.e. The inside of your house, limited to a single floor.)
-
The robot has enough, (or can be provided with enough), information to know, or discover, where it is based on its surroundings.
-
The robot is capable of recognizing and avoiding obstacles, either random or fixed. (i.e. The cat, which is independently mobile and whose location cannot be predicted with any accuracy at all at a particular point in time because it moves, or a piece of furniture that, (mostly), remains in the same place.)
-
The definition of “success” is:
- The ability to navigate from point “A” to point “B” with a minimum of help or collisions.
- Be able to know where it is within a certain degree of uncertainty, (ε), that is within an acceptable tolerance of error, (δ), such that it can successfully navigate.
IMHO, navigation can be divided into two broad categories: Dead-reckoning and pilotage.
-
Dead reckoning is the process of location using accurate internally derived positional measurements relative to a previous, known position to determine, (possibly independently of the local surroundings), the present position, distance to the goal, and the potential path to get to the goal. The primary dependency of dead-reckoning is the ability to accurately determine, based on internal positional measurements, where you are in a 2 or 3 dimensional bounded domain with a location accuracy, (ε), within an acceptable domain tolerance, (δ), such that you can safely navigate.
-
Pilotage is the ability to locate yourself by using externally provided navigational aids and/or landmarks, that when compared to an external reference standard, (a map, flight-plan, or navigator), allows you to determine your present position, distance to the goal, and the potential path to get to the goal. The primary dependency of pilotage is the presence of sufficient landmarks or navigation aids and a sufficiently accurate and complete external reference standard to determine where you are in a 2 or 3 dimensional bounded domain with a location accuracy, (ε), within an acceptable domain tolerance, (δ), such that you can safely navigate.
The primary difference between dead-reckoning and pilotage is that dead-reckoning depends on accurate internal reference standards whereas pilotage depends on accurate reference standards that are externally provided.
My navigation theory is based on the common model of navigation based on landmarks and a knowledge of the path to take between these landmarks.
IMHO, the primary difficulty with the “ROS”, (mapping based), navigation paradigm is that it depends on accurate mapping and precise location with respect to that, internally generated, map. Because of that, any loss of precision or external mapping noise is immediately fatal because the location accuracy rapidly becomes unacceptable.
My thesis suggests that, even with a LIDAR, the base map should be externally generated and provided as a reference standard, and the robot should navigate based on the externally generated, (and therefore precise), reference map.
For example, lets examine the way Yandex provides mapping and navigation.[1]
- Yandex has accurate and detailed access to current satellite mapping data.
- Yandex has access to a gigantic repository of previous data.
- The Yandex navigator provides a large “crowd-sourced” data source to Yandex based on inputs from users all over Russia.
- The navigator app allows users to notify of construction, accidents, new or removed speed cameras, up-to-date speed-limits, etc.
- Yandex has a fleet of “street-view” cars, (not unlike Google), that provide additional correlation and input to their maps.
As a result, Yandex maps and Yandex navigator data represents some of the most accurate mapping and navigation data in this part of the world.
Using the example of a self-driving car, the requirements to successfully self drive, (translation: navigate from here to there independently), depends on:
- Accurate knowledge of where it is.
- The ability to follow a road.
- The ability to avoid obstacles.
- The ability to follow directions provided by a navigation data source.
- The ability to ask for help when it gets confused or lost.
Note that these requirements are the same as those of a human driver navigating from point “A” to point “B”.
I believe that a robot can successfully navigate from pint “A” to point “B” given the same knowledge:
- The ability to determine where it is.
- The ability to determine where it is supposed to go.
- The ability to know where/what obstacles are around and the ability to avoid them.
- The ability to determine what direction to proceed toward the goal.
- The ability to know when it has arrived at its destination.
- The ability to stop and ask for help when lost or confused.
Note that none of this requires accurate odometery or SLAM data. All it needs is the ability to follow directions, notice landmarks, avoid obstacles, and determine when it has arrived at the destination.
IMHO, a LIDAR can be used as an “extra pair of eyes” to detect and avoid obstacles instead of hyper-accurate location mapping.
Though navigation by pilotage might not be as sexy or cool as SLAM/odometery based navigation, I believe that its basic simplicity will make it both easier to implement and easier to succeed.
Question:
What do you think is the best and most efficient path toward that goal?
- ROS and the use of ROS’s capabilities?
- Pure Python, (etc.), within the bounds of the current GoPiGo O/S?
- Something else? If so, what?
What say ye? I’d really like to hear your input on this.
==================== Footnotes ====================
- Yandex provides mapping and navigational services, (along with search engine, shopping, delivery, and God only knows what else), for the Russian Federation and countries within the CIS regions, (The Commonwealth of Independent States which are the former members of the Soviet Union that wish to be a part of it, (kind of like the European Union), though not necessarily under Russia’s thumb.)