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

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

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