改進(jìn)A*算法的移動(dòng)機(jī)器人路徑規(guī)劃設(shè)計(jì)

申 瑞，劉 佳，2，王夢(mèng)園，張運(yùn)喜，2

（1.天津職業(yè)技術(shù)師范大學(xué)自動(dòng)化與電氣工程學(xué)院，天津3 00222；2.天津市信息傳感與智能控制重點(diǎn)實(shí)驗(yàn)室，天津 300222）

近年來(lái)，隨著人工智能技術(shù)的快速發(fā)展，移動(dòng)機(jī)器人產(chǎn)業(yè)邁向了一個(gè)新的高度，由原來(lái)的單一化、機(jī)械化的發(fā)展模式逐漸轉(zhuǎn)變?yōu)槎嘣?、智能化的發(fā)展體系。人工智能被廣泛應(yīng)用于工業(yè)生產(chǎn)、物流傳送、醫(yī)療衛(wèi)生等眾多領(lǐng)域中，給人類的生產(chǎn)生活方式帶來(lái)了翻天覆地的變化。其中，移動(dòng)機(jī)器人的路徑規(guī)劃作為移動(dòng)機(jī)器人智能導(dǎo)航的關(guān)鍵技術(shù)，是當(dāng)前研究的一個(gè)熱點(diǎn)與難點(diǎn)問(wèn)題。路徑規(guī)劃是指移動(dòng)機(jī)器人按照某種性能指標(biāo)在有障礙物的環(huán)境里從起點(diǎn)至終點(diǎn)間找到一條最短或最佳的安全無(wú)碰撞路徑[1]。根據(jù)移動(dòng)機(jī)器人對(duì)外界環(huán)境信息的感知情況與應(yīng)用的場(chǎng)景不同，可以將路徑規(guī)劃劃分為靜態(tài)全局路徑規(guī)劃和動(dòng)態(tài)局部路徑規(guī)劃。全局路徑規(guī)劃[2]是指移動(dòng)機(jī)器人在已知整個(gè)靜態(tài)工作環(huán)境信息的情況下，通過(guò)搭建外界環(huán)境模型，得到一條從起點(diǎn)到終點(diǎn)的最優(yōu)路徑。隨著機(jī)器人技術(shù)的發(fā)展，全局路徑規(guī)劃算法日趨成熟，普遍使用的算法有A*算法[3]、柵格法[4]、快速隨機(jī)搜索樹(shù)算法[5]等；局部路徑規(guī)劃[2]是指在未知?jiǎng)討B(tài)環(huán)境的情況下，通過(guò)移動(dòng)機(jī)器人的傳感器、雷達(dá)等來(lái)實(shí)時(shí)感應(yīng)周邊環(huán)境，自主探索出一條從起點(diǎn)到終點(diǎn)的最優(yōu)路徑。目前常用的局部路徑規(guī)劃算法有人工勢(shì)場(chǎng)法[6]、動(dòng)態(tài)窗口法DWA[7]等。

A*算法是在Dijkstra算法與最佳優(yōu)先算法（breadth first search，BFS）的基礎(chǔ)上，兼顧搜索效率與最優(yōu)路徑的一種啟發(fā)式搜索算法[8]。A*算法常被用于全局路徑規(guī)劃，但也存在計(jì)算效率低、冗余點(diǎn)和拐點(diǎn)、路徑不平滑等問(wèn)題[9]。針對(duì)上述問(wèn)題，研究人員從多個(gè)角度對(duì)A*算法進(jìn)行改善。王紅衛(wèi)等[10]針對(duì)A*算法轉(zhuǎn)折次數(shù)過(guò)多，提出在前后節(jié)點(diǎn)的連線上沒(méi)有障礙物時(shí)，將中間節(jié)點(diǎn)刪除，從而優(yōu)化了路徑平滑度，但是計(jì)算效率并沒(méi)有提高。高慶吉等[11]針對(duì)A*算法路徑搜索效率問(wèn)題，引入“人工搜索標(biāo)志”，減少了無(wú)用區(qū)間的搜索，提高了搜索效率。吳鵬等[12]采用雙向A*搜索策略，分別在起點(diǎn)和終點(diǎn)進(jìn)行搜索，2條路徑匯于中間區(qū)域，得到一條完整的搜索路徑，提高了路徑的搜索效率，但獲得的路徑不一定是最優(yōu)路徑。文獻(xiàn)[13]針對(duì)規(guī)劃路徑對(duì)移動(dòng)機(jī)器人的安全性增加了子節(jié)點(diǎn)的選擇規(guī)則，從而避免移動(dòng)機(jī)器人斜穿障礙物頂點(diǎn)，減少碰撞風(fēng)險(xiǎn)，但增加路徑的長(zhǎng)度，無(wú)法獲得最優(yōu)路徑?；谏鲜銮叭说难芯浚疚尼槍?duì)傳統(tǒng)A*算法存在的問(wèn)題，設(shè)計(jì)一種基于A*算法改進(jìn)的有效路徑規(guī)劃算法，旨在提高搜索效率的同時(shí)兼顧路徑的最優(yōu)化。

1 經(jīng)典A*算法

1.1 環(huán)境模型的建立

一般在進(jìn)行路徑規(guī)劃之前，首先需要構(gòu)建環(huán)境地圖模擬障礙物空間來(lái)表達(dá)環(huán)境信息的復(fù)雜程度，再使用A*算法進(jìn)行全局路徑規(guī)劃。依據(jù)地圖的種類，可以分為柵格圖、拓?fù)鋱D、可視圖[14]等。柵格地圖是指用相同尺寸的柵格將環(huán)境地圖進(jìn)行劃分，柵格地圖編程簡(jiǎn)單且能有效地表達(dá)2D靜態(tài)環(huán)境中的障礙物信息，所以本文在進(jìn)行路徑規(guī)劃仿真時(shí)采用柵格法構(gòu)建環(huán)境地圖。

1.2 傳統(tǒng)A*算法

A*算法是在靜態(tài)環(huán)境中兼顧搜索效率與最優(yōu)路徑的一種啟發(fā)式搜索算法。A*算法在搜索路徑中，是以計(jì)算相關(guān)節(jié)點(diǎn)的評(píng)價(jià)函數(shù)[15]為核心，從而確定運(yùn)動(dòng)方向與引導(dǎo)路徑的產(chǎn)生。起點(diǎn)作為第1個(gè)父節(jié)點(diǎn)入OPEN列表中，計(jì)算周圍8個(gè)節(jié)點(diǎn)的評(píng)價(jià)函數(shù)，選取最小評(píng)價(jià)函數(shù)值所對(duì)應(yīng)的節(jié)點(diǎn)作為下一個(gè)父節(jié)點(diǎn)，同時(shí)將起點(diǎn)放入CLOSE列表中，使用新的父節(jié)點(diǎn)再計(jì)算周圍節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值，不斷更新OPEN、CLOSE列表。從起點(diǎn)開(kāi)始選取評(píng)價(jià)函數(shù)最小值所對(duì)應(yīng)的節(jié)點(diǎn)，不斷迭代直到終點(diǎn)結(jié)束[16]。將這些選取的節(jié)點(diǎn)從終點(diǎn)依次連接到起點(diǎn)，構(gòu)成整個(gè)最優(yōu)路徑。正是因?yàn)樵谒阉鬟^(guò)程中選取的是最小評(píng)價(jià)函數(shù)值，所以最終形成的路徑代價(jià)也是最小的。評(píng)價(jià)函數(shù)f（n）的表達(dá)式為

式中：g（n）為起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際路徑代價(jià)值；h（n）為當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)路徑代價(jià)值。

計(jì)算h（n）、g（n）有2種計(jì)算方法，分別為歐幾里得距離與曼哈頓距離。本文采用的是歐幾里得距離[17]算法，其表達(dá)式為

式中：（xo，yo）為當(dāng)前點(diǎn)；（xs，ys）為起始點(diǎn)；（xt，yt）為目標(biāo)點(diǎn)。

由上述分析可知，A*算法在運(yùn)行搜索過(guò)程中需要不斷更新OPEN和CLOSE數(shù)組列表，計(jì)算每個(gè)節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值，從而尋找路徑代價(jià)最小節(jié)點(diǎn)，完成對(duì)路徑的規(guī)劃，但同時(shí)在路徑規(guī)劃過(guò)程中也暴露了A*算法存在的不足：

（1）在路徑搜索過(guò)程中無(wú)用節(jié)點(diǎn)過(guò)多，計(jì)算量過(guò)大而使得算法效率變低，運(yùn)行時(shí)間變長(zhǎng)。

（2）在規(guī)劃的路徑中不必要的轉(zhuǎn)折點(diǎn)過(guò)多，導(dǎo)致路徑變長(zhǎng)且平滑度較差，不利于移動(dòng)機(jī)器人的平穩(wěn)運(yùn)行。

（3）在規(guī)劃路徑時(shí)，只考慮障礙物節(jié)點(diǎn)信息，沒(méi)有考慮現(xiàn)實(shí)中移動(dòng)機(jī)器人具有一定的體積，當(dāng)其斜穿障礙物頂點(diǎn)時(shí)，其邊緣可能碰到障礙物導(dǎo)致機(jī)器人停止運(yùn)動(dòng)，甚至存在損壞的風(fēng)險(xiǎn)。

2 改進(jìn)A*算法

本文針對(duì)上述傳統(tǒng)A*算法在搜索過(guò)程中不足之處的分析，對(duì)傳統(tǒng)A*算法進(jìn)行了改進(jìn)，使得路徑得到優(yōu)化。首先，基于精簡(jiǎn)搜索策略，將父節(jié)點(diǎn)的擴(kuò)展點(diǎn)由周圍8個(gè)節(jié)點(diǎn)縮減到5個(gè)。其次，采用安全保護(hù)策略，改變子節(jié)點(diǎn)的選擇方式，避免移動(dòng)機(jī)器人發(fā)生損壞。最后，實(shí)施路徑平滑策略，減少路徑的長(zhǎng)度，刪除一些冗余點(diǎn)和拐點(diǎn)，改善平滑度。

2.1 精簡(jiǎn)搜索策略

傳統(tǒng)A*算法在每個(gè)節(jié)點(diǎn)進(jìn)行搜索時(shí)一般有8個(gè)搜索方向，分別為前、后、左、右、左前、左后、右前、右后。

9個(gè)節(jié)點(diǎn)的中心節(jié)點(diǎn)表示移動(dòng)機(jī)器人的當(dāng)前位置，而其周圍有8個(gè)節(jié)點(diǎn)，需要計(jì)算此8個(gè)節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值，選取最小值所對(duì)應(yīng)的節(jié)點(diǎn)作為移動(dòng)機(jī)器人到達(dá)的下個(gè)節(jié)點(diǎn)，導(dǎo)致其在這個(gè)過(guò)程中遍歷了許多無(wú)用節(jié)點(diǎn)，計(jì)算效率不高。此時(shí)，采用精簡(jiǎn)搜索策略[18]，在搜索時(shí)根據(jù)目標(biāo)節(jié)點(diǎn)pt（xt，yt）與當(dāng)前節(jié)點(diǎn)po（xo，yo）的相對(duì)坐標(biāo)位置選擇不同的搜索區(qū)域。根據(jù)已知的當(dāng)前點(diǎn)坐標(biāo)po與目標(biāo)點(diǎn)坐標(biāo)pt求取余弦值cos B，再將這2點(diǎn)的余弦值轉(zhuǎn)化成相應(yīng)的角度值。

建立直角坐標(biāo)系，先將當(dāng)前點(diǎn)坐標(biāo)po設(shè)置為坐標(biāo)原點(diǎn)，再將坐標(biāo)系均勻劃分為8個(gè)區(qū)域，同時(shí)求取目標(biāo)點(diǎn)pt到當(dāng)前點(diǎn)po角度值B。當(dāng)337.5＜B＜360或0＜B＜22.5時(shí)，pt為第一區(qū)域；當(dāng)22.5≤B＜67.5時(shí)，pt為第二區(qū)域；當(dāng)67.5≤B＜112.5時(shí)，pt為第三區(qū)域；當(dāng)112.5≤B＜157.5時(shí)，pt為第四區(qū)域；當(dāng)157.5≤B＜202.5時(shí)，pt為第五區(qū)域；當(dāng)202.5≤B＜247.5時(shí)，pt為第六區(qū)域；當(dāng)247.5≤B＜292.5時(shí)，pt為第七區(qū)域；當(dāng)292.5≤B＜337.5時(shí)，pt為第八區(qū)域。

當(dāng)A*算法運(yùn)行，開(kāi)始使用精簡(jiǎn)搜索策略對(duì)路徑進(jìn)行搜尋，精簡(jiǎn)搜索策略應(yīng)用如圖1所示。

圖1 精簡(jiǎn)搜索策略應(yīng)用圖

在第一區(qū)域時(shí)，剔除左、左前、左后3個(gè)節(jié)點(diǎn)搜索；在第二區(qū)域時(shí)，剔除左、后、左后3個(gè)節(jié)點(diǎn)搜索；在第三區(qū)域時(shí)，剔除左后、后、右后3個(gè)節(jié)點(diǎn)搜索；在第四區(qū)域時(shí)，剔除右、右后、后3個(gè)節(jié)點(diǎn)搜索；在第五區(qū)域時(shí)，剔除右前、右、右后3個(gè)節(jié)點(diǎn)搜索；在第六區(qū)域時(shí)，剔除右、右前、前3個(gè)節(jié)點(diǎn)搜索；在第七區(qū)域時(shí)，剔除左前、前、右前3個(gè)節(jié)點(diǎn)搜索；在第八區(qū)域時(shí)，剔除左、左前、前3個(gè)節(jié)點(diǎn)搜索。正是通過(guò)精簡(jiǎn)搜索策略，從傳統(tǒng)的8個(gè)節(jié)點(diǎn)搜索縮減到5個(gè)，剔除了許多無(wú)用節(jié)點(diǎn)的搜索，節(jié)約了搜索時(shí)間，計(jì)算效率得到提高。

2.2 安全保護(hù)策略

在傳統(tǒng)A*算法中，當(dāng)選擇下個(gè)子節(jié)點(diǎn)進(jìn)行擴(kuò)展時(shí)，只考慮障礙物所處的位置，未考慮因移動(dòng)機(jī)器人體積問(wèn)題而帶來(lái)的障礙物與子節(jié)點(diǎn)之間的邊緣碰撞。因此，當(dāng)它斜穿障礙物頂點(diǎn)時(shí)，可能會(huì)發(fā)生碰撞，帶來(lái)安全隱患。針對(duì)此問(wèn)題，本文優(yōu)化子節(jié)點(diǎn)的選擇，避免產(chǎn)生碰撞。子節(jié)點(diǎn)圖如圖2所示。

圖2 子節(jié)點(diǎn)圖

父節(jié)點(diǎn)與8個(gè)子節(jié)點(diǎn)位置關(guān)系圖參見(jiàn)文獻(xiàn)[9]。將父節(jié)點(diǎn)相鄰的8個(gè)子節(jié)點(diǎn)劃分為2組。在父節(jié)點(diǎn)垂直方向的4個(gè)子節(jié)點(diǎn)（節(jié)點(diǎn)2、4、6、8）分為Ⅰ類。在父節(jié)點(diǎn)對(duì)角線方向的4個(gè)子節(jié)點(diǎn)（節(jié)點(diǎn)1、3、5、8）分為Ⅱ類。根據(jù)Ⅰ類、Ⅱ類子節(jié)點(diǎn)的優(yōu)先順序，對(duì)子節(jié)點(diǎn)進(jìn)行如下優(yōu)化。

（1）當(dāng)障礙物在節(jié)點(diǎn)2時(shí)，則刪除節(jié)點(diǎn)1、節(jié)點(diǎn)3，從而不產(chǎn)生O1、O3這2條相關(guān)路徑。

（2）當(dāng)障礙物在節(jié)點(diǎn)4時(shí)，則刪除節(jié)點(diǎn)3、節(jié)點(diǎn)5，從而不產(chǎn)生O3、O5這2條相關(guān)路徑。

（3）當(dāng)障礙物在節(jié)點(diǎn)6時(shí)，則刪除節(jié)點(diǎn)5、節(jié)點(diǎn)7，從而不產(chǎn)生O5、O7這2條相關(guān)路徑。

（4）當(dāng)障礙物在節(jié)點(diǎn)8時(shí)，則刪除節(jié)點(diǎn)1、節(jié)點(diǎn)7，從而不產(chǎn)生O1、O7這2條相關(guān)路徑。

此方法有效防止生成障礙物相鄰節(jié)點(diǎn)路徑，使與障礙物產(chǎn)生一定的距離，避免移動(dòng)機(jī)器人斜穿障礙物頂點(diǎn)，發(fā)生碰撞事故。

2.3 路徑平滑策略

當(dāng)使用傳統(tǒng)A*算法生成一條從起點(diǎn)到終點(diǎn)的完整路徑時(shí)，由于在搜索過(guò)程中有π/4角度的限制，所以存在許多轉(zhuǎn)折點(diǎn)和冗余點(diǎn)。針對(duì)該問(wèn)題，使用Floyd算法[19]對(duì)路徑進(jìn)行平滑度處理，將不必要的轉(zhuǎn)折點(diǎn)做刪除處理，縮短整個(gè)路徑的長(zhǎng)度并且減少機(jī)器人在轉(zhuǎn)折點(diǎn)的時(shí)間損耗，確保機(jī)器人更加平穩(wěn)、快速地運(yùn)行。

Floyd算法又稱為插點(diǎn)法，是借鑒動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法。本文結(jié)合A*算法與Floyd算法對(duì)路徑進(jìn)行二次規(guī)劃，通過(guò)使用Floyd算法從起始點(diǎn)到目標(biāo)點(diǎn)進(jìn)行了多次迭代優(yōu)化，進(jìn)一步縮短使用A*算法規(guī)劃出的路徑長(zhǎng)度，同時(shí)極大地改善了路徑的平滑化，更加符合現(xiàn)實(shí)應(yīng)用中規(guī)劃的最優(yōu)路徑。Floyd算法原理圖[20-21]如圖3所示。

圖3 Floyd算法原理圖

L（A，D）為節(jié)點(diǎn)A到節(jié)點(diǎn)D的距離，R（A，D）為節(jié)點(diǎn)A到節(jié)點(diǎn)D的路徑。從圖3可知，節(jié)點(diǎn)A、D之間存在障礙物，假設(shè)L（A，D）=+∞，即節(jié)點(diǎn)A、D之間距離為無(wú)窮大。R（A，D）=A-＞D，即節(jié)點(diǎn)A到節(jié)點(diǎn)D的路徑為節(jié)點(diǎn)A指向節(jié)點(diǎn)D。

B節(jié)點(diǎn)是節(jié)點(diǎn)A、D之間規(guī)避障礙物所規(guī)劃的節(jié)點(diǎn)：

若

則

在節(jié)點(diǎn)B、D之間插入節(jié)點(diǎn)C：

若

則

通過(guò)Floyd算法優(yōu)化，由原來(lái)的規(guī)劃路徑節(jié)點(diǎn)A、B、D到現(xiàn)在的規(guī)劃路徑節(jié)點(diǎn)A、C、D，刪除了一些多余的節(jié)點(diǎn)，路徑轉(zhuǎn)折角度變小，使得路徑平滑度得到改善，確保機(jī)器人更加平穩(wěn)運(yùn)行。

3 仿真實(shí)驗(yàn)與分析

3.1 地圖構(gòu)建

本文改進(jìn)的A*算法采用Matlab 2018b作為軟件平臺(tái)，Inter Core i5-8400 2.8GHz CPU，RAM 4GB作為硬件平臺(tái)。使用傳統(tǒng)A*算法與與改進(jìn)A*算法（精簡(jiǎn)搜索策略A*算法、安全保護(hù)策略A*算法、路徑平滑策略A*算法）分別對(duì)移動(dòng)機(jī)器人行駛路徑進(jìn)行規(guī)劃，得出相應(yīng)的仿真實(shí)驗(yàn)結(jié)果。將仿真結(jié)果進(jìn)行對(duì)比，從而驗(yàn)證改進(jìn)A*算法的有效性。

本文通過(guò)20×20的柵格圖來(lái)構(gòu)建環(huán)境地圖，將障礙物信息寫入柵格環(huán)境地圖中。

3.2 仿真分析

本文將傳統(tǒng)A*算法與分別使用精簡(jiǎn)搜索策略、安全策略、平滑策略的改進(jìn)A*算法進(jìn)行仿真，A*算法柵格圖如圖4所示。圖4中，白色柵格為可通行區(qū)域，黑色柵格為障礙物區(qū)域，藍(lán)色柵格為在路徑規(guī)劃過(guò)程中使用A*算法遍歷的柵格數(shù)量。

圖4 A*算法柵格圖

由圖4可知，在使用柵格圖進(jìn)行路徑規(guī)劃時(shí)，起始點(diǎn)坐標(biāo)為（1.5，1.5），用紅色小圓圈表示；目標(biāo)點(diǎn)坐標(biāo)為（20.5，20.5），用綠色小圓圈表示。從終點(diǎn)到起點(diǎn)用藍(lán)色線條依次連接起來(lái)的路徑，即為通過(guò)A*算法規(guī)劃的路徑。傳統(tǒng)A*算法存在遍歷許多無(wú)用節(jié)點(diǎn)、邊緣碰撞、平滑性差等問(wèn)題。改進(jìn)A*算法柵格圖如圖5所示，A*算法與改進(jìn)A*算法對(duì)比如表1所示。

由圖5和表1可知，在改進(jìn)A*算法中，在2個(gè)紅色圓圈處相比于圖4中傳統(tǒng)A*算法搜索節(jié)點(diǎn)進(jìn)行了縮減，左側(cè)圓圈處縮減了4個(gè)節(jié)點(diǎn)，右側(cè)圓圈處縮減了3個(gè)節(jié)點(diǎn)。正是通過(guò)使用精簡(jiǎn)搜素策略，將遍歷節(jié)點(diǎn)數(shù)從226個(gè)減少到219個(gè)，搜索節(jié)點(diǎn)數(shù)減少了3.1%，縮短了路徑規(guī)劃的運(yùn)行時(shí)間。路徑規(guī)劃時(shí)不僅要考慮縮短規(guī)劃時(shí)間，要重要的是考慮路徑的安全性，為此不得不增加路徑轉(zhuǎn)折點(diǎn)與路徑長(zhǎng)度作為路徑安全代價(jià)。通過(guò)使用安全搜索策略，使得規(guī)劃的路徑與障礙物之間解決了移動(dòng)機(jī)器人邊緣碰撞問(wèn)題，切實(shí)提高了移動(dòng)機(jī)器人的安全性，但也增加了路徑長(zhǎng)度與路徑轉(zhuǎn)折點(diǎn)。最后通過(guò)Floyd算法對(duì)路徑進(jìn)行平滑處理，一方面，解決了因考慮安全性而引起的路徑長(zhǎng)度問(wèn)題，路徑長(zhǎng)度由傳統(tǒng)A*算法規(guī)劃的29.799到使用改進(jìn)A*算法規(guī)劃的28.815 4，路徑長(zhǎng)度縮短3.3%；另一方面，減少了路徑轉(zhuǎn)折點(diǎn)，改善了路徑的平滑度。

圖5 改進(jìn)A*算法柵格圖

表1 A*算法與改進(jìn)A*算法對(duì)比

4 結(jié)語(yǔ)

本文針對(duì)傳統(tǒng)A*算法存在的搜索效率低、轉(zhuǎn)折點(diǎn)過(guò)多、路徑不平滑等問(wèn)題，通過(guò)采用精簡(jiǎn)搜索策略、安全搜索策略、平滑路徑策略對(duì)傳統(tǒng)A*算法進(jìn)行改進(jìn)。采用精簡(jiǎn)搜索策略，減少無(wú)用區(qū)域的搜索，提高搜索效率；采用安全搜索策略，避免邊緣碰撞，確保其安全性；采用平滑路徑策略，減少轉(zhuǎn)折點(diǎn)、改善路徑的平滑度。4組仿真對(duì)比實(shí)驗(yàn)表明：路徑運(yùn)行時(shí)間、路徑長(zhǎng)度均得到了優(yōu)化，改進(jìn)A*算法優(yōu)于傳統(tǒng)A*算法。下一步研究將從A*算法的評(píng)價(jià)函數(shù)入手，進(jìn)一步提高A*算法的搜索效率，縮短搜索時(shí)間。