计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2009年
31期
245-248
,共4页
全区域覆盖路径规划%遗传算法%矩形分解法%模板算法
全區域覆蓋路徑規劃%遺傳算法%矩形分解法%模闆算法
전구역복개로경규화%유전산법%구형분해법%모판산법
complete coverage path planning%Genetic Algorithms(GA)%rectangular decomposition method%template algorithm
全区域覆盖是一种特殊的路径规划,要求遍历环境中所有的可达区域.目前已经提的许多算法,如模板算法、分块算法等,都只能保证覆盖所有的区域,对于寻找全局最优解却无能为力.提出了一种基于遗传算法的全区域覆盖算法,结合分决算法和模板算法的优点.先采用矩形分解法将环境划分成若干个相邻的子模块,并为每一个子模块选用相应的模板,从而生成覆盖路径,然后采用遗传算法找出最优的路径.算法在虚拟环境中进行了实验,实验结果证明了其可行性和有效性.
全區域覆蓋是一種特殊的路徑規劃,要求遍歷環境中所有的可達區域.目前已經提的許多算法,如模闆算法、分塊算法等,都隻能保證覆蓋所有的區域,對于尋找全跼最優解卻無能為力.提齣瞭一種基于遺傳算法的全區域覆蓋算法,結閤分決算法和模闆算法的優點.先採用矩形分解法將環境劃分成若榦箇相鄰的子模塊,併為每一箇子模塊選用相應的模闆,從而生成覆蓋路徑,然後採用遺傳算法找齣最優的路徑.算法在虛擬環境中進行瞭實驗,實驗結果證明瞭其可行性和有效性.
전구역복개시일충특수적로경규화,요구편력배경중소유적가체구역.목전이경제적허다산법,여모판산법、분괴산법등,도지능보증복개소유적구역,대우심조전국최우해각무능위력.제출료일충기우유전산법적전구역복개산법,결합분결산법화모판산법적우점.선채용구형분해법장배경화분성약간개상린적자모괴,병위매일개자모괴선용상응적모판,종이생성복개로경,연후채용유전산법조출최우적로경.산법재허의배경중진행료실험,실험결과증명료기가행성화유효성.
A special kind of path planning is complete coverage path planning.There are a lot of algorithms on this problem have been developed,e.g.template based,cellular decomposition.But these algorithms just cover the complete area;they are not designed to optimize the process.This paper presents a method of complete coverage path planning based on genetic algorithms, which combine the advantages of cellular decomposition and template algorithm.The environment is divided in sub-regions as in rectangular decomposition method,and then Genetic Algorithms (GA) is used to compute and find the order of the sub-regions and the appropriate template for each region. The algorithm is tested in the virtual environment;the simulation results confirm the feasibility of this method.
