Lecture
The right-hand rule. Elements of a maze. Building a map of a maze.
Recall the amusing story told by the English writer Jerome K. Jerome in his book “Three Men in a Boat (To Say Nothing of the Dog)” (if you haven't read it, you really should — it's in Chapter 6). How many people laughed at the eccentric Harris, who got lost in the Hampton Court maze!
— We'll just step in here so you can say you've been in the maze, but it isn't complicated at all. It's almost absurd to call it a maze. We'll walk around for about ten minutes and then go and have breakfast, — Harris kept telling his relative.
But alas! Not only did he get lost himself, he also led astray the people he had undertaken to rescue from the tormenting wandering through the maze. At least twenty people were following him, including a woman with a child, who had been unsuccessfully searching for the way out of the maze all morning.
Following his tactic, Harris kept turning right the whole time. It seemed to him that he was just about to get out of the maze. But time passed, and… the whole party, led by Harris, found itself back at the spot where they had already been. Half a bun, dropped by the child and noticed by Harris's relative seven minutes earlier, unmistakably marked the place they had recently passed through.
Then Harris suggested going back and starting all over again. The suggestion to start over was not met with much enthusiasm, but everyone agreed to turn back.
The procession turned around and trailed after Harris in the opposite direction, but ten minutes later the whole party once again found itself in the center of the maze. The subsequent attempts ended in the same failure. Whichever way they turned, every path led them back to the center. This began repeating itself with such regularity that some of them simply stayed put and waited for the others to walk around and come back to them.
Finally, the despairing maze enthusiasts called on the keeper for help, and he led them out to “freedom”.
Poor Harris would not have had to wander about and torment people if he had known an algorithm for finding paths through a maze. Several such algorithms exist. One of them is connected with the ancient Greek myth of the legendary hero Theseus, who dared to enter the maze in order to find and kill the monstrous Minotaur inside it. Ariadne helped him find his way out of the maze by giving Theseus a ball of thread, one end of which she held herself. As Theseus went deeper into the maze, the ball unwound; later, winding the thread back up, Theseus safely made his way back to the exit.
Let us picture a maze as a finite system of landings from which corridors branch out, each corridor connecting two landings (we will call such landings adjacent); however, there may also be landings from which only a single corridor leads (we will call such landings dead ends). Geometrically, a maze can be represented as a system of points A, B, C, … (representing the landings) and a set of segments AB, BC, … (representing the corridors) joining certain pairs of these points (fig. 1).
Fig. 1
We will say that landing Y is reachable from landing X if there is a path leading from X to Y through intermediate corridors and landings. More precisely, this means that either X and Y are adjacent landings, or there exists a sequence of landings X1, X2, X3, ..., Xn, such that the pairs of landings X and X1, X1 and X2, X2 and X3, …, Xn and Y are adjacent. For example, in the figure shown, landing H is reachable from dead end A by way of the path AB, BC, CD, DE, EF, FD, DH, whereas landing K is not reachable from A. At the same time, if Y is reachable from X at all, then it is also reachable by a simple path, that is, a path in which each landing (and, all the more so, each corridor) is traversed only once. In the previous example the path was not simple, but by cutting out the loop DE, EF, FD we obtain the simple path AB, BC, CD, DH.
It is assumed that the Minotaur is located on one of the landings of the maze (let us denote it M), and Theseus, setting out to find him from landing A, where Ariadne awaits him, must solve the following problem: it is required to determine whether M is reachable from A or not1. If it is reachable, he must reach it by whatever path, but must return to Ariadne by a simple path. If M is not reachable, he must return to Ariadne.
There can be an unlimited variety of different mazes, and the relative positions of landings A and M within a given maze can likewise vary. Since Theseus knows nothing in advance about the layout of the given maze or about the Minotaur's location in it, the solution to the stated problem is conceived as a general search method suitable for any maze and for any arrangement of landings A and M within it. In other words, the solution is conceived as an algorithm that solves any problem of this type (this, as is well known, is precisely what constitutes the property of an algorithm known as generality).
The search algorithm. To construct such an algorithm we will consider one special search method. At any stage of the search process, in accordance with this method, the corridors must be distinguished as follows:
1) not yet traversed by Theseus at all (conventionally — green);
2) traversed once (yellow);
3) traversed twice (red).
Furthermore, while at any given landing, Theseus can move to one of the adjacent landings by means of one of the following two moves:
1. Unwinding the thread. Moving from the given landing along any green corridor to an adjacent landing. In doing so, Ariadne's thread unwinds along this corridor, which is thereafter considered yellow.
2. Winding the thread back up. Returning from the given landing along the last-traversed yellow corridor to an adjacent landing. In doing so, Ariadne's thread, previously unwound along this corridor, is wound back up, and this corridor is then declared red.
It is assumed that Theseus makes markings of some kind that will later allow him to tell green corridors apart from green ones; yellow ones are recognizable by the fact that Ariadne's thread runs along them2. The choice of one move or the other depends on the situation Theseus observes at the landing where he currently finds himself; this situation can be characterized by one or several of the following signs:
1. Minotaur. The Minotaur has been found at the given landing.
2. Loop. Ariadne's thread already runs through the given landing; in other words, at least two yellow corridors radiate from the landing.
3. Green street. The given landing has an exit into at least one green corridor.
4. Ariadne. Ariadne is at the given landing.
5. The fifth case. None of the preceding signs is present.
Our search method can now be specified by the following scheme (see Table 1):
Table 1
While at any given landing, Theseus makes his next move as follows: he checks, in the numerical order of the left-hand column of the scheme, which of the listed signs applies; upon finding the first such sign, he (without checking the remaining signs) makes the corresponding move (or stop) from the right-hand column. Such moves are made until a stop occurs.
The validity of the proposed method follows directly from the following three statements:
1. For any relative arrangement of A and M in the maze, after a finite number of moves a stop will necessarily occur either at the Minotaur's landing or at Ariadne's landing.
2. If the stop occurs at the Minotaur's landing, then the Minotaur is reachable. Moreover, in this case Ariadne's thread turns out to be stretched along a simple path leading from A to M; by winding up the thread, Theseus can now return along this path to Ariadne.
3. If the stop occurs at Ariadne's landing, then the Minotaur is unreachable.
The proof of these statements can be found, for example, in .
And we will show, using two examples, how the proposed method works.
Example 1. Suppose the search for the Minotaur, who is located at F, begins from landing A of the maze (see fig. 1). The search process in accordance with our method is conveniently depicted by means of the scheme presented in Table 2 (because of the freedom in choosing the green corridor, this is only one of several possible schemes).
We see that in this case the Minotaur is reachable. By picking out, in the next-to-last column, those corridors that remained yellow (in accordance with the entries in the last column), we obtain the following simple path leading from A to F: ABCDF.
Example 2. If, on the other hand, the search begins from landing K, the search process can be depicted in the scheme presented in Table 3.
We see that in this case the Minotaur is unreachable.
Note that the algorithm described does not possess the property of definiteness — from some landing there may be exits into several green corridors, and our prescription does not specify which of them to choose; more precisely, it allows an arbitrary choice among them. For this property to hold, it is necessary to regulate how the choice of the next corridor to check should be made in such situations.
Table 2
Table 3
Draw up a scheme for finding the way out of the maze (from landing 1 to landing 10 — see fig. 2), using the algorithm described in this article:
If a landing has exits into several green corridors, movement among them should proceed “clockwise”.
Please present the schemes in the form of tables similar to Table 2 and Table 3.
One of the simplest rules for getting through a maze is the "one-hand rule": while moving through the maze, you must keep touching its wall with your right or left hand the whole time. This algorithm was probably already known to the ancient Greeks. You will have to travel a long way, going into every dead end, but in the end the goal will be reached. Although this rule does have one drawback, which we will discuss later.
Let us try to describe a robot that acts according to the "right-hand rule".
At the start of its operation, the robot must find a wall to follow. To do this, it can simply move forward until it runs into an obstacle.
Once the robot has run into an obstacle, it begins moving according to the "right-hand rule".
While moving along the wall, the robot checks whether there is an opening on the right. If there is an opening, the robot must go through it so as not to lose contact with the wall on its right.
If there is no opening - there is a wall ahead - the robot turns left. If there is still no opening, it turns left once more, thereby turning 180 degrees, and heads in the opposite direction.
The flowchart of the algorithm for a robot working by the "right-hand rule" is shown in the figure.
Fig. Flowchart of the algorithm for a robot working according to the rule
Let us try to test how this algorithm works and write a program for it. For this purpose we will turn to the GameLogo programming environment. This environment is a convenient tool for modeling various algorithms related to robot control. It has a turtle executor, which is, in essence, nothing other than a genuine robot. The turtle has a very convenient set of commands - forward, right, left, back. In addition, at the center of the turtle there is a sensor that takes on a value from 0 to 100, depending on the shade of the surface it is on.
Dialect of the Logo language, which we will use, is very simple and resembles Basic. You can learn about the language's commands here. And you can download the GameLogo programming environment for free here. The distribution is not large - only 1 Mb.
The GameLogo archive contains maze backgrounds, one of which we will use.
File maze1.gif
the flag variableAt the very beginning of the program, let us give the turtle a command to raise its pen (by default the turtle leaves a trail behind it).
The field size is 800 by 600 points. The turtle's starting position is at the point with coordinates 115, 545 (the white square).
The color of the maze paths is light, and on them the sensor will read values greater than 50. The color of the maze walls is dark, and the sensor value there will be less than 50. The exit from the maze is represented by a black square, above which the sensor value will be equal to 0.
Let us declare the flag variable, which we will use to keep track of whether the exit from the maze has been reached.
Let us write the program and run it using the big red button labeled "Run".
background = maze1.gif
raise pen
place 115, 545
' search for the first wall
repeat while sensor > 50 {
forward 12
}
' right-hand rule
repeat while flag = 0 {
right 90
forward 12
if sensor = 0 then
flag = 1
else
if sensor < 50 then
back 12
left 90
forward 12
if sensor < 50 then
back 12
left 90
end if
end if
end if
}
write "goal reached"
If it is known that the maze has no free-standing walls, that is, no closed routes by which one could return to the starting point, then such a maze is called simply connected, and it can always be traversed completely by applying the "one-hand rule".
If, however, the maze contains free-standing walls, then applying the "one-hand rule" will not always let you pass through all the corridors and dead ends. Mazes with free-standing walls and closed routes are called multiply connected. Multiply connected mazes can, moreover, be divided into two groups: those without a "loop" around the goal (the closed route does not pass around the goal) and those with a closed "loop" around the goal (the goal can be circled along a closed route).
Robot for maze traversal based on the ATmega8
(Micromouse competition).
Knowing the Trémaux algorithm, one can refine the behavior of the legendary Theseus. Inspired by a gift from his beloved Ariadne, he confidently makes his way through the maze. Suddenly a passage appears ahead of him along which the thread has already been laid... What should he do? Under no circumstances cross it; instead, he should go back along the already-known path, doubling the thread, until he finds another untraveled passage. In multiply connected mazes of the second group, the "one-hand rule" does not work, and applying it makes it impossible to reach the goal. But these mazes, too, can be traversed by relying on an exact algorithm.
The solution to the problem of such mazes belongs to a comparatively late period, and it was begun by Leonhard Euler. Euler had good reason to believe that the way out of any maze could be found, and by a comparatively simple method at that.
A universal algorithm for traversing any maze was described only a century later, in a book by the French mathematician É. Lucas, "Récréations mathématiques", published in 1882. Interestingly, in describing the algorithm Lucas pointed to the priority of another French mathematician, M. Trémaux. Thus the algorithm became known as the Lucas-Trémaux algorithm.
Trémaux proposes the following rules: starting from any point of the maze, one should make a mark on its wall (a cross) and move in an arbitrary direction until reaching a dead end or an intersection; in the first case, go back, place a second cross indicating that the path has been traversed twice - there and back - and head in a direction not yet traveled at all, or traveled only once; in the second case, go in an arbitrary direction, marking each intersection with one cross both on entry and on exit; if an intersection already has one cross, a new path should be taken; if not, then the already-traveled path should be taken, marking it with a second cross.
Claude Shannon (Claude Elwood Shannon)
Applying a variant of the Trémaux algorithm, the father of information theory Claude Shannon (Claude Elwood Shannon) built one of the first self-learning robots. Shannon gave it the resounding name "Theseus", but in history "Theseus" became better known as Shannon's "mouse". The "mouse" first explored the entire maze, and then (the second time) traversed the whole path significantly faster, avoiding sections that had been traversed twice.
A maze at the Micromouse competition.
Nowadays, robots that solve mazes take part in one of the most interesting competitions of thinking machines, held in several countries around the world. These competitions are collectively known as the Micromouse competition and, in terms of their technical innovations, rank among the leaders of robotics sport.
At the first Russian Robot Olympiad, a competition was held whose goal was to get through a special kind of maze: in the shortest possible time, moving through "open doors" in the walls, the robot had to make its way from the starting point to the finish. The robot could keep track of its movement using black lines marked on the floor of the maze.
[[b8727]]
Comments