-
Notifications
You must be signed in to change notification settings - Fork 10
Searching The Maze
The first thing the micromouse must do in the maze is find the goal.
In the classic contest, the goal is always the block of four cells in the centre. Using x and y coordinates, this block has corners (7,7) and (8,8). The entire block is the goal area and there may be more than one entrance. Also there is no guarantee that any other entrance/exit will lead to a path back to the start.
The half-size contest has a slightly different rule in that the goal area is any pre-defined rectangular region in the maze. A single cell may be used or a large rectangular area of any dimension. As with the classic contest, the goal area is denoted by the two opposite corner cells.
Depending on the maze configuration and the searching technique, it is unlikely that the robot has used an optimal path to find the goal. Optimal here means a path that is the fastest that a particular robot can run. It is not always the path that covers the least cells. A slightly longer path with fewer turns may suit some robots rather than others.
The principle of maze searching can be quite simple. Assume the robot starts in the centre of a cell:
set the target cell
intitialise and flood the maze
decide the start heading
turn to face that heading
move forward to cell boundary
while robot location is not the target
update the robot location
get the local wall information
update and flood the map of the maze
decide the next command
execute the command
Obviously, this hides a bunch of details but the idea is that basic. In practice, the wall testing and decision making will start a few millimeters before a cell boundary in the expectation that these tasks will take a short time and the robot will still be moving. Flooding the maze is dealt with elsewhere. The idea though is to create a map that gives the cost of getting from every cell to the goal. That cost can be just the manhattan distance (the number of cells) in the simplest method. Once the flooding is complete, the code can use the current robot location and heading, together with the flooding data to decide which cell to visit next.
Note that the flooding during a search assumes that unseen walls are absent. That means that the flooder will always indicate that it is possible to get to the target. One of the aims when searching is to find out if that is true.
There is a limited set of operations, or commands, that can result from this decision making. It is convenient if these are all identified in the design and have their own function to execute them. For example, there must clearly be a command to simply move forward one cell.
Allowing for the start of the search and the end, the complete set of search commands is quite short and each can be given an identifier. Executing each of these has its own sequence of operations. In each of these command, I assume that the robot will be sampling the walls when it is 10mm from the cell boundary. That is, its position is 170mm from the previous boundary.
Assume the robot starts at rest in the center of the cell:
- Reset the drive system
- Set the robot position to 90mm
- Enable the sensors
- Start moving at search speed
- Wait until sensing point
Notice that the steering is not explicitly enabled in this command to avoid unpleasant behaviour at low speed.
The robot will already be moving forward at search speed.
- Enable Steering
- Subtract 180 from the robot position
- Wait until the sensing point
The subtraction may worry you. Remember that zero is the cell boundary and 180 is the next cell boundary. Immediately before executing this command, the robot did a bunch of sensing, flooding and deciding. All that began at 170mm and teh robot continued moving. By the time the command is actually executed, several millimeters of travel have happened and it is not clear how much that might have been. All that is important is that this command must finish after 180mm of travel where the robot will, once again be at position 170.
For this turn, assume that the robot will do an in-place turn. A smooth, integrated turn is more complex but faster. Learn the basics with in-place-turns first. As with the forward move, the robot may not be certain what its position is. Although that can be looked up, it is just easier to subtract 180mm.
- Enable the steering
- Subtract 180 from the robot position
- Brake to a halt at 90mm (cell center)
- Turn left 90 degrees in place (disables sensors and steering)
- execute the SEARCH_START (avoid writing code twice!)
By re-using the SEARCH_START command, you can be sure that the action is performed consistently and the code is not repeated. In-place turns where there is a wall ahead before the turn give the robot an opportunity to adjust their distance from that wall to help with alignment.
Unsuprisingly, the right turn is just like the left turn. It might be tempting to re-use the same function with a parameter that says which way to turn. If all you ever want is in-place turns, that is fine. When it comes to implementing faster, smooth search turns, you may find that the left and right turns are not consistent and it is better to deal with each in its own functions.
- Enable the steering
- Subtract 180 from the robot position
- Brake to a halt at 90mm (cell center)
- Turn right 90 degrees in place (disables sensors and steering)
- execute the SEARCH_START (avoid writing code twice!)
Inevitably, the robot will find itself in a dead-end and need to turn around. Sometimes this will happen even if there is no dead end if the newly discovered maze walls indicate to the flooder that there is no point in carrying on any further. Dead ends provide an opportunity for the robot to make use of the wall to realign itself. here, though, the robot just does 180 degree turn in place. Again, this looks exactly like a left or right turn but with a larger angle. Some builders also like to do the turn in two 90 degree phases so that the robot can adjust its alignment.
- Enable the steering
- Subtract 180 from the robot position
- Brake to a halt at 90mm (cell center)
- Turn left or right 180 degrees in place (disables sensors and steering)
- execute the SEARCH_START (avoid writing code twice!)
Stopping the robot is a reasonably simple business. In the search phase, a STOP command means that the robot is entering the current target cell. This is a good place to save the current maze map to EEPROM if desired. Writing to EEPROM takes quite a while so it is best done when stationary.
- Enable the steering
- Subtract 180 from the robot position
- Brake to a halt at 90mm (cell center)
- Save the maze
Searching is not always done just to the goal area or the start cell. When a search run is finished, the robot must work out what to do next. In particular, it must decide whether the route found is good enough for a speed run.
Because your robot reached the goal, you know there is a valid route. For a starter robot, it is probably enough just to search back to the start and then try for a speed run using whatever you have discovered. A great advantage of this tactic is that you get a speed run in as soon as possible and any chance for faults to show up after prolonged running are reduced.
Remember that the flooder, in search mode, thinks that unseen walls are absent. You must ensure that the speed run path only goes through cells that have neen explored
In general though, the search back is likely to reveal that there may be a better route than the one already found and you might choose to search come more. There are many strategies for improving the route. The simplest is possibly to first search for the goal and then repeatedly search back to the start and perform a speed run to the goal. The return searches will improve the route although the absolute best route may not be found. It is often more important to get reliable speed runs done than fully optimise the route or increasing the speed run performance too quickly.
The contest rules limit the number of runs the robot is allowed to make. If you want to do a lot of searching without wasting runs, do the return search to cell 1 (the cell to the north of the start cell) rather than cell zero. A couple of back-and-forth searches are often enough to find a good route.
The more advanced builder can look into marking cells as visited during the search. One indication of an optimal route is that a route calculated under the assumption that unseen walls are absent does not pass through an unseen cell.