人工智能3D打印完全遍歷路徑規劃技術研究★

李 榮 帥

(上海建工集團工程研究總院，上?！?01114)

?

·計算機技術及應用·

人工智能3D打印完全遍歷路徑規劃技術研究★

李 榮 帥

(上海建工集團工程研究總院，上海201114)

在系統總結3D打印技術、人工智能以及路徑規劃技術發展的基礎上，在建筑3D打印領域中提出進行打印頭完全遍歷路徑規劃研究，并分析了其必要性和緊迫性,同時，構建了打印頭完全遍歷路徑規劃的數學模型，提出了評價打印頭完全遍歷路徑規劃性能的評價指標，最后展望了通過人工智能算法進行建筑3D打印完全遍歷路徑規劃的研究方向。

3D打印，建筑，人工智能，完全遍歷，路徑規劃

0　引言

3D 打印(3D printing，又稱三維打印)是一種快速成形技術，它以數字化模型為基礎，運用可粘合材料，通過逐層打印的方式構造物體。目前，隨著技術的發展，3D打印技術相繼應用于很多行業，2010年開始，各國研究人員相繼在建筑3D打印領域開展了相關的研究和應用，取得了一定的成果，但是在建筑3D打印領域的研究和應用更多的是一種應用探索，而缺乏相關的系統研究。目前應用于建筑3D打印領域的3D打印裝置基本上均基于熔融沉積式(Fused Deposition Modeling，FDM)成形原理?；贔DM技術的建筑用3D打印裝置示意圖如圖1所示，俯視角度觀察，建筑3D打印機平面如圖2所示。

相對于一般的3D打印物品，建筑結構體量巨大，帶來的一個直接問題就是打印頭如何進行打印路徑規劃，以達到效率與精度的優化平衡。而對打印頭路徑規劃問題進行數學描述，建模，引入人工智能算法進行求解與優化就成了必須面對和解決的問題[1-4]。

1　遍歷路徑規劃及人工智能的發展

1.1人工智能的發展

人工智能(AI)是21世紀科技領域最為前沿的技術之一，是意圖通過了解智能的實質，進而生產出一種智能機器，而且使其能按照人的智能相類似的方式做出相應的反應，這一領域的研究主要有語言與圖像識別、自然語言的處理、智能機器人以及專家系統等。我們通常將人工智能劃分為三個階段，分別為計算智能、感知智能和認知智能。

圖1　建筑用3D打印機示意圖

圖2　建筑3D打印機平面示意圖

目前人工智能的發展還處于最初的計算智能階段,從廣義上講，計算智能就是通過借鑒基于生物體系的物種進化、免疫、神經網絡等某些生物體智能機制,而用數學語言將其進行抽象描述，進而形成的計算方法。其特點是不需要建立精確模型對問題本身進行描述。目前，發展比較迅速且被實踐證明比較有效的主要計算智能方法包括免疫算法、進化計算、進化神經網絡、模糊進化計算、DNA計算人工神經網絡等[17-20]。

1.2遍歷路徑規劃的發展

目前，在3D打印領域，打印頭路徑規劃技術一般還沿用數控切削加工中的路徑規劃方法。但是原有的數控加工技術是基于去除原理，而3D打印技術是基于離散堆積原理的快速成形技術，這兩者在理論上就有很大的不同，同時由于在建筑3D打印中，采用混凝土等非即時固化材料，導致建筑體或構件成形速度比較低，而且出料精度差，這樣的特點使得針對一些其他快速成形技術比較有效的路徑規劃技術并不適用于建筑3D打印。與此同時，先前研究[13-20]中都沒有針對建筑3D打印的特點給出路徑規劃技術完整的數學模型，也沒有給出路徑遍歷策略及簡化的定理和證明，將路徑間排序問題簡化為以路徑原始起點為單元的TSP，忽略了其他潛在起點對此問題的影響；所使用算法尋優能力和效率不高，對于大規模問題只能得到一般可行解[9-12]。

1.3建筑3D打印完全遍歷路徑規劃的核心問題

環境建模和路徑搜索是打印頭完全遍歷路徑規劃的核心問題。環境建模有三方面表示：1)可打印空間表示；2)目標表示；3)不可打印空間表示。在打印頭路徑規劃問題中，第一步需要解決的就是環境建模，因為每一種路徑規劃算法都是為了針對某一個環境建模而構建的，它們是一一對應的，所以環境建模方法的好壞直接影響到路徑規劃的策略和效率及其完成度。環境模型劃分為靜態模型和動態模型兩大類。靜態模型是固定模型，環境是固定不變的。動態模型是不斷變化的模型。靜態路徑規劃是目前研究的熱點，關于靜態已知環境的研究和建模技術研究較成熟，但是隨著科技的發展，動態的路徑規劃問題也引起越來越多人們的注意。在解決部分未知或者完全未知環境的路徑規劃問題方面存在一定的困難，這其中主要原因是因為難以建立有效的環境模型。合理的環境建模有利于減少規劃中的搜索量，提高打印效率[13-16]。

打印頭路徑規劃問題，關鍵就是要尋找一條安全路徑，來保證打印頭在指定的區域內從起始位置越過不可打印區域移動到目標位置。合理的通過設計環境模型、表達方法與數據結構來反映打印頭處于某一個位置時可能發生偏離可打印區域的概率，這樣構成了一個狀態空間。在此基礎上，建立各個子區域的連通回路，連通回路的構成主要依靠搜索功能，搜索完成后即在起點與終點間得到一條路徑，將通路上的各個節點全部在模型中表示出來，所構成的路徑就是打印頭的遍歷路徑[17-20]。

2　建筑3D打印中完全遍歷規劃的數學描述與評價指標

2.1數學描述

假設：V={x,y|x,y特定的點，打印頭移動范圍}。

定義1：路徑區間VΩ={x，y|ocup(x,y)=0}?V,其中，ocup(x,y)為占有函數，如下式所示。

定義2：不可達區域VΔ={x,y|ocup(x,y)=1}?V，顯然VΩ∩VΔ=0，且VΩ∪VΔ=1。

打印頭在移動過程中將其看成一個質點，質點運動就會形成連續的運動軌跡?？尚斜闅v軌跡是指打印頭移動過程產生的運動軌跡，在一個平面內可以產生多條路徑，該路徑均為可能路徑，這些路徑構成一個集合，稱之為遍歷軌跡，可以用下式表示:

首先，政府在宏觀層面的戰略部署能夠促進一國文化產業的蓬勃發展，甚至成為一國經濟的主要支撐點。以擁有相似文化底蘊的文化大國韓國為例，1998年韓政府出臺“文化立國”戰略，隨后又緊跟著出臺了一系列政策，使韓國影視文化行業迸發活力。時至今日，韓國影視劇出口值屢獲新高，文化產業成為國民經濟的支柱產業，真正做到了“文化強國”、“文化立國”。其次，國家文化企業實力強大離不開有力的文化監管。如今很多文化企業存在偷稅漏稅、抄襲、惡意競爭等問題，影視文化行業需要政府對法律的完善和對違法行為的嚴厲處罰，只有保證文化氛圍的文明和諧才能更好地進行文化產業體制改革。

L∑={li(x,y,xs,ys,xg,yg)}。

其中,(xs,ys),(xg,yg)分別為打印頭起點和終點坐標值，(x,y),(xs,ys),(xg,yg)?V。

2.2性能指標

打印頭遍歷區域的性能可以用路徑總長度、轉彎次數、遍歷重疊率、遍歷覆蓋率來衡量。假設用V,VΩ,Vhc以及Vcc依次表示打印頭的整個工作空間、可打印空間、已遍歷的面積和重復遍歷面積，可得到以下四個性能指標：

1)路徑總長度。

路徑總長度是指打印頭完成遍歷路徑規劃后，得出的打印頭移動距離。在統一換進地圖下，相同的遍歷完成率，路徑總長度越小，控制打印頭的算法越好。

2)轉彎次數。

轉彎次數是指打印頭在移動過程中運動方向發生改變的次數，通常打印頭在運動過程中，轉彎次數越少，越能說明控制打印頭的算法越好。

3)遍歷完成率。

遍歷完成率指在進行規劃路徑時，打印頭所走過路徑的覆蓋面積和全部可能到達面積的比例，最后表示結果是一個百分比，具體如下式所示：

Dhc=Vhc/VΩ。

遍歷完成率表示了打印頭完成任務的百分比，百分比越高，越能說明該算法的優秀。

4)遍歷重疊率。

在路徑規劃時，打印頭所有的遍歷中出現的重疊面積總和與可達區域面積的比值，如下式所示：

Dcc=Vcc/VΩ。

遍歷相鄰區域時，盡量要將整個區域遍歷完全，但是不可避免的在遍歷過程中可能會存在一定的交叉。從算法的角度講，交叉的區域應盡可能小，此時打印頭性能會比較高。但是打印頭本身就存在一定的系統誤差和定位誤差，遍歷重疊的區域不會像理想的那么小。此外，根據該比例還可計算出沒有被遍歷過的面積所占有的百分比，可以表示成：

Duc=1-Dhc。

該比例是指打印頭沒有遍歷過的面積所占總的可以到達的面積的比例。打印頭性能越高，其各項指標會越優。

上述給出了打印頭完全遍歷路徑規劃的性能評價指標，可以根據這個指標來評判一個算法的優越程度。

3　結論與展望

在目前3D打印技術、人工智能技術及路徑規劃技術都取得了長足發展的情況下，針對建筑結構體量巨大，打印效率與精度的矛盾愈發突出，有必要開展基于人工智能的建筑3D打印完全遍歷路徑規劃技術研究，通過研究，取得大體量建筑直接進行3D打印的效率與精度的優化平衡。未來，本方面的主要研究方向包括：

1)建立建筑3D打印路徑規劃技術的環境模型，針對靜態環境模型和動態環境模型的不同開展相應的對比研究。

2)開展人工智能算法在建筑3D打印完全遍歷路徑規劃領域的性能對比研究，選擇出一種或幾種性能相對較好的人工智能算法。

3)開展基于人工智能的建筑3D打印完全遍歷路徑規劃技術數值模擬研究，檢驗選定的人工智能算法在設定的環境模型中的適應性及性能。

4)進行實驗研究，在實際的建筑3D打印裝置中運用人工智能控制打印頭的移動路徑，對算法的性能進行實際驗證。

另外，鑒于建筑3D打印實際是在三維空間下進行的，所以后續應在實現二維空間下基于人工智能的建筑3D打印完全遍歷路徑規劃后，后續還應開展在三維空間下的遍歷路徑規劃技術研究工作。

[1]焦陽.基于模糊PID算法的3D打印后處理系統[J].電子制作,2014(20):44-45.

[2]朱博,鄧三鵬,王英飛,等.基于生物激勵神經網絡的移動機器人遍歷路徑規劃[J].裝備制造技術,2014(12):30-32.

[3]史玉升,張李超,白宇,等.3D打印技術的發展及其軟件實現[J].中國科學:信息科學,2015(2):197-203.

[4]羅楠,王泉,劉紅霞.一種快速3D打印分層方向確定算法[J].西安交通大學學報,2015(5):140-146.

[5]胡瑞珍,黃惠.3D打印啟發下的模型實例化優化研究綜述[J].計算機輔助設計與圖形學學報,2015(6):961-967.

[6]劉利剛,徐文鵬,王偉明,等.3D打印中的幾何計算研究進展[J].計算機學報,2015(6):1243-1267.

[7]張淑華.裸眼3D打印中光強矢量化處理算法研究[J].科學技術與工程,2013(30):9083-9088.

[8]王妹婷,齊永鋒,陸柳延,等.雙向清洗機器人玻璃幕墻完全遍歷路徑規劃[J].機械設計與制造,2013(11):211-213.

[9]李旭東.從仿真看3D打印及其若干問題[J].工業技術創新,2014(1):5-18.

[10]魏瀟然,耿國華,張雨禾.3D打印中的模型去支撐劃分方法[J].西安電子科技大學學報,2016(2):180-185.

[11]田春穎,劉瑜,馮申坤,等.基于柵格地圖的移動機器人完全遍歷算法——矩形分解法[J].機械工程學報,2004(10):56-61.

[12]楊竹豐,張赤斌,顏肖龍.基于標點定位的清掃機器人遍歷算法研究[J].電子機械工程,2006(1):59-61.

[13]邱雪娜,劉士榮,宋加濤,等.不確定動態環境下移動機器人的完全遍歷路徑規劃[J].機器人,2006(6):586-592.

[14]邱雪娜,劉士榮,俞金壽,等.移動機器人的完全遍歷路徑規劃:生物激勵與啟發式模板方法[J].模式識別與人工智能,2006(1):122-128.

[15]張赤斌,王興松.基于蟻群算法的完全遍歷路徑規劃研究[J].中國機械工程,2008(16):1945-1949.

[16]劉奎,張赤斌,易紅.在未知環境下完全遍歷算法——等單元分解法[J].系統仿真技術,2005(3):136-140.

[17]劉星,張雪峰,蔡勇,等.改進遺傳算法求解焊位群完全遍歷[J].機械與電子,2011(3):24-26.

[18]李開生,張慧慧,費仁元,等.具有遍歷特性的移動機器人規劃方法的研究[J].機器人,2001(6):486-492.

[19]郭小勤.未知環境下移動機器人遍歷路徑規劃[J].計算機工程與設計,2010(1):172-174，202.

[20]李一波,張慶濤.室內未知環境遍歷路徑規劃算法綜述[J].計算機科學,2012(S3):334-338.

Research of complete coverage path planning of building 3D printing based on artificial intelligence★

Li Rongshuai

(EngineeringGeneralInstituteofShanghaiConstructionGroup,Shanghai201114，China)

Based on the system summary of 3D printing technology, artificial intelligence and development on the basis of path planning technology, research of complete coverage path planning of print head is firstly put forward in the field of building 3D printing, the necessity and urgency is analyzed. At the same time, build the mathematical model of the print head complete coverage path planning, put forward the evaluation of the print head complete coverage path planning performance evaluation indexes, finally, research direction of complete coverage path planning of building 3D printing based on artificial intelligent algorithm is prospected.

3D printing， building， artificial intelligence， complete coverage， path planning

1009-6825(2016)21-0256-03

2016-05-18★:上海市浦江人才計劃資助(項目編號：15PJ1434200)

李榮帥(1983- )，男，博士，高級工程師

TP319

A