基于聚類(lèi)分區(qū)和改進(jìn)蟻群算法的清潔機(jī)器人路徑規(guī)劃研究.pdf

1、智能清潔機(jī)器人融合了多項(xiàng)人工智能技術(shù)，廣泛地應(yīng)用于家庭、公共場(chǎng)所、寫(xiě)字樓等環(huán)境的半自動(dòng)或自動(dòng)清潔。全局路徑規(guī)劃是智能清潔機(jī)器人中最重要的技術(shù)之一，在一定程度上標(biāo)志著智能清潔機(jī)器人智能化水平。全局路徑規(guī)劃要求清潔機(jī)器人在已知環(huán)境信息的情況下，以最小的代價(jià)（如路徑最短、時(shí)間最少、能耗最低等）規(guī)劃一條覆蓋全局且不與障礙物發(fā)生碰撞的最優(yōu)或較優(yōu)路徑。蟻群算法作為一種常用的路徑優(yōu)化算法，具有原理簡(jiǎn)單且實(shí)現(xiàn)容易等優(yōu)點(diǎn)，已經(jīng)有許多研究者將其用于解決智能

2、清潔機(jī)器人路徑規(guī)劃問(wèn)題。使用蟻群算法來(lái)解決清潔機(jī)器人路徑規(guī)劃問(wèn)題時(shí)，蟻群算法具有容易收斂到局部最優(yōu)解和解決大規(guī)模問(wèn)題時(shí)效率低下的缺點(diǎn)。本文基于聚類(lèi)分區(qū)和改進(jìn)蟻群算法進(jìn)行了清潔機(jī)器人路徑規(guī)劃研究，主要工作如下：
　　首先利用柵格法對(duì)清潔機(jī)器人工作的環(huán)境進(jìn)行建模，然后考慮到路徑優(yōu)化算法在面對(duì)凹形障礙物容易陷入局部最優(yōu)解的缺點(diǎn)，對(duì)已知的柵格地圖上的障礙物使用數(shù)字圖像處理里面的腐蝕（Erosion）、膨脹（Dilation）進(jìn)行預(yù)處理，使

3、得凹形障礙物變成矩形障礙物，從而避免蟻群算法陷入局部最小解。
　　其次，針對(duì)優(yōu)化算法在解決大規(guī)模路徑優(yōu)化問(wèn)題時(shí)效率低下的問(wèn)題，提出了將柵格地圖分區(qū)，然后分布地對(duì)柵格區(qū)域使用蟻群算法進(jìn)行路徑規(guī)劃的方法。本文使用K-Means聚類(lèi)算法和支持向量機(jī)（svm）相結(jié)合的方法，以不同的約束條件進(jìn)行聚類(lèi)，使得柵格地圖被縱向地分割成幾個(gè)區(qū)域，然后再利用蟻群算法對(duì)分割完成的柵格區(qū)域進(jìn)行路徑尋優(yōu)，使得蟻群算法總的效率大幅提高。
　　最后，針對(duì)蟻

4、群算法本身求解全局路徑規(guī)劃問(wèn)題時(shí)，具有易于收斂到局部最優(yōu)解和解決大規(guī)劃對(duì)稱(chēng)環(huán)境問(wèn)題時(shí)效率低下的缺點(diǎn)，提出了一種改進(jìn)的蟻群算法。該算法在采用偽隨機(jī)比例規(guī)則選擇路徑的基礎(chǔ)上，采用了局部信息素更新和全局信息素更新相結(jié)合的更新策略；在局部搜索方式上采用4-opt（4-optimization）方法進(jìn)行局部搜索；使得算法的全局搜索能力和效率都得到了提高。針對(duì)使用本文方法解決路徑規(guī)劃問(wèn)題時(shí)，出現(xiàn)的路徑穿過(guò)障礙物的現(xiàn)象，采用LB（Liang-Bars