8.e. Simplifying the Solution (Pololu 3pi Robot User’s Guide) 日本語訳【非公式】

これは Pololu 3pi Robot User’s Guide ≫ 8.e. Simplifying the Solution の非公式日本語訳です。
目次
前： 8.d. The Main Loop(s)
次： 8.f. Improving the Maze-Solving Code

8.e. Simplifying the Solution

After every turn, the length of the recorded path increases by 1. If your maze, for example, has a long zigzag passageway with no side exits, you’ll see a sequence like ‘RLRLRLRL’ appear on the 3pi’s LCD. There’s no shortcut that would get you through this section of the path faster than just following the left hand on the wall strategy. However, whenever we encounter a dead end, we can simplify the path to something shorter.

曲がるたびに、記録された経路の長さは1ずつ増えます。例えば、ジグザグで脇道のない長い経路がある場合は、3piのLCDに "RLRLRLRL" のようなシーケンスが表示されます。There’s no shortcut that would get you through this section of the path faster than just following the left hand on the wall strategy. しかしながら、行き止まりに遭遇するときはいつでも、経路をいくらか短く単純化することができます。

Consider the sequence ‘LBL’, where ‘B’ stands for “back” and is the action taken when a dead end is encountered. This is what happens if there is a left turn that branches off of a straight path and leads immediately to a dead end. After turning 90° left, 180°, and 90° left again, the net effect is that the robot is heading in its original direction again. The path can be simplified to a 0° turn: a single ‘S’. The following diagram depicts this scenario, showing the two functionally equivalent paths from start to end:

"LBL"というシーケンスを考えます。ここで"B"は"back"を意味し、行き止まりに遭遇したときのアクションです。まっすぐな道から分岐してすぐ行き止まりになる左折がある場合、これは起こります。左に90°、180°、再び左に90°旋回した後の最終的な結果は、ロボットが再び元の方向に向かっていることです。この経路は0°の回転、つまり1つの"S"に単純化することができます。次の図はこのシナリオを描いており、スタートからゴールまでの機能的に等価な2つのパスを示しています。

Another example is a T-intersection with a dead end on the left: ‘LBS’. The turns are 90° left, 180°, and 0°, for a total of 90° right. The sequence should be replaced with a single ‘R’.

別の例は、左側に行き止まりがある丁字路："LBS"です。旋回は左に90°、180°、0°であり、合計で右に90°です。シーケンスは1つの"R"に置き換わるはずです。

In fact, whenever we have a sequence like ‘xBx’, we can replace all three turns with a turn corresponding to the total angle, eliminating the U-turn and speeding up our solution. Here’s the code to handle this:

実のところ、"xBx"のようなシーケンスあるときは、3つの旋回すべてを、角度の合計に対応する1つの旋回に置き換えることができ、Uターンを排除して解く速度を上げることができます。これを処理するコードはこちらです：

// Path simplification.  The strategy is that whenever we encounter a
// sequence xBx, we can simplify it by cutting out the dead end.  For
// example, LBL -> S, because a single S bypasses the dead end
// represented by LBL.
void simplify_path()
{
    // only simplify the path if the second-to-last turn was a 'B'
    if(path_length < 3 || path[path_length-2] != 'B')
        return;

    int total_angle = 0;
    int i;
    for(i=1;i<=3;i++)
    {
        switch(path[path_length-i])
        {
        case 'R':
            total_angle += 90;
            break;
        case 'L':
            total_angle += 270;
            break;
        case 'B':
            total_angle += 180;
            break;
        }
    }

    // Get the angle as a number between 0 and 360 degrees.
    total_angle = total_angle % 360;

    // Replace all of those turns with a single one.
    switch(total_angle)
    {
    case 0:
        path[path_length - 3] = 'S';
        break;
    case 90:
        path[path_length - 3] = 'R';
        break;
    case 180:
        path[path_length - 3] = 'B';
        break;
    case 270:
        path[path_length - 3] = 'L';
        break;
    }

    // The path is now two steps shorter.
    path_length -= 2;
}

One interesting point about this code is that there are some sequences that should never be encountered by a left-turning robot, like ‘RBR’, which would be replaced by ‘S’ according to this code. In a more advanced program, you might want to keep track of inconsistencies like this, since they indicate some kind of a problem that could cause the robot to get lost.

このコードに関する興味深い点は、"RBR"のように左手法で動くロボットが決して遭遇してはいけないシーケンスがいくつかあることです。このコードに従うと、これは"S"に置き換えられます。ロボットが道に迷いかねないという、ある種の問題を示しているため、より高度なプログラムでは、このような矛盾を記録したいかもしれません。

Now let’s step through a slightly more complicated maze, showing how we can simplify the path as we explore it:

次に、もう少し複雑な迷路を使って、探索しながら経路を単純化する方法を説明します。

Fully explore the maze using a left-hand-on-the-wall strategy.

左手法を使用して迷路を完全に調査してください。

The above list of actions is a record of all the steps we took to fully explore the maze while looking for the end, which is marked by the large black circle. Our goal is to now reduce this list to represent the shortest path from start to finish by weeding out all of the dead ends. One option is to perform this pruning when we finish the maze, but the better approach is to perform the pruning as we go to keep our list from growing excessively large and taking up more memory than we have available.

上記のアクションリストは、大きな黒色の円でマークされたゴールを探しながら迷路を完全に探索するために行ったすべての手順の記録です。私たちの目標は、このリストを削減するために、すべての行き止まりを取り除いて、スタートからゴールまでの最短経路を表すことです。1つの選択肢は迷路を終えたときにこの枝刈りを実行することですが、より良いアプローチは、リストが過度に大きくなって使用可能なメモリを超えないようにリストを保つために、処理が進むごとに枝刈りを実行することです。

Prune out the first dead end as we identify it.

最初の行き止まりを確認しながら枝刈りします。

When we encounter the first intersection after our first “back” action, we know we have reached a dead end that can be removed from our list of actions. In this case, the most recent actions in our list is the sequence ‘SBL’, and the diagram shows that this sequence can be simplified into a single right turn ‘R’.

最初の"back"アクションの後に最初の交差点に遭遇したとき、アクションリストから取り除くことができる行き止まりに到達したことがわかります。この場合、リスト中の最も最近のアクションはシーケンス"SBL"であり、この図はこのシーケンスが1つの右折"R"に単純化できることを示しています。

Prune out the rest of this dead-end branch as we back-track.

来た道を引き返すように、残りの行き止まりのブランチを枝刈りします。

We next end up with the sequence ‘RBL’, which reduces to a single back ‘B’, and this combines with the next action to produce the sequence ‘LBL’, which reduces to a single straight ‘S’.

次に、シーケンス"RBL"は1つの戻る"B"に削減され、次のアクションと組み合わさってシーケンス"LBL"は1つの直進"S"に削減される結果になります。

Prune out the final dead-end branch to leave us with the shortest path from start to finish.

スタートからゴールまでの最短経路を残すために最後の行き止まりを枝刈りします。

The last dead end gives us the sequence ‘SBL’, which reduces to a sigle right turn ‘R’. Our action list is now just ‘R’ and represents the shortest path from start to finish.

最後の行き止まりはシーケンス"SBL"を1つの右折"R"に削減します。アクションリストはただ"R"だけとなり、始点から終点までの最短経路を表します。

As we drove the maze, our action list would have looked like the following:

迷路を走行したとき、アクションリストは以下のようになります：

1. L
2. LS
3. LSB
4. LSBL => LR (pruning occurs here)
5. LRB
6. LRBL => LB (pruning occurs here)
7. LBL => S (pruning occurs here)
8. SB
9. SBL => R (pruning occurs here)