Putting Things Away

Imagine that you have to get to Grandma’s house, which, according to legend, is over the hills and through the woods, and two states away. That would be two countries away if you live in Europe. To plan your trip, you can start in one of two ways. Ignoring the fact that Google has taken away most map reading and navigation skills from today’s youth, you would get out a map and do one of the following:

• Start at your house and try to find the roads that are closest to a straight line to Grandma’s house
• Start at Grandma’s house and try to find roads leading to your home

From either direction, you will find that the road or path you seek forks, intersects, changes, meanders, and may even come to a dead end. Also, all roads are not created equally – some are bigger, with higher speed limits, and some are smaller, with more stop signs. In the end, you pick your route by the combination of decisions that results in...

Technical requirements

The one tool we use for this chapter, you should have already installed from earlier chapters – scikit-learn (http://scikit-learn.org/stable/developers/advanced_installation.html).

Or, if you have the pip installer in Python, you can install it using the following command:

pip install –U scikit-learn

You’ll find the code for this chapter at https://github.com/PacktPublishing/Artificial-Intelligence-for-Robotics-2e.

Task analysis

Our task in this chapter is one that you may have been waiting for if you have been keeping score since Chapter 3, where we discussed our storyboards. We need to navigate around the room on our wheels and find a path to our destination, whether that is picking up a toy or driving to a toybox.

To achieve this, we will be using decision trees, classification (a type of unsupervised learning), fishbone diagrams, which are good for troubleshooting, and finally, path planning.

Introducing decision trees

The concept of a decision tree is fairly simple. You are walking down the sidewalk and come to a corner. Here, you can go right, turn left, or go straight ahead. That is your decision. After making the decision – to turn left – you now have different decisions ahead of you than if you turned right. Each decision creates paths that lead to other decisions.

As we are walking down the sidewalk, we have a goal in mind. We are not just wandering around aimlessly; we are trying to get to some goal. One or more combinations of decisions will get us to the goal. Let’s say the goal is to get to the grocery store to buy bread. There may be four or five paths down sidewalks that will get you to the store, but each path may be different in length or may have different paths. If one path goes up a hill, that may be harder than taking the level path. Another path may have you wait at a traffic light, which costs time. We assign a value to each of...

Random forests

I really wanted to add this section on random forest classifiers, but not just because the name sounds so cool. While I may have been accused of stretching metaphors to the breaking point, this time, the name may have inspired the name of this type of decision tree process. We have learned how to make decision trees, and we have learned that they have some weak points. It is best if the data really belongs to distinct and differentiated groups. They are not very tolerant of noise in the data. And they really gets unwieldy if you want to scale them up – you can imagine how big a graph would get with 200 classes rather than the 6 or 7 we were dealing with.

If you want to take advantage of the simplicity and utility of decision trees but want to handle more data, more uncertainty, and more classes, you can use a random forest, which, just as the name indicates, is just a whole batch of randomly generated decision trees. Let’s step through the process:

...

Introducing robot path planning

In this section, we will be applying decision tree techniques to perform robot navigation. Some people like to refer to these as graph-based solutions, but any sort of navigation problem ends up being a decision tree. Consider as you drive your car, can you divide your navigation problems into a set of decisions – turn right, turn left, or go straight?

We are going to take what we have learned so far and press on to a problem related to classification, and that is grid searching and path finding. We will be learning about the famous and widely used A* (pronounced A-star) algorithm. This will start with grid navigation methods, topological path finding, such as GPS route finding, and finally, expert systems. You will see that these are all versions and variations on the topic of decision trees that we have already learned.

Some problems and datasets, particularly in robotics, lend themselves to a grid-based solution as a simplification of...

Summary

Well, this has been a very busy chapter. We covered the uses of decision trees for a variety of applications. The basic decision tree has leaves (nodes) and links, or branches, that each represent a decision or a change in a path. We learned about fishbone diagrams and root cause analysis, a special type of decision tree. We showed a method using scikit-learn to have the computer build a classification decision tree for us and create a usable graph. We discussed the concept of random forests, which are just an evolved form of using groups of decision trees to perform prediction or regression. Then, we got into graph search algorithms and path planners, spending some time on the A* (or A-star) algorithm, which is widely used for making routes and paths. For times when we do not have a map created in advance, the D* (or dynamic A-star) process can use dynamic replanning to continually adjust the robot’s path to reach its goal. Finally, we introduced topological graph path...

Questions

1. What are the three ways to traverse a decision tree?
2. In the fishbone diagram example, how does one go about pruning the branches of the decision tree?
3. What is the role of the Gini evaluator in creating a classification?
4. In the toy classifier example using Gini indexing, which attributes of the toy were not used by the decision tree? Why not?
5. Which color for the toys was used as a criterion by one of the classification techniques we tried?
6. Give an example of label encoding and one-hot encoding for menu items at a restaurant.
7. In the A* algorithm, discuss the different ways that G() and H() are computed.
8. In the A* algorithm, why is H() considered a heuristic and G() is not? Also, in the D* algorithm, heuristics are not used. Why not?
9. In the D* algorithm, why is there a RAISED and LOWERED tag and not just a CHANGED flag?

Further reading

• Introduction to the A* Algorithm: https://www.redblobgames.com/pathfinding/a-star/introduction.html
• Introduction to AI Robotics by Robin R. Murphy, MIT Press, 2000
• How Decision Tree Algorithm Works: https://dataaspirant.com/2017/01/30/how-decision-tree-algorithm-works/
• Game Programming Heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
• D*Lite Algorithm Blog (Project Fast Replanning) by Sven Koening: http://idm-lab.org/project-a.html
• Graph-Based Path Planning for Mobile Robots, Dissertation by David Wooden, School of Electrical and Computer Engineering, Georgia Institute of Technology, December 2006
• The Focused D* Algorithm for Real-Time Replanning by Anthony Stentz: https://robotics.caltech.edu/~jwb/courses/ME132/handouts/Dstar_ijcai95.pdf