Rules Of The Maze (Robot Avoidance Rules and Strategy)

By: Matt Shellhammer (Electronics & Control Engineer)

Approved by: Lucas Gutierrez (Project Manager)

Introduction

When traveling through the maze, robots have the possibility to encounter other robots. To ensure the robots will be able to successfully navigate the maze and complete the mission objectives, we need to have general rules of the maze. These rules should be followed by all projects to guarantee that all robots are following the same rules for navigating the maze.

Possible encounter cases:

2.1.  Face-to-Face in hallway (North/South & East/West)

2.2.  Face-to-Back in hallway (North/South & East/West)

2.3.  T – Intersection

 

Rules for robots that occupy more than one room

Some projects have robots that are larger than one room size which if not addressed can cause issues with the rules of the maze. For projects that will take up more than one room size, the excess robot space should be in the previous room. This is to ensure that robots will not be seen as within the intersection when they have not yet stepped into the intersection. This will mean that robots that take up more than one room will be occupying their current room and part of the previous room, which should not cause any problems for the rules of the maze. If the robot has just stepped through the intersection and is partially within the intersection, it will be cleared once they step into the next room.

Rules for detection

To detect robots within intersections and in face-to-face or face-to-back encounters, detection should be continuous since robots will not be moving in synchronization and a robot can step into a new room at any time. Robots should be able to detect a robot in the next room ahead since all decisions will be made within a one room range.

Rules for encounters 2.1 (Face-to-Face) & 2.2 (Face-to-Back)

For encounters 2.1 & 2.2 the rules will be defined as follows:

A robot that is in a hallway (vertical/horizontal) that encounters another robot, either face-to-face (case 2.1) or face-to-back (case 2.2) will immediately pause movement for three seconds. If this robot still detects the other robot after these three seconds, the robots must be in case 2.1. If the robot no longer detects the other robot after these three seconds, the robot then must be in case 2.2.

If the robots are in case 2.1 and they are in a vertical hallway (north/south) the robot facing north has the highest priority. If the robots are in case 2.1 and they are in a horizontal hallway (east/west) the robot facing east has the highest priority. In case 2.1 robots facing either south or west have the lowest priority and are therefore left with the burden of clearing the path. The robot with lower priority should turn around and retrace its path until the robot with highest priority is able to pass. When the robot is retracing its path it should retrace its path until its last decision point (last intersection) and wait for the robot to pass. If the higher priority robot tries to go down the hallway that the lower priority robot is waiting in, the robots are now in either case 2.3 or 2.4. In this case the robot within the intersection is now at lower priority and follows the rules explained in Section 4.

If the robots are in case 2.2 they will then continue on with the desired path.

Rules for encounters 2.3 (T – Intersection)

For encounter 2.3 the rules will be defined as follows:

When a robot comes to an intersection it will attempt to step into the intersection and either turn or move straight along its path. If a robot steps into an intersection and sees another robot as it tries to make its maneuver, then these robots will be in case 2.3. In this case the robot that is within the intersection (in the middle of the T – intersection) has the lowest priority and must move out of the way of the other robots (if the other robots are in the path of the low priority robot). The lowest priority robot will step down the hallway that is not blocked and then wait for the other robot to pass. The robot may try to step down the hallway that the waiting robot is in and this will mean that this robot is now at lower priority and has to move for the previously waiting robot. A robot waiting at an intersection for another robot to pass should timeout after waiting ten seconds for a robot to pass. After timing out the robot should then make a second attempt to continue along its path. This timeout is used for when a robot in an intersection detects another robot in its path, as long as the detected robot was not traveling through the intersection (e.g. waiting to enter another intersection).

 

Recovery strategy

If a lower priority robot is required to clear the path of a higher priority robot then there must be a recovery strategy for that lower priority robot. The recovery strategy for case 2.1 should have the robot only travel forwards and backwards along its designated path to allow for the robot to easily repeat the steps taken clear the path. This then allows the robot to either step forward or backward along the recorded path, and requires no modification to the robot’s path. And for cases 2.3 and 2.4, the robots should only move off the designated path to move out of the way for other robots when required, and then continue back on the designated path.

 

Special Cases to consider

Three robots at T – Intersection (special case of 2.3)

Rules for three robots within a T – Intersection

If a robot is thought to be in case 2.3, then attempts to move down the other hallway, and then again encounters another robot, then there must be three robots within this intersection. I don’t know we should deal with this case… What if another robot comes up behind this robot, it is now boxed in… Additionally, the other robots do not know that there is three robots (four if you include the additional robot) at the intersection.

Other things to consider

Detection of robots multiple rooms away, so when there’s an intersection with three robots, there is an open space for the robot within the intersection to move into to allow the other robot to move by.