李 榮 帥

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

?

·計(jì)算機(jī)技術(shù)及應(yīng)用·

人工智能3D打印完全遍歷路徑規(guī)劃技術(shù)研究★

李 榮 帥

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

在系統(tǒng)總結(jié)3D打印技術(shù)、人工智能以及路徑規(guī)劃技術(shù)發(fā)展的基礎(chǔ)上，在建筑3D打印領(lǐng)域中提出進(jìn)行打印頭完全遍歷路徑規(guī)劃研究，并分析了其必要性和緊迫性,同時(shí)，構(gòu)建了打印頭完全遍歷路徑規(guī)劃的數(shù)學(xué)模型，提出了評(píng)價(jià)打印頭完全遍歷路徑規(guī)劃性能的評(píng)價(jià)指標(biāo)，最后展望了通過人工智能算法進(jìn)行建筑3D打印完全遍歷路徑規(guī)劃的研究方向。

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

0　引言

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

相對(duì)于一般的3D打印物品，建筑結(jié)構(gòu)體量巨大，帶來的一個(gè)直接問題就是打印頭如何進(jìn)行打印路徑規(guī)劃，以達(dá)到效率與精度的優(yōu)化平衡。而對(duì)打印頭路徑規(guī)劃問題進(jìn)行數(shù)學(xué)描述，建模，引入人工智能算法進(jìn)行求解與優(yōu)化就成了必須面對(duì)和解決的問題[1-4]。

1　遍歷路徑規(guī)劃及人工智能的發(fā)展

1.1人工智能的發(fā)展

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

圖1　建筑用3D打印機(jī)示意圖

圖2　建筑3D打印機(jī)平面示意圖

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

1.2遍歷路徑規(guī)劃的發(fā)展

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

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

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

打印頭路徑規(guī)劃問題，關(guān)鍵就是要尋找一條安全路徑，來保證打印頭在指定的區(qū)域內(nèi)從起始位置越過不可打印區(qū)域移動(dòng)到目標(biāo)位置。合理的通過設(shè)計(jì)環(huán)境模型、表達(dá)方法與數(shù)據(jù)結(jié)構(gòu)來反映打印頭處于某一個(gè)位置時(shí)可能發(fā)生偏離可打印區(qū)域的概率，這樣構(gòu)成了一個(gè)狀態(tài)空間。在此基礎(chǔ)上，建立各個(gè)子區(qū)域的連通回路，連通回路的構(gòu)成主要依靠搜索功能，搜索完成后即在起點(diǎn)與終點(diǎn)間得到一條路徑，將通路上的各個(gè)節(jié)點(diǎn)全部在模型中表示出來，所構(gòu)成的路徑就是打印頭的遍歷路徑[17-20]。

2　建筑3D打印中完全遍歷規(guī)劃的數(shù)學(xué)描述與評(píng)價(jià)指標(biāo)

2.1數(shù)學(xué)描述

假設(shè)：V={x,y|x,y特定的點(diǎn)，打印頭移動(dòng)范圍}。

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

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

打印頭在移動(dòng)過程中將其看成一個(gè)質(zhì)點(diǎn)，質(zhì)點(diǎn)運(yùn)動(dòng)就會(huì)形成連續(xù)的運(yùn)動(dòng)軌跡?？尚斜闅v軌跡是指打印頭移動(dòng)過程產(chǎn)生的運(yùn)動(dòng)軌跡，在一個(gè)平面內(nèi)可以產(chǎn)生多條路徑，該路徑均為可能路徑，這些路徑構(gòu)成一個(gè)集合，稱之為遍歷軌跡，可以用下式表示:

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

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

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

2.2性能指標(biāo)

打印頭遍歷區(qū)域的性能可以用路徑總長(zhǎng)度、轉(zhuǎn)彎次數(shù)、遍歷重疊率、遍歷覆蓋率來衡量。假設(shè)用V,VΩ,Vhc以及Vcc依次表示打印頭的整個(gè)工作空間、可打印空間、已遍歷的面積和重復(fù)遍歷面積，可得到以下四個(gè)性能指標(biāo)：

1)路徑總長(zhǎng)度。

路徑總長(zhǎng)度是指打印頭完成遍歷路徑規(guī)劃后，得出的打印頭移動(dòng)距離。在統(tǒng)一換進(jìn)地圖下，相同的遍歷完成率，路徑總長(zhǎng)度越小，控制打印頭的算法越好。

2)轉(zhuǎn)彎次數(shù)。

轉(zhuǎn)彎次數(shù)是指打印頭在移動(dòng)過程中運(yùn)動(dòng)方向發(fā)生改變的次數(shù)，通常打印頭在運(yùn)動(dòng)過程中，轉(zhuǎn)彎次數(shù)越少，越能說明控制打印頭的算法越好。

3)遍歷完成率。

遍歷完成率指在進(jìn)行規(guī)劃路徑時(shí)，打印頭所走過路徑的覆蓋面積和全部可能到達(dá)面積的比例，最后表示結(jié)果是一個(gè)百分比，具體如下式所示：

Dhc=Vhc/VΩ。

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

4)遍歷重疊率。

在路徑規(guī)劃時(shí)，打印頭所有的遍歷中出現(xiàn)的重疊面積總和與可達(dá)區(qū)域面積的比值，如下式所示：

Dcc=Vcc/VΩ。

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

Duc=1-Dhc。

該比例是指打印頭沒有遍歷過的面積所占總的可以到達(dá)的面積的比例。打印頭性能越高，其各項(xiàng)指標(biāo)會(huì)越優(yōu)。

上述給出了打印頭完全遍歷路徑規(guī)劃的性能評(píng)價(jià)指標(biāo)，可以根據(jù)這個(gè)指標(biāo)來評(píng)判一個(gè)算法的優(yōu)越程度。

3　結(jié)論與展望

在目前3D打印技術(shù)、人工智能技術(shù)及路徑規(guī)劃技術(shù)都取得了長(zhǎng)足發(fā)展的情況下，針對(duì)建筑結(jié)構(gòu)體量巨大，打印效率與精度的矛盾愈發(fā)突出，有必要開展基于人工智能的建筑3D打印完全遍歷路徑規(guī)劃技術(shù)研究，通過研究，取得大體量建筑直接進(jìn)行3D打印的效率與精度的優(yōu)化平衡。未來，本方面的主要研究方向包括：

1)建立建筑3D打印路徑規(guī)劃技術(shù)的環(huán)境模型，針對(duì)靜態(tài)環(huán)境模型和動(dòng)態(tài)環(huán)境模型的不同開展相應(yīng)的對(duì)比研究。

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

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

4)進(jìn)行實(shí)驗(yàn)研究，在實(shí)際的建筑3D打印裝置中運(yùn)用人工智能控制打印頭的移動(dòng)路徑，對(duì)算法的性能進(jìn)行實(shí)際驗(yàn)證。

另外，鑒于建筑3D打印實(shí)際是在三維空間下進(jìn)行的，所以后續(xù)應(yīng)在實(shí)現(xiàn)二維空間下基于人工智能的建筑3D打印完全遍歷路徑規(guī)劃后，后續(xù)還應(yīng)開展在三維空間下的遍歷路徑規(guī)劃技術(shù)研究工作。

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

[2]朱博,鄧三鵬,王英飛,等.基于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)的移動(dòng)機(jī)器人遍歷路徑規(guī)劃[J].裝備制造技術(shù),2014(12):30-32.

[3]史玉升,張李超,白宇,等.3D打印技術(shù)的發(fā)展及其軟件實(shí)現(xiàn)[J].中國(guó)科學(xué):信息科學(xué),2015(2):197-203.

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

[5]胡瑞珍,黃惠.3D打印啟發(fā)下的模型實(shí)例化優(yōu)化研究綜述[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2015(6):961-967.

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

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

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

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

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

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

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

[13]邱雪娜,劉士榮,宋加濤,等.不確定動(dòng)態(tài)環(huán)境下移動(dòng)機(jī)器人的完全遍歷路徑規(guī)劃[J].機(jī)器人,2006(6):586-592.

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

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

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

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

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

[19]郭小勤.未知環(huán)境下移動(dòng)機(jī)器人遍歷路徑規(guī)劃[J].計(jì)算機(jī)工程與設(shè)計(jì),2010(1):172-174，202.

[20]李一波,張慶濤.室內(nèi)未知環(huán)境遍歷路徑規(guī)劃算法綜述[J].計(jì)算機(jī)科學(xué),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★:上海市浦江人才計(jì)劃資助(項(xiàng)目編號(hào)：15PJ1434200)

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

TP319

A