3

私はロボット プロジェクト (SVG ファイルから生成されたいくつかのセンサーとマップを使用して自分自身をローカライズする「自律型」車) のフロント エンドに取り組んでいます。

ロボットを制御可能にするには、現在の位置と目標の間のパスを生成する必要があります。そのために最も簡単なアルゴリズムを使用しました：A *。

これを行うと、奇妙な結果が得られました。車は 45 度の倍数で進む傾向があり、特に厄介な問題が 1 つあります。

この場合、オレンジ色の四角形の近くにノイズの多いパスが表示されます。

生成されたパスの視覚化

これらの奇妙な/ノイズの多い結果を回避する方法はありますか? 最終的には、方向角の変更が最小限のパスを作成する必要があります。(車は移動せずに曲がることができるため、パスの「平滑化」は必要ありません)。

これが私の A* 実装です:

def search(self, begin, goal):
    if goal.x not in range(self.width) or goal.y not in range(self.height):
        print "Goal is out of bound"
        return []
    elif not self.grid[begin.y][begin.x].reachable:
        print "Beginning is unreachable"
        return []
    elif not self.grid[goal.y][goal.x].reachable:
        print "Goal is unreachable"
        return []
    else:

        self.cl = set()
        self.ol = set()

        curCell = begin
        self.ol.add(curCell)

        while len(self.ol) > 0:

            # We choose the cell in the open list having the minimum score as our current cell
            curCell = min(self.ol, key = lambda x : x.f)

            # We add the current cell to the closed list
            self.ol.remove(curCell)
            self.cl.add(curCell)

            # We check the cell's (reachable) neighbours :
            neighbours = self.neighbours(curCell)

            for cell in neighbours:
                # If the goal is a neighbour cell :
                if cell == goal:
                    cell.parent = curCell
                    self.path = cell.path()
                    self.display()
                    self.clear()
                    return self.path
                elif cell not in self.cl:
                    # We process the cells that are not in the closed list
                    # (processing <-> calculating the "F" score)
                    cell.process(curCell, goal)

                    self.ol.add(cell)

EDIT 1:一般的な要求により、スコア計算関数 (プロセス) は次のとおりです。

def process(self, parent, goal):
    self.parent = parent
    self.g = parent.distance(self)
    self.h = self.manhattanDistance(goal)
    self.f = self.g + self.h

編集これが隣人の方法です（user1884905の回答に従って更新されました）：

def neighbours(self, cell, radius = 1, unreachables = False, diagonal = True):
    neighbours = set()
    for i in xrange(-radius, radius + 1):
        for j in xrange(-radius, radius + 1):
            x = cell.x + j
            y = cell.y + i
            if 0 <= y < self.height and 0 <= x < self.width and ( self.grid[y][x].reachable or unreachables ) and (diagonal or (x == cell.x or y == cell.y)) :
                neighbours.add(self.grid[y][x])

    return neighbours

(これは複雑に見えますが、セルの 8 つの隣接要素 (対角線の隣接要素を含む) を提供するだけです。他の機能に使用されるため、1 以外の半径を取ることもできます)

および距離の計算 (対角線を使用するかどうかに応じて:)

def manhattanDistance(self, cell):
    return abs(self.x - cell.x) + abs(self.y - cell.y)

def diagonalDistance(self, cell):

    xDist = abs(self.x - cell.x)
    yDist = abs(self.y - cell.y)

    if xDist > yDist:
        return 1.4 * yDist + (xDist - yDist)
    else:
        return 1.4 * xDist + (yDist - xDist)
4

2 に答える 2

4

ゴールに最も近い (カラスが飛ぶように) 検査されたセルにまだ入っていないセルに移動しているため、実装が正しくないようですが、見つけるために障害物を見つけるときにそれを試してパスを元に戻す必要があります最適なもの。アイデアを得るには、ウィキペディアでこの素敵なアニメーションを参照してください。

ここでの問題は、計算方法に関連しています。計算cell.fを行うときに現在のセルのスコアを追加していない可能性があります。一般に、A * はここで赤でマークされた手順を実行し、そのような最適でないパスを生成する必要があります。

空間は個別のセルに分割されているため、連続した世界の最適なパス (常にカラスが飛ぶように) が 2 つの個別の動きのちょうど中間にある場合、その奇妙なパスでできる限り最適に近似します。

ここには 2 つのアプローチがあります。

  1. 評価された各セルの正しい距離値を維持するアルゴリズム (ここでは疑似コード) を修正します (貼り付けられたセルには、計算方法に関する情報がありませんcell.f)。
  2. Djikstraを使用すると、現在のアルゴリズムを少し変更するだけで簡単に実装できるはずです。実際、A* はその最適化されたバージョンにすぎません。
于 2013-03-19T11:14:35.847 に答える
3

neighbourおよび関数をどのように実装したかを確認できなくてもdistance、何が問題なのかについてはまだ推測できます。

斜めのトラバーサルを許可する場合は、マンハッタン距離を使用しないでください。

ゴール関数のマンハッタン距離は、ゴールまでの最短距離の尺度でなければなりません。（積み木を斜めに通り抜けることができれば、そうではありません。）

これを修正する最も簡単な方法は、マンハッタン距離を目標関数として維持し、隣接セルの定義を変更して、上下左右に隣接する 4 つのセルのみを含めることです。

編集

コードにはまだ問題があります。次の疑似コードは、wikipediaから取得したものです。チェックしなければならない重要な行をマークしました。i) より良い解決策が見つかった場合は、オープン セット内のノードを更新していること、および ii) 以前に移動した距離を常に考慮に入れていることを確認する必要があります。

function A*(start,goal)
     closedset := the empty set    // The set of nodes already evaluated.
     openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
     came_from := the empty map    // The map of navigated nodes.

     g_score[start] := 0    // Cost from start along best known path.
     // Estimated total cost from start to goal through y.
     f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

     while openset is not empty
         current := the node in openset having the lowest f_score[] value
         if current = goal
             return reconstruct_path(came_from, goal)

         remove current from openset
         add current to closedset
         for each neighbor in neighbor_nodes(current)
             // -------------------------------------------------------------------
             // This is the way the tentative_g_score should be calculated.
             // Do you include the current g_score in your calculation parent.distance(self) ?
             tentative_g_score := g_score[current] + dist_between(current,neighbor)
             // ------------------------------------------------------------------- 
             if neighbor in closedset
                 if tentative_g_score >= g_score[neighbor]
                     continue

             // -------------------------------------------------------------------
             // You never make this comparrison
             if neighbor not in openset or tentative_g_score < g_score[neighbor]
             // -------------------------------------------------------------------
                 came_from[neighbor] := current
                 g_score[neighbor] := tentative_g_score
                 f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                 if neighbor not in openset
                     add neighbor to openset

     return failure

 function reconstruct_path(came_from, current_node)
     if current_node in came_from
         p := reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node
于 2013-04-04T15:11:01.043 に答える