王恒升，任 晉

1.中南大學(xué) 機(jī)電工程學(xué)院，長沙 410083

2.中南大學(xué) 高性能復(fù)雜制造國家重點(diǎn)實(shí)驗(yàn)室，長沙 410083

1 引言

對移動機(jī)器人進(jìn)行遠(yuǎn)程控制是很多場合的不二選擇。例如月球或火星探測車，用于災(zāi)害或危險(xiǎn)場合的探測、作業(yè)或救援機(jī)器人等。對機(jī)器人進(jìn)行遠(yuǎn)程操作的研究與實(shí)踐很早就出現(xiàn)了，例如在美國三厘島核電站發(fā)生核事故后，就使用了一臺遠(yuǎn)程操作的機(jī)器人，操作人員在無核區(qū)，通過鉛化玻璃，操作處于有核區(qū)的一臺機(jī)器進(jìn)行核事故處理[1]。

文獻(xiàn)[2]提出一種通過自然語言進(jìn)行遠(yuǎn)程人機(jī)交互的方案，即操作人員通過自然語言發(fā)出指令，機(jī)器人在遠(yuǎn)程執(zhí)行指令要求的動作。這種自然的、類似人與人之間的交互方式不（或者很少）需要對操作人員進(jìn)行專門訓(xùn)練。用于救災(zāi)機(jī)器人的交互時(shí)，方便領(lǐng)域?qū)＜抑苯訉C(jī)器人發(fā)出緊急作業(yè)指令；用于服務(wù)機(jī)器人的交互時(shí)，更容易為普通用戶所接受。

正如人與人之間進(jìn)行語言交流時(shí)，人們對交流中所用的語言術(shù)語有著基本的共識，這是相互理解的基礎(chǔ)。與機(jī)器人進(jìn)行自然語言交互時(shí)，也需要對語義進(jìn)行定義。目前語義網(wǎng)的研究對概念的語義定義采用本體（Ontology）的方式[3-8]，即定義概念的類結(jié)構(gòu)及相互關(guān)系，實(shí)現(xiàn)知識的表達(dá)與知識的檢索獲取。本文的研究目標(biāo)是對機(jī)器人基于自然語言進(jìn)行導(dǎo)航控制，要控制的機(jī)器人處于建筑物內(nèi)部。因此導(dǎo)航用語中有大量的建筑物內(nèi)部的地名詞，例如“走到601房門口”，“在A座4樓電梯口往左拐”等，這里的“601房”、“A座”、“4樓電梯”等均是與某建筑相關(guān)聯(lián)的地名詞。本文借用本體的方法建立建筑物內(nèi)部的地名詞的概念體系，在此基礎(chǔ)上建立建筑物的語義地圖。

本文所說的語義地圖，其實(shí)質(zhì)是基于本體的對建筑物內(nèi)部地名詞的描述，更進(jìn)一步說，是對建筑物空間知識的一種表達(dá)，或者說是關(guān)于建筑物內(nèi)部空間的數(shù)據(jù)庫。本文采用Prolog語言[9-11]，將地名詞描述為Horn Clause事實(shí)，其中包括名字信息、空間坐標(biāo)信息等。從這些事實(shí)庫中可以得到建筑物內(nèi)部空間的拓?fù)溥B接關(guān)系（即拓?fù)涞貓D）供機(jī)器人進(jìn)行路徑規(guī)劃等，也能畫出建筑內(nèi)部空間簡要的平面圖供操作者參考。這樣定義的地名詞與人對這些名詞的理解是一致的，也就是具有相同的“語義”；同時(shí)能夠方便獲得所需要的“地圖”，本文稱為語義地圖。

語義地圖是一種基于語義表達(dá)環(huán)境地理信息的一種方法，屬于知識表達(dá)的范疇，在機(jī)器人人工智能領(lǐng)域有廣泛的研究及應(yīng)用預(yù)期。Zender等人[12]首先提出并實(shí)現(xiàn)了層級式的空間表達(dá)模型，應(yīng)用于典型的室內(nèi)辦公環(huán)境，在尺度地圖、導(dǎo)航地圖、拓?fù)涞貓D的基礎(chǔ)上，通過激光、相機(jī)的傳感信息來識別物體，借助自然語言處理，抽取出概念地圖，以基于描述邏輯的本體語言的形式儲存。Crespo等人[13]提出了一種語義關(guān)系模型，機(jī)器人通過人機(jī)對話系統(tǒng)完成室內(nèi)環(huán)境下的高層導(dǎo)航任務(wù)，語義概念的相似性適應(yīng)于不同環(huán)境。Tenorth等人[14]提出了一種處理知識的服務(wù)框架KnowRob，使用prolog語言，將模糊的任務(wù)描述與任務(wù)操作所需詳細(xì)信息聯(lián)系起來；其合作者Beetz等人[15]在此基礎(chǔ)上，開發(fā)出一套功能更為完善的知識處理服務(wù)平臺Open-EASE，可實(shí)時(shí)獲取機(jī)器人的操作片段，并可以詢問到機(jī)器人所觀察和推理的信息，例如完成任務(wù)的方式、原因以及相關(guān)行為引發(fā)的后果。Drouilly等[16]和Landsiedel等[17]對室外更為復(fù)雜的語義地圖進(jìn)行了探索，描述了街道地圖。本文的關(guān)注點(diǎn)在于室內(nèi)環(huán)境的語義地圖構(gòu)建，主要目的是為移動機(jī)器人能夠應(yīng)用于室內(nèi)環(huán)境、與人通過自然語言的方式進(jìn)行交互。出發(fā)點(diǎn)是將建筑物環(huán)境信息作為先驗(yàn)知識和推理的基礎(chǔ)，服務(wù)于人機(jī)交互；進(jìn)一步基于傳感器數(shù)據(jù)對室內(nèi)空間和物體進(jìn)行辨識，補(bǔ)充語義地圖的動態(tài)信息，不在本文范圍。

本文后面的內(nèi)容安排如下：第2章以某實(shí)際大樓為例，介紹語義地圖的構(gòu)建；第3章利用“事實(shí)-規(guī)則-推理”的邏輯編程方法，在語義地圖事實(shí)庫的基礎(chǔ)上，實(shí)現(xiàn)機(jī)器人自定位的邏輯程序設(shè)計(jì)；第4章通過邏輯編程實(shí)現(xiàn)機(jī)器人的自定位算法。

2 構(gòu)建語義地圖

2.1 建筑物簡介

以中南大學(xué)機(jī)電工程學(xué)院大樓為例構(gòu)建語義地圖。該大樓是一個(gè)集辦公、教學(xué)和實(shí)驗(yàn)于一體的綜合建筑，以下簡稱CMEE，圖1為其第四層平面圖。CMEE包含4棟建筑，圖1由左到右分別為A、B、C和D棟。這4棟建筑每層均由橋式走廊連通。A棟為辦公區(qū)，共有6層。其他3棟為實(shí)驗(yàn)和教學(xué)區(qū)，共有5層，圖2示出各樓棟樓層的高度（虛線框代表樓棟，粗實(shí)線代表樓棟各層的連接通道）。CMEE相對較為復(fù)雜，在樓層、建筑群、連接通道、室內(nèi)功能空間等方面具有多樣性和代表性，涉及語義豐富，對醫(yī)院、商場、寫字樓等類型的建筑均可有相似的語義表達(dá)，因此具有一定的代表性和可移植性。

2.2 建立本體

首先考慮描述建筑物空間的最小單元（基元），選擇區(qū)域和節(jié)點(diǎn)兩類最小單元。

Fig.1 Fourth floor of CMEE圖1 CMEE第四層平面示意圖

Fig.2 Diagram of floors height of CMEE圖2 CMEE高度方向示意圖

區(qū)域是指由墻壁分割開的空間，包括房間（使用空間）和交通空間[18]。交通空間分為水平交通空間和垂直交通空間。水平交通空間又分為樓道（樓棟內(nèi)部通道）、橋式通道（連接樓棟與樓棟的通道）和臺階（連接室內(nèi)局部高差）。垂直交通空間又分為樓梯間和電梯間。

節(jié)點(diǎn)指的是區(qū)域之間的連接點(diǎn)，例如房間的門就是房間區(qū)域與樓道區(qū)域的連接點(diǎn)，再如一個(gè)十字路口的交叉點(diǎn)也是一個(gè)節(jié)點(diǎn)（即兩個(gè)或多個(gè)樓道的連接點(diǎn)，有時(shí)存在一個(gè)實(shí)際的防火門）。將節(jié)點(diǎn)定義為一個(gè)實(shí)體是方便建立區(qū)域之間的連接關(guān)系。

CMEE的概念本體如圖3所示，從不同的視角進(jìn)行分類，最終落實(shí)到最小的單元實(shí)體，即區(qū)域和節(jié)點(diǎn)。最小的單元實(shí)體可按不同的角度歸屬不同的類。例如一個(gè)房間a513，根據(jù)用途可歸到辦公室類，根據(jù)所處的樓層可歸到5樓，根據(jù)所在的樓棟可歸到A棟。

Fig.3 Ontology of CMEE圖3 CMEE的概念本體

對最小單元實(shí)體按照日常用語習(xí)慣進(jìn)行命名。例如房間編號“a601”，可以清楚看出該房間是位于A座6樓的01號房間。模仿房間命名格式，可以對具體的每一個(gè)樓道和臺階個(gè)體進(jìn)行編號，如“a6c1”代表A座6樓，后面的字母c代表其區(qū)域類型為樓道（corridor），最后的數(shù)字1是該樓道的具體編號；對節(jié)點(diǎn)的命名也一樣，如“a601d1”，代表a601房間的第一個(gè)門口（其中d代表門）；再如“a6p02”，代表a座6樓的第二個(gè)交叉路口（其中p表示樓道連接的虛擬節(jié)點(diǎn)）。需要注意的是，建筑物內(nèi)還存在若干區(qū)域無法用上述規(guī)則準(zhǔn)確命名，如橋式走廊和樓梯間等，分別連接著相鄰的樓棟與樓層。類似前文用單個(gè)字母的表達(dá)形式無法充分表明其真實(shí)的連接關(guān)系，因此引入雙字符以準(zhǔn)確命名。如區(qū)域“p4cd6”，其中，第一位字母p代表區(qū)域類型為橋式走廊（passage），第二位數(shù)字4代表位于4層，第三、四位代表連接C棟和D棟，第五位數(shù)字是該區(qū)域的具體編號。類似地，“s45a1”代表位于A棟、連接4層和5層的1號樓梯間（stairwell）區(qū)域；“e5a1”代表位于A棟5層的1號電梯（elevator）。其中，當(dāng)樓梯間（或電梯）與各層區(qū)域連接的節(jié)點(diǎn)位于橋式走廊上，即處于樓棟與樓棟之間時(shí)，借助不同編號定義的橋式走廊，如圖1所示的①～⑥，采用單個(gè)字母p（區(qū)別于a、b、c、d），配合對應(yīng)橋式走廊的唯一編號準(zhǔn)確定義。

2.3 語義地圖描述

選用Prolog語言[9-11]進(jìn)行語義地圖的描述。Prolog是一種基于一階謂詞邏輯的描述型邏輯編程語言,是最早出現(xiàn)的邏輯編程語言之一，1972年在法國馬賽由Colmerauer和Philippe Roussel共同開發(fā)，最早用于自然語言處理；迄今Prolog仍是應(yīng)用最廣的邏輯編程語言，有免費(fèi)的和商用的多個(gè)版本，廣泛應(yīng)用于機(jī)器證明、專家系統(tǒng)等需要知識表達(dá)與邏輯推理的場合。隨著新技術(shù)和新思想的出現(xiàn)，在Prolog的基礎(chǔ)上擴(kuò)充了許多功能，如約束邏輯編程（constrained logic programming，CLP）、面向?qū)ο筮壿嬀幊蹋╫bjectoriented logic programming，OOLP）、回答集編程（answer setprogramming，ASP）等，擴(kuò)展了對語義網(wǎng)支持的Prolog形成了RDF、OWL描述語言。各種版本及擴(kuò)展的邏輯編程語言，其基本描述方式和語法表達(dá)都是基于Prolog的。為閱讀方便，本文的示例均以Prolog的語法給出，并在免費(fèi)平臺SWI-Prolog上調(diào)試通過。

用Prolog對CMEE的每個(gè)單元實(shí)體進(jìn)行定義，就構(gòu)成了語義地圖的事實(shí)（facts）數(shù)據(jù)庫，這樣可以實(shí)現(xiàn)定義的完備性并避免重復(fù)定義。每一個(gè)單元實(shí)體事實(shí)包含兩項(xiàng)基本內(nèi)容：名字和坐標(biāo)。根據(jù)Prolog的規(guī)范，小寫字母開頭的表示常量，描述事實(shí)的語句中所有量均為常量；大寫字母開頭的表示變量，在實(shí)現(xiàn)推理的謂詞設(shè)計(jì)中，所有量均為需要綁定的變量。本文涉及Prolog程序的敘述均沿用這個(gè)慣例。本文的所有程序均在SWI-Prolog中調(diào)試通過。

例如一個(gè)區(qū)域?qū)嶓wa603的定義為：

area(a603,[coor(122660,110342,19600),coor(121859,112391,19600),coor(126610,114247,19600),coor(127920,110893,19600),coor(123169,109038,19600),coor(123024,109411,19600)])

其中第一項(xiàng)為區(qū)域的名稱，后面的一個(gè)列表就是該區(qū)域的多邊形頂點(diǎn)坐標(biāo)序列。

再如節(jié)點(diǎn)實(shí)體a603d1的定義為：node(a603d1,coor(122842,109876,19600))。

其中定義式中的coor(122842,109876,19600)表示一個(gè)點(diǎn)的三維坐標(biāo)，Prolog可以很方便實(shí)現(xiàn)這種自定義數(shù)據(jù)類型。

3 語義地圖應(yīng)用

有了基本的語義地圖數(shù)據(jù)庫，可以在Prolog的框架下設(shè)計(jì)各種謂詞，實(shí)現(xiàn)不同的推理需求。

3.1 生成拓?fù)涞貓D

拓?fù)涞貓D從高一層次上反映了區(qū)域之間的連接關(guān)系，是實(shí)現(xiàn)最短路徑規(guī)劃的基礎(chǔ)。生成拓?fù)涞貓D的基礎(chǔ)是建立區(qū)域和節(jié)點(diǎn)之間的連接關(guān)系。通過下面的謂詞connect/4進(jìn)行推理，可找到直接相連接的兩個(gè)區(qū)域Area1和Area2。

謂詞中的參數(shù)Node是連通兩個(gè)區(qū)域的節(jié)點(diǎn)，Dis為兩個(gè)區(qū)域之間的距離。這個(gè)推理描述的邏輯為：“如果節(jié)點(diǎn)Node既在區(qū)域Area1內(nèi)，又在區(qū)域Area2內(nèi)，且Area1和Area2不同，那么這兩個(gè)區(qū)域通過該節(jié)點(diǎn)直接相連”。Prolog是一種描述性語言，其謂詞設(shè)計(jì)的基本思想是按約束滿足問題(constraint satisfaction problem，CSP)的思路將問題描述出來。例如上面的謂詞connect(Area1,Area2,Node,Dis)就是尋找同時(shí)滿足in_area(Node,Area1)（即Node在區(qū)域Area1中）、in_area(Node,Area2)（即Node在區(qū)域Area2中）和not(Area1==Area2)（即這兩個(gè)區(qū)域不同）3個(gè)條件的變量Area1、Area2和Node；最后一個(gè)條件area_distance()不需要搜索，只是完成一個(gè)計(jì)算過程，即計(jì)算通過節(jié)點(diǎn)Node相連的兩個(gè)區(qū)域Area1和Area2之間的距離。問題的求解是由Prolog來完成的。設(shè)計(jì)者的主要任務(wù)只是描述問題而不是像其他程序設(shè)計(jì)語言那樣給出具體的求解過程。

有了上面的謂詞后，可借助謂詞save_fact/0,由CMEE的基本事實(shí)庫生成一個(gè)擴(kuò)展事實(shí)庫directly_link.pl。

事實(shí)庫directly_link.pl描述了CMEE的所有區(qū)域之間的直接相連的關(guān)系，實(shí)際上就是生成一個(gè)拓?fù)涞貓D數(shù)據(jù)庫。

3.2 擴(kuò)充的概念語義

有了這些定義的基本單元實(shí)體后，可以通過基本規(guī)則來定義擴(kuò)充的概念語義，如樓棟（building）、樓層（floor）等。這些語義是日常口語中常用到的。下面給出通過區(qū)域名稱和當(dāng)前位置坐標(biāo)來判別樓棟和樓層的推理過程。

3.2.1 根據(jù)區(qū)域名稱推理

若機(jī)器人觀察到區(qū)域門牌號，或是從人機(jī)交互中獲得空間區(qū)域的名稱信息，則可以根據(jù)這些地名詞和地名詞的命名規(guī)則，推理出相應(yīng)的樓層樓棟信息。

一個(gè)名為Name的實(shí)體屬于“某棟”（Building）的基本規(guī)則可寫為：

第一個(gè)字母

一個(gè)名為Name的實(shí)體屬于“某層”(Floor)的基本規(guī)則可寫為：

中的第二個(gè)字母

3.2.2 根據(jù)當(dāng)前坐標(biāo)推理

機(jī)器人也可根據(jù)自身實(shí)時(shí)位置坐標(biāo)，推理出相應(yīng)的樓層樓棟信息。下面的謂詞building_by_coor/2實(shí)現(xiàn)這一功能。

這里還用到了樓棟定義的事實(shí)，如A棟區(qū)域進(jìn)行定義如下：

building(a).%區(qū)域a是樓棟

area(a,[coor(125300,117600,_),oor(97900,117600,_),coor(97900,45798,_),coor(107365,47528,_),coor(131465,53167,_),coor(148876,57241,_),coor(140363,79037,_),coor(141760,79583,_),coor(135211,96349,_),coor(133814,95804,_)]).%A棟的區(qū)域坐標(biāo)信息

判斷位置點(diǎn)與多邊形關(guān)系的謂詞point_ploygon/3是這里的核心，關(guān)于這個(gè)謂詞的實(shí)現(xiàn)在后面第4章有詳述。

通過下面的謂詞floor_by_coor/2可以根據(jù)坐標(biāo)推理出所在的樓層。

該謂詞可判斷當(dāng)前位置處于A棟的各個(gè)樓層，其數(shù)據(jù)與圖2中樓層高度是統(tǒng)一的。其他樓棟的樓層謂詞也類似，這里省略以免冗長。

3.3 搜索最短路徑

路徑規(guī)劃是移動機(jī)器人完成室內(nèi)導(dǎo)航的基本任務(wù)之一。下面的謂詞path/8可找出區(qū)域Area1到區(qū)域Area2的可行路徑序列。

not(member(Area3,Pathlist1)),%保證新找到的區(qū)域不在已經(jīng)過的區(qū)域序列中Dis3 isDis1+Dis2,

要找到連接起點(diǎn)Area1到終點(diǎn)Area2的一條路徑，就先找到一個(gè)與起點(diǎn)Area1直接相連的區(qū)域Area3；將原始路徑問題改為找到“起點(diǎn)是Area3，終點(diǎn)是Area2”的路徑序列，如此用遞歸的方法最終可以解決原始問題。遞歸求解必須給出終止條件，如下。

當(dāng)path/8中的兩個(gè)區(qū)域直接相連，不再需要找到一個(gè)中間區(qū)域時(shí)，遞歸結(jié)束，得到滿足條件的路徑序列。

path/8中還用到其他約束條件，如not(member(Area3,Pathlist1))表示“中間區(qū)域Area3不在已經(jīng)過的區(qū)域序列Pathlist1中”，確?！安蛔呋仡^路”。該謂詞同時(shí)還列出經(jīng)過的節(jié)點(diǎn)序列和路徑的路程長度。

謂詞find_route/5從所有路徑中找出路程長度最小的路徑序列，由約束條件min(Dislist,Dis)來描述。若未找到答案，則返回空序列。

3.4 舉例

為了方便說明，截取圖1中CMEE第四層的局部區(qū)域，如圖4所示。用2.3節(jié)的方法建立語義地圖，用3.1節(jié)的方法生成形如“connect(c410,c4c3,c405d2,7276).”(表示房間c410和樓道c4c3通過節(jié)點(diǎn)c405d2相連，距離權(quán)值為7276 mm)的拓?fù)溥B接數(shù)據(jù)庫（即拓?fù)涞貓D）。為方便表達(dá)，將拓?fù)潢P(guān)系畫在圖5中。

Fig.4 Partial area of the fourth floor of CMEE圖4 CMEE的第四層局部區(qū)域

Fig.5 Topological graph of Fig.4圖5 圖4所示區(qū)域的拓?fù)潢P(guān)系

在與機(jī)器人進(jìn)行交互時(shí)，如需要從樓道c4c3到目的地c410，進(jìn)行路徑規(guī)劃，可以發(fā)出詢問“find_route(b4c2,c410,Pathlist,Nodelist,Dis).”。 由 3.3 節(jié) 的謂詞find_route/5可以得到從樓道b4c2到房間c410的最短路徑：區(qū)域序列為Pathlist=[b4c2,p4bc1,c4c3,c410],途徑節(jié)點(diǎn)序列為Nodelist=[b4p01,c4p01,c405d2],總的距離和為Dis=66408 mm。最短路徑在圖5中用粗實(shí)線表示，可以看出，該最短路徑是正確的。

4 點(diǎn)與多邊形的位置關(guān)系

3.2 節(jié)中使用了一個(gè)謂詞point_ploygon/3，用來判斷點(diǎn)與多邊形的位置關(guān)系。這個(gè)謂詞在機(jī)器人的自定位中很有用。本章詳細(xì)說明這一謂詞的實(shí)現(xiàn)。

4.1 解決思路

點(diǎn)和多邊形的位置關(guān)系是計(jì)算機(jī)圖形學(xué)領(lǐng)域的基本問題[19-21]。常用的3種判斷方法是：夾角和檢驗(yàn)法、叉積判斷法和射線法。其中，夾角和檢驗(yàn)法需要進(jìn)行大量復(fù)雜三角運(yùn)算；叉積判斷法只能判斷凸多邊形，不具備普適性，改進(jìn)后計(jì)算量也不容忽視；射線法是從待判斷點(diǎn)引一條射線，通過其與多邊形交點(diǎn)數(shù)的奇偶性進(jìn)行判斷，是最常用的一種方法。

文獻(xiàn)[22]基于射線法的基本原理，提出一種建立多邊形頂點(diǎn)坐標(biāo)數(shù)據(jù)庫，然后利用數(shù)據(jù)庫的SQL語言進(jìn)行搜索。設(shè)計(jì)合適的搜索條件，可以得到點(diǎn)與多邊形位置的判斷結(jié)果。方法簡便，運(yùn)算效率高。本節(jié)的方法受這一思路的啟發(fā)，將多邊形表示為Prolog數(shù)據(jù)事實(shí)，然后利用Prolog的搜索及推理機(jī)制，實(shí)現(xiàn)點(diǎn)與多邊形位置關(guān)系的判斷。在具體實(shí)現(xiàn)上本節(jié)將待判斷的點(diǎn)當(dāng)作坐標(biāo)原點(diǎn)，計(jì)算待判斷多邊形頂點(diǎn)的相對坐標(biāo)；將點(diǎn)與多邊形的位置關(guān)系轉(zhuǎn)化為直角坐標(biāo)系的正橫軸與一系列邊線段的相交關(guān)系。算法處理邏輯清晰，算法應(yīng)用適合任何形式的多邊形。

4.2 算法描述

將多邊形平移到待判斷點(diǎn)為原點(diǎn)的坐標(biāo)系內(nèi)，考慮任意邊與正x軸的相交關(guān)系，遍歷所有邊，計(jì)算總的相交次數(shù)，可以得到點(diǎn)與多邊形的關(guān)系：若交點(diǎn)總數(shù)為奇數(shù)，則被測點(diǎn)在多邊形內(nèi)；偶數(shù)，則在多邊形外；在多邊形上的情況需單獨(dú)判斷。如圖6給出了所有可能的點(diǎn)與線段的相對關(guān)系。

Fig.6 Positional relationship between point and lines圖6 點(diǎn)與線段的位置關(guān)系

（1）圖（a）表示線段在任一單獨(dú)的象限內(nèi)，與正x軸無交點(diǎn)。圖（b）表示線段跨越1-2、2-3、3-4象限，無交點(diǎn)。圖（c）表示線段跨越1-4象限，有交點(diǎn)。這3種情況比較容易判斷，圖中的ΔQ為線段端點(diǎn)所處象限的差的絕對值，根據(jù)這個(gè)值就可以對應(yīng)這3種情況，進(jìn)而確定交點(diǎn)情況。有一種特殊情況如圖（d），將正y軸歸于第一象限，負(fù)y軸歸于第四象限，此時(shí)ΔQ=3與圖（c）一樣，但此時(shí)被測點(diǎn)處于線段上；為了區(qū)分這兩種情況，增加“兩端點(diǎn)橫坐標(biāo)均為0”的條件。

（2）圖（e）和圖（f）為 ΔQ=2的情況，即線段兩端點(diǎn)位于相對象限。此時(shí)可能有一個(gè)交點(diǎn)，或者無交點(diǎn)，或者在線段上。具體情況可依據(jù)線段與x軸的交點(diǎn)來區(qū)分，交點(diǎn)坐標(biāo)為：

x>0時(shí)，線段與x正半軸有一個(gè)交點(diǎn)；x<0時(shí)，線段與x正半軸無交點(diǎn)；x=0時(shí)，被測點(diǎn)處于線段上。

（3）圖（g）到圖（i）涉及到被測線段有端點(diǎn)在x軸的情況。為了處理這種情況，特別將x軸負(fù)半軸上的點(diǎn)集定義為第八象限，將x軸正半軸上的點(diǎn)集定義為第十六象限。若ΔQ=8，則兩端點(diǎn)分別位于x軸的正負(fù)半軸，如圖（g）所示，點(diǎn)在線段上；若ΔQ=4,5,6,7，則一端點(diǎn)位于x軸負(fù)半軸上，如圖（i）所示，線段與x正半軸無交點(diǎn)；若ΔQ=12,13,14,15，則一端點(diǎn)位于x軸正半軸上，如圖（h）所示，線段與x正半軸有交點(diǎn)。參照文獻(xiàn)[16]中給出的方法，根據(jù)走向給各交點(diǎn)賦不同的權(quán)值，比較兩端點(diǎn)的縱坐標(biāo)：

若y2>y1，走向向上，交點(diǎn)個(gè)數(shù)取值+0.5；

若y2

若y2=y1，走向水平，交點(diǎn)個(gè)數(shù)取值0。

表1總結(jié)了圖6的所有情況，分為4類，其中0類和1類正好對應(yīng)“0個(gè)交點(diǎn)”和“1個(gè)交點(diǎn)”的情況。其中符號0(1)表示類型0的第一種情況，2(3)表示類型2的第三種情況，以此類推。

Table 1 Classification of positional relationship between point and lines表1 點(diǎn)與線段位置關(guān)系分類情況

根據(jù)以上分析，判斷待測點(diǎn)與多邊形位置關(guān)系的算法描述如下：

（1）將待測點(diǎn)設(shè)為原點(diǎn)，對多邊形各頂點(diǎn)相對待判斷點(diǎn)進(jìn)行坐標(biāo)平移變換。

（2）若存在一多邊形頂點(diǎn)與原點(diǎn)重合，則待測點(diǎn)位于多邊形上，跳至（9）。

（3）檢測多邊形一邊線段與原點(diǎn)的關(guān)系，給出關(guān)系類型（如表1）。

（4）若其類型為2，則待測點(diǎn)位于多邊形上，跳至（9）。

（5）若其類型為0、1、3，則原點(diǎn)與線段的交點(diǎn)數(shù)分別為0、1、0.5（或-0.5）。

（6）檢查是否遍歷完所有邊。若無，則跳至（3）檢測下一條邊；若已遍歷完成，則繼續(xù)下一步。

（7）將點(diǎn)與遍歷過的各邊線段的交點(diǎn)數(shù)目求和。

（8）檢測結(jié)果：若交點(diǎn)和為奇數(shù)，則點(diǎn)在多邊形內(nèi)；若為偶數(shù)，點(diǎn)在多邊形外。

（9）結(jié)束。

4.3 算法的Prolog實(shí)現(xiàn)

以上算法可以用任何編程語言來實(shí)現(xiàn)，下面給出Prolog的程序?qū)崿F(xiàn)，該程序充分利用Prolog的特點(diǎn)，結(jié)構(gòu)清晰，運(yùn)行效率高。設(shè)計(jì)謂詞point_polygon/3，如下：

point_polygon(Coor,Area,InOrOut):-%Coor為待測點(diǎn),Area為多邊形區(qū)域,InOrOut標(biāo)志判斷結(jié)果

area(Area,[Head1|Tail]), %匹配出多邊形區(qū)域?qū)?yīng)的頂點(diǎn)坐標(biāo)序列

append([Head1|Tail],[Head1],List),%將坐標(biāo)序列首項(xiàng)添加至序列尾部

coor_transform(Coor,List,NewList),%以待測點(diǎn)為原點(diǎn),對坐標(biāo)序列進(jìn)行坐標(biāo)變換

(member(coor(0,0,_),NewList),%判定點(diǎn)是否為多邊形頂點(diǎn)

InOrOut=-1;%若是,給InOrOut賦值-1

intersection_number(NewList,0,N), %逐項(xiàng)判斷原點(diǎn)與各新線段的位置關(guān)系及交點(diǎn)數(shù),累加得出交點(diǎn)總數(shù)

round_mod(N,InOrOut)).%取整后判斷交點(diǎn)數(shù)的奇偶性,輸出InOrOut

上述算法預(yù)先將判斷點(diǎn)和多變形頂點(diǎn)重合的情況剝離；原坐標(biāo)點(diǎn)序列相對于待測點(diǎn)進(jìn)行相對坐標(biāo)轉(zhuǎn)換后，得到新的坐標(biāo)點(diǎn)序列和原點(diǎn)的相對位置關(guān)系，將線段端點(diǎn)的象限差作為分類依據(jù)進(jìn)行判別。

4.4 實(shí)例驗(yàn)證

為便于對比驗(yàn)證，采用文獻(xiàn)[22]中的范例，并稍加改動，將全部可能產(chǎn)生特殊交點(diǎn)的情況考慮進(jìn)去，以test命名測試區(qū)域，該區(qū)域事實(shí)為：

area(test,[coor(240,22,_),coor(222,100,_),coor(347,31,_),coor(366,170,_),coor(302,226,_),coor(383,226,_),coor(337,352,_),coor(289,289,_),coor(185,289,_),coor(96,325,_),coor(182,170,_),coor(146,170,_),coor(80,200,_)])

其中，謂詞area的第二個(gè)參數(shù)即為區(qū)域test的有序坐標(biāo)點(diǎn)序列，其二維平面圖像如圖7所示。坐標(biāo)點(diǎn)序列亦可參照表2。

Fig.7 Example of polygon area圖7 多邊形實(shí)例

Table 2 Vertex coordinates of polygon in Fig.7表2 圖7的多邊形端點(diǎn)坐標(biāo)

取10個(gè)有代表性的點(diǎn)進(jìn)行驗(yàn)證（圖7中用圓圈包圍的數(shù)字），其中點(diǎn)①～⑤為文獻(xiàn)[22]中的范例點(diǎn)，方便對比驗(yàn)證，⑥～⑩為隨機(jī)抽取的任意點(diǎn)。待測點(diǎn)①～⑩的二維坐標(biāo)分別為(216，64),(113,100),(200,170),(231,226),(158,289),(337,352),(103,260),(164.8,201),(247,135),(190,43)。程序運(yùn)行結(jié)果：點(diǎn)①、③～⑤、⑨在多邊形內(nèi)部，點(diǎn)②、⑦、⑩在多外形外部，點(diǎn)⑥、⑧在多邊形邊上，符合實(shí)際情況。

針對前面第3章建立的語義地圖，對移動機(jī)器人的定位算法和程序進(jìn)行了真機(jī)實(shí)驗(yàn)。CMEE的語義地圖數(shù)據(jù)庫由各樓棟和樓層中的所有區(qū)域事實(shí)和節(jié)點(diǎn)事實(shí)構(gòu)成，形如2.3節(jié)所述。全部的區(qū)域事實(shí)共665條，節(jié)點(diǎn)事實(shí)共924條。

在獲取機(jī)器人實(shí)時(shí)的三維坐標(biāo)后，借助3.2.2節(jié)所述謂詞building_by_coor/2可推理出其所在樓層，機(jī)器人的自定位問題便由三維轉(zhuǎn)化為二維平面問題。

例如，區(qū)域a420的事實(shí)為：

area(a420,[coor(135475,45840,12800),coor(135621,46212,12800),coor(130870,48068,12800),coor(129560,44714,12800),coor(134311,42859,12800),coor(135111,44908,12800)]).

選取機(jī)器人所處3個(gè)位置：（1）節(jié)點(diǎn)a420d1（a420的1號門）；（2）a421d1（a421的1號門）；（3）a420內(nèi)部任意一點(diǎn)node420n1。這3個(gè)位置的坐標(biāo)：

node(a420d1,coor(135293,45374,12800))

node(a421d1,coor(136603,48727,12800))

node(node420n1,coor(132794,45259,12800))

算法point_polygon/3的運(yùn)算結(jié)果與實(shí)際相符，即點(diǎn)a420d1、a421d1和node420n1與區(qū)域的位置關(guān)系分別為在多邊形邊上（InOrOut=-1）、在多邊形外（InOr-Out=0）和在多邊形內(nèi)（InOrOut=1）。

4.5 層次漸進(jìn)的自定位算法

機(jī)器人在建筑物內(nèi)自定位時(shí)，需要判斷機(jī)器人所在點(diǎn)的區(qū)域位置。依據(jù)前述建立的語義地圖及擴(kuò)展的語義數(shù)據(jù)庫，引入層次漸進(jìn)的搜索思路，先判斷所在樓棟，再判斷所在樓層，大大縮小了搜索范圍。下面的謂詞self_localization/2實(shí)現(xiàn)這一功能。

self_localization(Coor,Area):-%由坐標(biāo)信息得到所在區(qū)域

building_by_coor(Coor,Building),%找到所在樓棟

floor_by_coor(Coor,Floor),%找到所在樓層

building_by_name(Area,Building),%匹配特定樓棟的區(qū)域

floor_by_name(Area,Floor),%匹配特定樓層區(qū)域

point_polygon(Coor,Area,1).%匹配所在的區(qū)域

5 結(jié)論

移動機(jī)器人的智能在很大程度上取決于機(jī)器人對人類環(huán)境的理解，實(shí)現(xiàn)這一點(diǎn)的基礎(chǔ)是機(jī)器人能夠理解人類對其所處環(huán)境的名詞概念，其實(shí)質(zhì)就是建立有關(guān)環(huán)境的知識庫。本文的工作以人用自然語言的方式，以對處于室內(nèi)的遠(yuǎn)程機(jī)器人的導(dǎo)航控制為背景，要求機(jī)器人能夠理解自然語言指令中的術(shù)語。以中南大學(xué)機(jī)電工程學(xué)院大樓為例，基于本體論建立了其室內(nèi)地名詞概念本體，用Prolog邏輯編程語言將該概念本體表述為其室內(nèi)環(huán)境的知識庫事實(shí)。Prolog邏輯推理功能的實(shí)現(xiàn)就是設(shè)計(jì)邏輯謂詞，邏輯謂詞的設(shè)計(jì)過程就是將其表述為約束滿足問題（CSP）的過程。本文設(shè)計(jì)的Prolog謂詞成功地用于建立語義地圖、機(jī)器人自定位、路徑規(guī)劃等機(jī)器人導(dǎo)航所需的基本任務(wù)。所有的程序均在SWI-Prolog環(huán)境下調(diào)試通過，程序運(yùn)行結(jié)果符合預(yù)期。這里給出的是研究救災(zāi)機(jī)器人人機(jī)交互的一部分，其他相關(guān)的工作包括自然語言理解、自然語言對話系統(tǒng)、機(jī)器人人機(jī)交互軟件平臺等，各方面的研究還在繼續(xù)。本文作為機(jī)器人基于本體概念體系的邏輯推理實(shí)例，如自定位，是基于邏輯實(shí)現(xiàn)的，即在假設(shè)傳感數(shù)據(jù)準(zhǔn)確的條件下實(shí)現(xiàn)的，未涉及基于實(shí)體機(jī)器人的傳感數(shù)據(jù)采集等內(nèi)容。在機(jī)器人真機(jī)的現(xiàn)場實(shí)驗(yàn)方面，文中的程序及算法均運(yùn)行正常，但由于機(jī)器人的里程計(jì)等傳感數(shù)據(jù)及其處理在實(shí)際應(yīng)用中還存在不少問題，作為機(jī)器人系統(tǒng)的整體導(dǎo)航效果還不夠理想，這也是學(xué)術(shù)界正在研究的一個(gè)熱點(diǎn)問題。