1
$\begingroup$

A robot starts at the origin pointing in some cardinal direction. Its only options are the following commands:

  • drive forward 1 unit F
  • turn left 90 degrees L
  • turn right 90 degrees R

The command list is a sequence of these letters e.g. "FRFL" is forward 1, right turn, forward 1, left turn.

I want to find if the robot will stay within some circular boundary or if it will diverge if you repeat a sequence of commands forever. For the above example, it will not be bounded by a circle because FRFL/FRFL/FRFL/FRFL.... results in a staircase-like path going to infinity.

In thinking about this problem, I figured that if I had the initial position and orientation and the final position and orientation after 1 set of commands, then I could extrapolate that by repeating the transformation.

My questions are:

-Is the final (x,y,direction) after one set of commands the only thing needed to solve this (in other words, is this "path independent?") If so, how would I prove that it is path independent or not?

-What would be the minimum number of repeated chunks to guarantee an answer? My intuition says "4" because there are only 4 possible orientations, but I'm not sure...

-If there are other, simpler ways to solve this problem.

$\endgroup$
2
$\begingroup$

The state of the robot can be encoded as $(z,r)$ where $z\in{\mathbb C}$ is a Gaussian integer and $r\in{\mathbb Z}_4$ indicates that the robot is pointing in direction $i^r$. The robot starts at $(z_0,r_0):=(0,0)$, and after one full period of commands is at some point $z_1=:w$ facing in direction $i^r$ for some $r\in{\mathbb Z}_4$. After the next full period of commands it is at $z_2=z_1+i^r w$ facing in direction $i^{2r}$, and so forth. It follows that after four periods of commands the robot is at $$z_4=z_0+(1+i^r+i^{2r}+i^{3r}) w\ .$$ If $r=0$ mod $4$ the robot has moved by $4w$ and again faces in direction $1$. If $w\ne0$ his orbit is therefore unbounded. If $r\ne0$ mod $4$ then $1+i^r+i^{2r}+i^{3r}=0$, hence $z_4=z_0$. This means that the robot cycles forever with a period at most equal to four times the length of the command sequence.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ To summarize: If the robot has changed position but is still pointing in the original direction, the path is unbounded. Otherwise, it is bounded. Nice and simple analysis (and I expect it still works even if the directions were not discretized into multiples of $\pi/2$). $\endgroup$ – user856 Nov 9 '17 at 21:18
  • $\begingroup$ This is a really good method; I didn't think to use complex numbers to describe this problem. $\endgroup$ – AAC Nov 16 '17 at 0:54
0
$\begingroup$

I think your intuition is right : because the angle is $90°$, there are only four possible "outcomes".

I would represent a basic chunk of instructions by a vector and a rotation. Any of the four rotations multiplied by $4$ is equivalent to a rotation of angle $0°$, so if you repeat your chunk four times, you will have a vector and a rotation $0°$. If the vector is $\overrightarrow 0$, then the trajectory is bounded. If not, the trajectory is unbounded.

Sometimes (if the resulting rotation is $0°$ or $180°$), you can form a conclusion by analyzing only the first or the first two repetitions. But it doesn't change the fact that repeating it four times gives the right result.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Each movement of the robot corresponds to an isometry of the entire plane that preserves orientation (that is, the robot's "right turn" and "left turn" directions do not get swapped). We apply the isometry and it moves the robot to a new configuration (position and direction in which it is pointing).

Any finite sequence of commands works out the same as the composition of the isometries for each step of the sequence. Exactly which isometry applies at each step depends on either the position or direction of the robot after the earlier steps, but the point is that there is some such isometry every time.

A finite sequence of commands is therefore itself an isometry. We can prove that this isometry is either a translation by some distance in some direction or a rotation around some point through an angle that is a multiple of $90$ degrees. Further, we can prove that if the isometry is a rotation, the next repetition of the sequence of commands will be a repetition of the same rotation through the same angle around the same center.

From this we can show that four repetitions of the sequence of commands will return the robot to its starting position and orientation, in which case the robot stays in a circle, or will not return the robot to its starting position, in which case the robot's path diverges.

Even better, however, by examining the outcome of just one repetition of a sequence of commands you can determine whether the robot's position will diverge or whether it will stay within a circular region when you repeat the sequence of commands indefinitely. You need only compare the starting configuration to the ending configuration, and check whether the robot's position changed and whether the direction the robot is pointing changed. I'll let you try to figure out in which cases the path diverges and in which cases it does not.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I can see that a composition of translation and rotation is also a rotation by drawing it out (I can always draw some lever arm that I can rotate to get the final configuration from the starting configuration), but how would I prove this? In this case any rotation or composition of rotation and translation after a sequence of commands will end up as a bounded path after repeating it forever, but if it is pure translation I will get divergence. $\endgroup$ – AAC Nov 16 '17 at 0:33
  • $\begingroup$ Interesting. I'll try to get back to this, because it's a well-known fact but it was also asked in math.stackexchange.com/questions/1573018/… and math.stackexchange.com/questions/1113692/… and never answered either time. $\endgroup$ – David K Nov 16 '17 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.