Exploring the Map

A rule set and tile state set were created for the compulsory problem, which will completely explore a LEGO tile course. The compulsory problem is solved entirely using reflex and tactical level rules. Here we only describe the tactical rules used.

Terms

T
A 3-way intersection.
+
A 4-way intersection.
Connection
A side through which the robot may enter or leave a tile. Straight and curved tiles have two connections (at opposite ends for a straight tile; on adjacent sides for a curved tile); Ts have three connections; +s have four connections. A connection is explored if the tile has either been entered or exited through it; it is unexplored if it has not. When a connection is explored, it is marked on the tile's state with a line (imitating the actual tile marking).
Unexplored Tile
A tile that has never been visited by the robot. A previously unexplored tile is one that has not been visited before the current execution cycle. All unexplored tiles except the start tile (which is in the start state) are in the unknown state.
Partially Explored Tile
A tile that has been entered at least once, but which has at least one unexplored connection.
Completely Explored Tile
A tile whose connections have all been explored.
The key features for each tile type were identified, and used to create states that could mark them as they were found. It is possible to identify Ts and +s based solely on the tile markings, while straight and curved tiles require direction information from the navigator.

The First Tile

We make no assumptions regarding the initial position of the robot when execution is first started. As long as we are still on the first tile, we simply follow the line and advance to the edge of the tile. When we reach the edge (identified by all five sensors over black), we mark the connection as explored with the

state and use the

navigation command to proceed to the next tile on the map.

There is a situation in which this strategy will result in an error: if the robot starts on a +, but before the crossing at the center of the intersection, the crossing will be mistaken for the start of a new tile. This can be detected and corrected in the course of tile identification, as will be described below.

Entering a Previously Unexplored Tile

When a previously unexplored tile is entered, it will be in the unknown state. Depending on the sensor inputs, we transition to either

(if either outboard or more than two of the inboard sensors are black) or

In the first case, we remain in the first state until we have left the black line, and then transition to the second. At this time, we have recognized that we have entered a new tile, and are past the tile-edge marker.

Intersections

If an outboard sensor goes black and then white, while no more than two of the inboard sensors are black, we have encountered tile encoding marks. If a single encoding mark is detected on one side or the other we have entered a T from the side; if we detect two encoding marks we have entered either a T from the bottom or a +. The states that identify these situations are

If all three inboard sensors go black and the outboard sensors do not, then the error in identifying the first tile referred to earlier has occurred, and we are still on the start tile. In this case, we are able to recognize that the tile we are on now is a +, and we will mark it as such. The tile to the south is actually labelled correctly (the marked connection does exist), even though we have not ever entered or exited it.

If we have entered a T from the side, we will proceed straight across the top of the T, marking the tile with the part we explored and the direction we exited. If we encountered two stripes, so we have entered either a T from the bottom or a +, we will turn right at the intersection (this is much easier than trying to disambiguate based on the disappearance of the center line if it's a T). Before we exit the tile, we will encounter either a single or a double tape stripe, which will enable us to disambiguate the tile.

Curved Tiles

The navigator is used to identify curved tiles. If the dead-reckoning navigation system concludes that we have turned more than 45 degrees since entering a tile, we enter a state recognizing that we have entered a turn:

Exiting a Tile, and Straight Tiles

When we reach the tape stripe identifying the end of the current tile (all sensors go black), we enter one of the states identifying the end of the tile:

Notice that in the case of a T, the exit used is marked. This is used to avoid exiting through the same connection the next time we enter the tile, and reduce the possibility of looping endlessly through a small part of the course (this is not necessary with a +, as the exit can be inferred).

If we have reached the end of the tile without recognizing it as anything else, it is a straight tile, and is recognized at this time

Re-entering a Tile

It may be necessary re-enter a tile that has been either partially or completely explored. Exploration continues on partially explored tiles, while completely explored tiles are re-traversed.

The start tile

We treat the start tile as if it were a completely unexplored tile when we re-enter it. While this reduces search efficiency in some cases (we will have ``forgotten'' that we exited it already), it reduces the number of rules and states.

Intersection Tiles

In a partially explored intersection, we exit through one of the unexplored connections. In a completely explored intersection, we exit through a connection other than the most recently exited one. If we have entered a partially explored intersection through its only previously unexplored connection, it has become a completely explored tile and we treat it as such.

The choice of exits is selected according to the following priorities:

These priorities are encoded in the line-following rules associated with the states. Also, in all these cases, the selected exit is marked.

Termination

Each tile state is marked as either a ``terminal'' or a ``Nonterminal'' state. The unknown and states representing fully explored tiles are terminal states; states representing partially explored tiles are nonterminal states.

Exploration stops when (1) every tile on the map is in a terminal state, and (2) the current tile is not in the Unknown state. The first condition captures the intent that we wish to stop when every tile that has been entered is completely explored, but will cause us to stop early when we enter a previously unexplored tile. The second condition handles this special case.

Example

A sample course is

with the result

Tile State Set

The complete tile state set for the compulsory problem, including rotations, is:

The ruleset has roughly 2100 rules.