In the last lesson we began to investigate how a rover on Mars might navigate the terrain with minimal human input. However, up until now, we've still had to supply each individual command to our rover.
In this lesson, we'll continue to optimize our rover control code and start working on some possible methods of automating rover navigation.
Before we start writing new code, let's import our two constant companions, numpy and matplotlib.
In [1]:
import numpy
import matplotlib.pyplot as plt
%matplotlib inline
In [2]:
def show_map(terrain):
'''
show_map takes a 2D Numpy array representing a simplified terrain map and prints
out a colorful version using numpy.imshow
'''
plt.figure(figsize=(10, 5))
plt.imshow(terrain, interpolation='none')
plt.xticks([]), plt.yticks([])
plt.show()
In [3]:
def move_rover(direction):
'''
move_rover takes a movement direction as a string, either 'up', 'down', 'left'
or 'right' and then returns an appropriate 2-element numpy array which will adjust
a location coordinate array accordingly
'''
if direction == 'up':
return numpy.array([-1,0])
elif direction == 'right':
return numpy.array([0,1])
elif direction == 'down':
return numpy.array([1,0])
else:
return numpy.array([0,-1])
Note that in crash_check_and_move we've made a small change, so that now we can send either 'up', 'down', 'left', or 'right' directly, instead of first querying our move_rover function. Instead, the call to move_rover is the first line of crash_check_and_move so we can change the rover's position with a single command.
In [4]:
def crash_check_and_move(location, movement, terrain):
'''
crash_check_and_move takes 3 variables: the current position, the desired movement
to make and the current terrain map (with rover position included). It checks
that the desired movement is 'allowed' and if it is, performs the movement,
updating both position and the terrain map.
If the movement is 'illegal', it simply returns the position and terrain map
unchanged.
If the movement will bring rover to the 'destination' it prints out a
congratulatory message.
'''
movement = move_rover(movement) ##This is the new line to make our lives easier
old_y, old_x = location
new_y, new_x = location + movement
if terrain[new_y][new_x] != 3 and terrain[new_y][new_x] != 5:
terrain[new_y][new_x] = 1.
terrain[old_y][old_x] = 0
return numpy.array([new_y,new_x])
elif terrain[new_y][new_x] == 4:
terrain[new_y][new_x] = 1.
terrain[old_y][old_x] = 0
print "You've reached your destination!"
return numpy.array([new_y,new_x])
else:
return location
Now that we have our functions from the previous module loaded, let's go ahead and load up our terrain map again. We also need to initialize our location coordinates to $[7,7]$.
In [5]:
terrain = numpy.loadtxt("./resources/terraindata/terrain1.csv",delimiter=",")
location = numpy.array([7,7])
show_map(terrain)
You'll recall that in the last lesson, we determined that one route for the rover to take to reach its destination was given by the follow set of movements:
With our movement functions, we've already automated things like obstacle checks, but we still had to call crash_check_and_move for every direction and that was kind of a pain. So now we're going to explore using loops to help us further automate the rover motion.
In [6]:
for i in [1,2,3,4,5]:
print i
Let's break down what's happening here. We've asked Python to iterate through a set of values, in this case, the numbers one through 5. It does that by setting the variable i equal to the first value in the set, then it executes all of the code below it using that specific value of i. Then, it comes back to the top, sets i equal to the second value in the set and goes through all of the code again. This continues until the loop has run for all of the values in the set we've defined.
Loops don't have to just deal with numbers, either. Strings can be looped over in exactly the same way:
In [7]:
for ingredient in ['bacon','lettuce','tomato']:
print ingredient
These are called for loops, because they loop over code once for every element in a set that we've defined.
In the last lesson, we had to call crash_check_and_move for each individual movement. Now we're going to do the same thing, but instead of typing them all out ourselves, we'll let the for loop handle it instead.
First, we need a list of the individual directions in order. Consulting our bullet points above leaves us with the following.
In [8]:
direction_list = ['left','left','left','up','left','left','up','up','up','up','up','right','right']
In [9]:
print direction_list
Ok, now that we've got our direction list ready to go, we want to create a for loop that will send those commands one at a time to our crash_check_and_move function.
In [10]:
for i in direction_list:
location = crash_check_and_move(location,i,terrain)
Ok, if that worked, then we should be able to print out our terrain map and our blue rover square should be at the destination.
In [11]:
show_map(terrain)
It worked! It's important to recognize that our 2-line loop above is no different than typing out all of those movement commands manually, it's just a lot easier.
Our for loop has made it much easier to send lots of commands to our rover in just a few lines of code, but we're still telling the rover each turn it has to take. That isn't going to work very well when the rover is on Mars and we've got a serious communication delay.
So how do we give the rover a set of (relatively) simple commands that will allow it to make its way to the destination point?
Let's try out a simple option. We'll implement a rover control logic system that uses the following rules:
That's it. Let's see what happens.
It sounds silly, but what does it mean to turn right if we're observing the rover from above? Let's break it down.
If the rover is going:
So turning right in our little flatland means cycling through our four commands in the order
$$\text{left} \rightarrow \text{up} \rightarrow \text{right} \rightarrow \text{down}$$and then repeating. How do we program that?
First, it's usually easier to program cycles of things using numbers, not strings, so let's translate our direction commands into a more convenient system.
In [12]:
directions = ['left','up','right','down']
Done! We just made a list of our four commands. And now we can refer to them using numbers as follows:
In [13]:
directions[0]
Out[13]:
In [14]:
directions[2]
Out[14]:
Ok, now that we can use numbers to refer to those directions, how do we get them to cycle and repeat the way that we want?
The numbers 0 through 3 correspond to our four directions, so we just need a function that counts from 0 to 3, then starts over at 0 again. And we already have all the tools we need to do that.
In [15]:
def turn_right(dir_num):
'''
Increments a direction counter from 0 to 3, then resets to 0
'''
dir_num += 1
if dir_num > 3:
dir_num = 0
return dir_num
Note that we've used another little Python shortcut +=. It's just a contraction of a longer command that would read
dir_num = dir_num + 1
It just takes our variable dir_num and adds 1 to it. Then we've got an if statement to check if we've reached a number greater than 3, in which case, we reset back to zero. Easy as pie. Let's see if it works.
Let's assume we're already going left, 0, and then turn right.
In [16]:
turn_right(0)
Out[16]:
We can even feed that directly into our list of directions:
In [17]:
directions[turn_right(0)]
Out[17]:
Now we should have all the pieces we need for our "always turn right" control program. We'll start the rover moving to the left, then, whenever it hits an obstacle, it will turn right and move in that direction until it hits an obstacle and continue in this way until (or if) it reaches our destination.
First, let's reload our terrain data, since we've already "solved" this route with our for loop above.
In [18]:
terrain = numpy.loadtxt("./resources/terraindata/terrain1.csv",delimiter=",")
location = numpy.array([7,7])
show_map(terrain)
How will we know if we hit an obstacle? If you recall, we programmed crash_check_and_move to return the location unchanged if there was an obstacle in the way, so we can check that our "new" location is different from our "old" location. If they're the same, then we know we've hit an obstacle and we can turn_right.
In [19]:
def always_turn_right(location):
dir_num = 0 #start out moving left
for i in range(31):
new_location = crash_check_and_move(location, directions[dir_num], terrain)
if new_location[0] == location[0] and new_location[1] == location[1]:
dir_num = turn_right(dir_num)
location = new_location.copy()
Ok, let's give it a shot!
In [20]:
always_turn_right(location)
show_map(terrain)
It worked! Here's a little video that shows the path that our "always turn right" control program yields for the rover:
This line was kind of random, wasn't it?
for i in range(31):
How did we know that we needed to create a for loop with 31 steps in it to reach the end?
We didn't. I cheated. And cheaters never win. Especially on Mars.
If we always have to count the right number of steps to feed to our for loop, that's really not that much better than just running the commands manually, is it? For tasks like this one, it's better to have a loop that just runs and runs until a given condition is met.
These types of loops are called while loops. They're kind of like a combination of an if statement and a loop. We give the while loop a condition and for as long as that condition is true, the loop will continue to run. Once the condition is met, the loop will stop.
So for our rover program, we can set up the same always_turn_right function, but this time we'll use a while loop that will run until our location is equal to $[1,4]$, the coordinates of our destination.
We can also create a counter variable, that will add one to itself each time the loop executes, so we can count how many iterations the loop went through before the rover arrived at its location.
First we need to reset our terrain map again:
In [21]:
terrain = numpy.loadtxt("./resources/terraindata/terrain1.csv",delimiter=",")
location = numpy.array([7,7])
or operatorThe last bit of information we need for the while loop is something called an or operator. In the for loop above, we used the and operator to write
if new_location[0] == location[0] and new_location[1] == location[1]:
which meant that both of the conditions had to evaluate to true for the if statement to be true.
The or operator, by contrast, allows an if statement (or a while loop!) to evaluate to true if either or both of the conditions are true.
You've probably seen something called a truth table and it's exactly these same ideas which are used.
For our while loop, we want to keep running the code within until we reach our destination cell, $[1,4]$. Therefore, if either our row number isn't $1$ or our column number isn't $4$, we want to keep going.
In [22]:
def always_turn_right(location):
dir_num = 0 #start out moving left
i = 0 #this is our counter variable
while location[0] != 1 or location[1] != 4:
new_location = crash_check_and_move(location, directions[dir_num], terrain)
if new_location[0] == location[0] and new_location[1] == location[1]:
dir_num = turn_right(dir_num)
location = new_location.copy()
i += 1
return i
Let's try out our new function:
In [23]:
i = always_turn_right(location)
show_map(terrain)
That also worked! Great. How many iterations did it take? Let's check on the value of i.
In [24]:
print i
Well, that's either a massive coincidence, or I already ran the while loop to figure out how many steps to put in the for loop. You be the judge.
Either way, hopefully it's becoming clearer that loops are very powerful, but that you need to choose the right tool for the job to take advantage of their benefits.
In [25]:
terrain = numpy.loadtxt("./resources/terraindata/terrain2.csv",delimiter=",")
location = numpy.array([7,7])
show_map(terrain)
This terrain map is more or less the same as the last one, it just has fewer obstacles. Should be easier then, right? Let's try it out.
Actually, let's not try it out. Can you see why it's probably a bad idea to give this map to our always_turn_right function? Here's another video that will show you what can go wrong.
As you can see, our rover gets stuck going in circles. There are two points to take note of here.
First, this lets us know that our "always turn right" plan will only work in very special situations where the landscape is set up just so. That doesn't sound very reliable.
Second, while loops can be a little dangerous. While the video above stops after just a few times around, the while loop that we wrote above will just keep going. In fact, if we run this second terrain map in that while loop, we'll have to crash Python to make it stop.
If you do have a runaway loop, you can always navigate up to the menu on top of this page and select Kernel -> Interrupt Kernel to make it stop.
while loops under controlYou can always interrupt a while loop that's gone off the rails using the Interrupt Kernel menu option, but that's the brute force approach and won't really offer any insight about what's going wrong.
A better option is to build in some safeguards. In our while loop version of always_turn_right, we had a variable i which we used to count the number of iterations. One safeguard we can implement is to add an extra if statement in the while loop that will break the loop if i reaches some value that we specify.
To break out of the loop, we use the command break.
Let's try it out. And remember, this isn't going to "work" in the sense that the rover will reach its destination. But at least it will stop on its own.
In [26]:
def always_turn_right(location):
dir_num = 0 #start out moving left
i = 0 #this is our counter variable
while location[0] != 1 or location[1] != 4:
new_location = crash_check_and_move(location, directions[dir_num], terrain)
if new_location[0] == location[0] and new_location[1] == location[1]:
dir_num = turn_right(dir_num)
location = new_location.copy()
i += 1
if i > 1000:
break
return i
In [27]:
always_turn_right(location)
Out[27]:
In [28]:
show_map(terrain)
So the rover hasn't reached its destination, but at least the program stopped running.
So remember, for loops have a built in stopping point, for situations where we know exactly how long we want the loop to run.
while loops will loop until their condition is met, but if the condition isn't met, they'll just keep going, so we have to exercise a little bit of caution. (Or just hit interrupt).
Always turning right hasn't worked out that well. We could try always turning left, but that probably won't work well either.
There are a number of increasingly complicated algorithms for navigating any type of maze-like path. We're going to implement the simplest version, which is called the "Random Mouse algorithm."
Here's how it works:
We only need one new NumPy function to complete our random mouse code, which is a function which provides random integers. It's called numpy.random.randint and it provides a random integer within a specified range, where the bottom of the range is inclusive and the top of the range is exclusive. Since we have a total of four possible directions, we want a random number from the set $[0,1,2,3]$, so each time we hit an obstacle, we'll ask for a new direction with
numpy.random.randint(0,4)
We're also going to be using two while loops to search for our destination. The outer loop, or parent loop, will run until the rover reaches coordinates $[1,4]$. The inner loop, or child loop, will run every time we change direction and will keep the rover moving in that direction until we hit the next obstacle.
When we have a while loop within another while loop, or an if statement within another if statement, we say that they are nested.
In [29]:
terrain = numpy.loadtxt('./resources/terraindata/terrain2.csv',delimiter=',')
location = numpy.array([7,7])
directions = ['up','down','left','right']
i = 0
new_location = numpy.array([0,0])
while location[0] != 1 or location[1] != 4:
rand_dir_int = numpy.random.randint(0,4)
rand_dir = directions[rand_dir_int]
while new_location[0] != location[0] or new_location[1] != location[1]:
new_location = crash_check_and_move(location, rand_dir, terrain)
location = new_location.copy()
new_location = numpy.array([0,0])
i+=1
show_map(terrain)
print i
It works, but wow that's a lot of iterations. Try running the random mouse code a few more times and see how widely the number of iterations can vary. It is random, after all.
Random mouse is definitely not an efficent way to navigate, but it does work without any extra input from us, so that's definitely progress.
As an extra challenge, wrap the entire random mouse code in a for loop and run it 1000+ times, saving the number of iterations that each run takes. Then plot those iterations to see if our numpy.random.randint function is really giving us output that seems suitable random.
In [30]:
from IPython.core.display import HTML
def css_styling():
styles = open("../styles/custom.css", "r").read()
return HTML(styles)
css_styling()
Out[30]: