|
A Commentary on the Relative Merits of Mapping and Odometry in Robotic Navigation
|
| |
|
My definitions of these terms:
|
| |
|
- Navigation: The process of determining where and how the robot should move to a new location.
|
| |
|
- Location: A specific point in the world or a Cartesian graph.
|
| |
|
- Mapping: The process of saving a representation of all or part of the world as a Cartesian graph.
|
| |
|
- Localization: The process of determining where you currently are within a space or Cartesian graph.
|
| |
|
- Odometry: The method of calculating where you are based on where you started and how far you have gone in a known direction.
|
| |
|
As a member of the Dallas Personal Robotics Group (DPRG)( https://www.dprg.org/), I have listened to many discussions on the relative merits of each of these processes/activities, the most recent being last nights (11/23/2021) discussion during our regular Tuesday Robot Builders Night Virtual meeting. (At some point this meeting will be on our YouTube channel (https://www.youtube.com/user/DPRGclips). This got me to thinking more on the subject and resulted in me deciding to formalize my opinions in this document.
|
| |
|
Since I am still a relative novice at robotics, my opinions should not be viewed as the final gospel on the topic, but may still present some thoughts worthy of consideration.
|
| |
|
One of my pet projects that I have slowly worked toward is my autonomous robot to rove about the house. This robot will require the ability to navigate successfully from room to room and respond to commands to navigate to a specific location. To this end, I have been considering how I would implement this behavior. I know that a lot has been written on the topic, but I like to try to tackle a problem myself to see if I can bring a fresh perspective to the subject before studying too much on how others have solved it. (Note: I usually end of reinventing the wheel, but sometimes come up with something useful. :)
|
| |
|
My opinion has been that having a map of the local world will help in navigating to specific locations. In last night’s DPRG meeting, as he has done in the past, David Anderson (who I greatly respect for his experience and accomplishments) gave his opinion that mapping is unnecessary because a combination of odometry and object avoidance seems to get the robot to the desired location with minor increased distance travelled. I can concede this as a valid point, even though it is counter to my plan. The object avoidance+odometry (OAO) method would require less memory consumed by the map and less computation for determining a best route to the destination from the current obstruction vice just how do I get around it efficiently. I would point out that a GPS will get you where you want to go, just not always by the shortest or fastest route. Who has not overruled the GPS when in known areas? It’s also easier to give a location or a region on a map a NAME rather than just an X-Y coordinate. For example:
|
| |
|
You can direct a robot to patrol the Hallway much easier than define a group of X-Y coordinates which encompass it. If a robot is working from a map in its navigation task, then dealing with an obstruction gets easier. Instead of reacting using general AI principles, the map can be used to determine the new best route from the current location.
|
| |
|
Let’s examine a potential example: Starting in the Kitchen and request the robot to deliver a beer to a person on the couch in the Living Room.
|
| |
|
| |
|
The map suggested a best route, which was obstructed twice by objects that were not part of the map but moved in the way by real world activities. The object avoidance robot might have a simple AI which tells it to go in the direction which gets it closest to its desired destination, turn in the way that is closer to the destination. This may result in initially going in the less useful direction and bumping around like a rat in a maze until the door out of the kitchen is found and then the rest relatively easy. Not seen in this example but useful to contemplate is that the object avoidance approach is superior if the map contains a large blocking object that is no longer there. It will compute a path around nothing, while the object avoidance robot may successfully pass through nothing in a more direct path.
|
| |
|
While the robot using mapping is traversing the chosen path, it will be using its object avoidance sensors to ensure the path is clear. The result of this activity is twofold; it updates the map to the current state of the area, and it uses the distance information from its sensors to validate that it is where it believes that it is located. If the robot has encoders on its motors it can also validate that the encoder driven odometry agrees with the current map location.
|
| |
|
When a robot is navigating using a map, it can collect and/or compute localization data relative to where it is in the map, rather than where it is in relationship to discovered objects. I believe that localization is basically meaningless in an object avoidance-odometry model, since the data is not utilized. If a robot always knows where it is within its world, it can respond to changing commands and/or circumstances by determining the best path to the current or new destination more efficiently.
|
| |
|
| |
|
Mapping has the following advantages:
|
| |
|
- Allows you to determine the best path to the destination based on what is known. If the map changes because an unknown object appears, then the map once again provides the information to select the best path to the destination from the obstruction.
|
| |
|
- Locations and regions within the map are easier to NAME which can be useful in other behaviors.
|
| |
|
Mapping has the following disadvantages:
|
| |
|
- The map takes memory space.
|
| |
|
- The use of the map takes programming space.
|
| |
|
- Computing the best route takes programming time both in writing the program and CPU cycles during computation.
|
| |
|
Odometry with Object Avoidance to navigate to a X-Y location has the following advantages:
|
| |
|
- Programming is simplified
|
| |
|
Odometry with Object Avoidance to navigate to a X-Y location has the following disadvantages:
|
| |
|
- The resulting route will almost certainly be longer and hence take more time to traverse.
|
| |
|
Given these relatively unimportant differences, I can see why David chose object avoidance over mapping. The gains in efficiency offered by mapping are not significant and he is not implementing other behaviors to take advantage of the Naming aspect provided by mapping. I will likely do the same in the beginning and add mapping after other desired features are implemented.
|
| |