Software Lab 13: For Whom The Toll Roads

The questions below are due on Tuesday May 07, 2019; 08:25:00 PM.
 

Files

This lab description is available as a PDF file here. Code is available here, or by running athrun 6.01 getFiles.

1) Getting Started

There are no assigned partners for this lab, but you may find it helpful to work with a partner of your choosing. You may use any machine that reliably runs soar.

Get today's files by running

> athrun 6.01 getFiles

2) Remembrance of Things Past

The file mazeBrain2.py in this week's distribution closely resembles a completed version of mazeBrain.py from last week's design lab:

• The on_load function (called whenever the brain is reloaded) uses the get_path function to determine a path from the robot's starting position to the goal, and plots that intended path in a graphing window. This path is stored as robot.path.
• The on_step function (called every 0.1 seconds) attempts to drive the robot to follow along the desired path.

3) Running

In soar, load the sl13world.py simulation world (from this week's distribution), and open the mazeBrain2.py brain. Start the robot running along its path.

Remember that we represented the maze (including the mapping between the maze and the physical world) with an instance of a class called RobotMaze. Answer the following questions about the specific instance of RobotMaze that represents this maze.

4) A New Slant On An Old Problem

The paths that our earlier search generated leave something to be desired. In particular, it looks like the robot could get to the goal more efficiently if it were allowed to move along diagonal paths, as well as moving vertically or horizontally.

Because we want our search to return a path where the robot travels the minimum possible distance to get to the goal, we will implement this new behavior using a uniform-cost search¹.

Implement a successors function for this new search, where the robot can move to any of the 8 adjacent cells, instead of up only up, down, left, and right.

Remember that a successors function for uniform cost search takes a slightly different form than the kind we used in BFS/DFS. In uniform cost, we need to know not only the possible child states, but also the cost of reaching each of them. As such, rather than just returning a list of child states, your successors function should return a list of (state, cost) tuples, where state is one possible child state, and cost is the cost of reaching the state directly (i.e., the cost of the link between the parent and child states, not the cost of the entire path).

In this case, we will use as our cost the distance the robot would have to travel to move between those states, in units of cell-widths (not in meters).

Implement the uc_maze_successors function, which should take in an instance of RobotMaze representing the maze under consideration, and should return an appropriate successor function.

You will also have to update the `get_path` function to that it uses uniform-cost search (along with your new successors function) to find the path to the goal, rather than using the simpler search from earlier.

Note that rather than returning only a path, this implementation of uc_search returns a tuple (path, cost), where path is a description of a path to the goal (as of a list of discrete indices), and cost is the total cost of the path returned.

Run your updated code, making a note of the path that was returned. Also note the amount of time the get_path function took to find a path.

5) Go, Speed Racer

One thing to note is that the search seems to take a while (probably at least a couple of seconds). However, we can speed up the search by using a heuristic. If the heuristic is admissible, we can still guarantee that the path returned by uc_search will be optimal (in terms of minimizing cost).

For now, we will use as our heuristic the Euclidean distance between the state being considered and the goal. Implement this heuristic function, and modify your get_path procedure to make use of it².

Now run your search again.

6) Toll Roads

Now, let's imagine that certain spots in the world have tolls associated with them (that is, you must pay some amount of money to enter certain cells). A common problem in GPS route-planning systems involves allowing a user to avoid toll roads, and we will deal with a similar problem here.

Set TOLLS = True in mazeBrain2.py, and hit "Reload Brain and World" in soar. You will see a red line near the bottom of the screen, representing cells that have the toll associated with them. Ideally, we would like to be able to prevent our robot from moving through those cells in certain conditions.

The toll_dollars(cell) function tells you the cost (in dollars) of the toll for moving into the given cell.

Update your search to use a new cost model that takes into account both the distance traveled and the amount of money paid in tolls. Implement this new cost model by implementing a new successors function called toll_maze_successors.

This function should make sure that the cost of moving cells_per_dollar cells is equivalent in terms of cost to paying a $1 toll (i.e., you would rather go that many cells out of your way than pay $1 worth of tolls).

Importantly, if we want our heuristic still to work, we need to make sure that the units of our new cost function match those of the heuristic (i.e., both functions should think of cost in terms of distances measured in cell-widths).

Implement the toll_maze_successors function and modify your get_path function to make use of it. Run the search with cells_per_dollar = 1000 and start your robot running.

 

---

Footnotes

¹Throughout this lab, we will use the term length to refer to the number of states in the path, and we will use the term cost to refer to the total cost of the path (for now, the total distance the robot would travel if following the path, in units of cell-widths). (click to return to text)

²For more information on the arguments uc_search takes, see the lib601 documentation for uniform_cost_search. (click to return to text)