基于Voronoi圖的機器人局部路徑規(guī)劃.pdf

1、路徑規(guī)劃是機器人學的一個重要課題，目前的研究主要分為全局路徑規(guī)劃和局部路徑規(guī)劃。傳統(tǒng)的基于Voronoi圖的路徑規(guī)劃主要用于全局路徑規(guī)劃，它屬于基于構型空間幾何構造的方法。本文主要研究了基于Voronoi圖的局部路徑規(guī)劃，它利用傳感器的信息，采用增量式構造地圖的方法，使之適用于局部路徑規(guī)劃。 基于傳感器的路徑規(guī)劃方法中，早期研究較多的是被稱作啟發(fā)式的規(guī)劃方法，且局限于平面的情況下。然而，一直以來人們都不能證明這些方法一定能正確的

2、發(fā)現(xiàn)路徑，其完備性無法解決。而本文所研究的算法采用廣義Voronoi圖（GVD），機器人首先到達GVD的一個等距邊，接著跟蹤這條邊直到到達GVD的一個節(jié)點，然后分別遍歷經(jīng)過這個節(jié)點的邊。當所有節(jié)點都沒有未遍歷的方向時，算法結束。這個結束條件使得本文的方法不同于傳統(tǒng)的基于傳感器的路徑規(guī)劃方法之處在于：它是完備的。 此外，本文的增量式構造方法擴展到用于三維空間，此時地圖的基本構成為三維空間中的廣義Voronoi圖（GVG）。三維空間