蘇維龍

（遼寧石油化工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，遼寧撫順113001）

交互式CAI課件中的分段路徑規(guī)劃

蘇維龍

（遼寧石油化工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，遼寧撫順113001）

在交互式CAI課件中，通過程序響應(yīng)用戶的輸入，演示變化過程，可以達(dá)到更好的教學(xué)效果。在設(shè)計(jì)一個關(guān)于《微機(jī)原理》課程的交互式CAI課件時，涉及到了一個實(shí)時路徑規(guī)劃問題。針對路徑規(guī)劃中實(shí)時性的要求，通過在路徑的不同階段采用不同的規(guī)劃方法，達(dá)到了降低計(jì)算復(fù)雜度的目的，滿足了實(shí)時性的要求。

路徑規(guī)劃j實(shí)時jCAIj3D模型

在設(shè)計(jì)一個關(guān)于《微機(jī)原理》課程的交互式CAI課件時，涉及到了一個路徑規(guī)劃問題。在實(shí)現(xiàn)兩個部件之間的數(shù)據(jù)流動時，課件試圖演示數(shù)字的移動過程。由于課件是交互性的，學(xué)生在使用課件時，可能輸入任何合法的操作和指令。因此，把數(shù)字的全部移動路徑事先存儲是不合理的。這樣，需要根據(jù)操作者輸入的操作或指令，實(shí)時地規(guī)劃數(shù)字的移動路徑［1_2］。

路徑規(guī)劃有多種方法，各有所長［3_5］。根據(jù)所面臨問題的具體情況，在路徑的不同階段，采用不同的方法。這樣，在每個階段只保留了相關(guān)的因素，簡化掉了很多與當(dāng)前階段無關(guān)的因素。在相對復(fù)雜的階段，用相對復(fù)雜的方法和計(jì)算過程保證路徑的質(zhì)量。在相對簡單的階段，用簡化的方法和計(jì)算過程降低計(jì)算的復(fù)雜度［6］。

數(shù)字移動時，首先經(jīng)過寄存器出口、起點(diǎn)支線，從寄存器來到干線（總線），在干線上行進(jìn)一段距離，進(jìn)入終點(diǎn)支線，最后到達(dá)另一個寄存器部件。根據(jù)路徑的特點(diǎn)，決定采用分段方式，各段采用不同的方法。場景是通過3DS Max建立的3D模型，使用VC代碼響應(yīng)用戶的輸入，演示數(shù)值的變化過程。寄存器、ALU、地址加法器、支線上控制門的坐標(biāo)，已經(jīng)通過其他手段獲知。為了描述方便，下文中把水平方向稱為東西南北，垂直方向稱為上下。

1　路徑各階段的規(guī)劃

如圖1所示。箭頭A所指向的是離開寄存器AL的第一個數(shù)字，這個數(shù)字0以及其后的數(shù)字011 0100，首先移到圖中箭頭B所指的寄存器出口。由于寄存器在讀出數(shù)據(jù)時，寄存器中仍然保持原有數(shù)據(jù)。這些表示原有數(shù)據(jù)的數(shù)字是固定不動的，相當(dāng)于是障礙物，移動數(shù)字要避開它們。同時，移動數(shù)字不能走出寄存器的范圍，寄存器四周相當(dāng)于是墻壁。

圖1　寄存器內(nèi)部路徑

采用人工勢場法形成路徑。其中有3個力影響數(shù)字的移動：目標(biāo)點(diǎn)“寄存器出口”的牽引力F0UT、障礙物數(shù)字的斥力F0B和墻壁的斥力FWALL。

到達(dá)寄存器出口之后，數(shù)字將沿著支線移動，經(jīng)過輸出控制門，前往干線（總線）。如圖2所示。

圖2　寄存器出口路徑

在輸出支線上，起點(diǎn)的坐標(biāo)B已知，支線上控制門的坐標(biāo)C已知。根據(jù)這兩個坐標(biāo)可以確定一個方向向量：

根據(jù)V0UT的方向，設(shè)置合適的測試間隔，決定兩個測試點(diǎn)。比如，在圖2中，方向向量V0UT指向第4象限，就在南和東兩個方向設(shè)置兩個測試點(diǎn)。從兩個測試點(diǎn)各向下發(fā)出一條射線，通過D3DXIntersect（）函數(shù)，獲知測試點(diǎn)與下方物體的距離。3D模型中，支線和干線是在同一個水平高度上的。如果測試點(diǎn)下方不是支線，測得的距離就會有不同。圖中南方向的測試點(diǎn)在支線上，而東方向的測試點(diǎn)不在支線上。因此，當(dāng)前的前進(jìn)方向確定為“向南”。

明確了第一個測試點(diǎn)之后，把它做為移動數(shù)字的目標(biāo)點(diǎn)。采用人工勢場法，讓這個目標(biāo)點(diǎn)對移動數(shù)字產(chǎn)生引力。由于支線是平行于Y軸或者X軸的，目標(biāo)點(diǎn)的引力會引著移動數(shù)字沿著支線移動，在沒有拐角時不會偏出支線，所以就把支線兩側(cè)的墻壁簡化掉，可以減少計(jì)算量。

當(dāng)?shù)谝粋€移動數(shù)字在支線上移動時，后序的移動數(shù)字可以踩著前一個移動數(shù)字的腳印前進(jìn)，不必另行規(guī)劃路徑。這就需要一個鏈表記載第一個移動數(shù)字的腳印。當(dāng)后序的移動數(shù)字都踩過某個腳印之后，這個腳印就可以從鏈表中刪除了。

移動數(shù)字到達(dá)測試點(diǎn)之后，沿著當(dāng)前方向，繼續(xù)尋找下一步的測試點(diǎn)。這個過程很像“摸石頭過河”。如圖3所示。在前進(jìn)方向的前、左、右3個方向上進(jìn)行測試。在到達(dá)拐角之前，測試結(jié)果都是“前測試點(diǎn)在支線上，左、右測試點(diǎn)不在支線上”，前測試點(diǎn)就是“下一塊石頭”，就是新的目標(biāo)點(diǎn)，對移動數(shù)字產(chǎn)生引力。

圖3　直線上的路徑

如圖4所示，當(dāng)前進(jìn)到向左轉(zhuǎn)向的拐角時，前測試點(diǎn)F和右測試點(diǎn)R將不在支線上，左測試點(diǎn)L在支線上。這時，把前進(jìn)方向由“向南”改為“向東”。向右轉(zhuǎn)向的拐角有類似的情況，把前進(jìn)方向由“向南”改為“向西”。

當(dāng)前進(jìn)到支線與干線的交匯點(diǎn)時，交匯點(diǎn)類似一個三岔路口或十字路口。前、左、右3個測試點(diǎn)中，至少有兩個會在干線或支線上。如圖5所示，左測試點(diǎn)L和右測試點(diǎn)R在干線上。

圖4　拐角的路徑

圖5　支線與干線的交匯點(diǎn)

下面要進(jìn)行干線上的路徑規(guī)劃，使移動數(shù)字沿著干線到達(dá)“終點(diǎn)支線與干線的交匯點(diǎn)”。由于到目前為此，這個坐標(biāo)還是未知的，所以，現(xiàn)在要先確定它。

確定“終點(diǎn)支線與干線的交匯點(diǎn)”的坐標(biāo)，方法與“起點(diǎn)支線與干線的交匯點(diǎn)”的確定過程是一樣的。從移動數(shù)字的終點(diǎn)開始，沿著支線反向推測，就可以找到它。這個過程中，不涉及移動數(shù)字的動態(tài)顯示，只找交匯點(diǎn)坐標(biāo)。

最后，在起點(diǎn)支線與干線的交匯點(diǎn)，與終點(diǎn)與干線的交匯點(diǎn)之間，建立起一條路徑。

干線是一個U型的內(nèi)部總線，采用極坐標(biāo)系的人式勢場法建立路徑。在U型內(nèi)部總線的內(nèi)側(cè)，任選一點(diǎn)作為極坐標(biāo)系的原點(diǎn)，U型內(nèi)部總線的開口方向?yàn)樽鴺?biāo)軸方向。如圖6所示。假設(shè)圖中A點(diǎn)是起點(diǎn)支線與干線的交匯點(diǎn)，D點(diǎn)是終點(diǎn)支線與干線的交匯點(diǎn)。極坐標(biāo)中A點(diǎn)的角度α小于D點(diǎn)的角度β，干線上的路徑就是從角度小的位置向角度大的位置前進(jìn)。沿著干線向下找測試點(diǎn)，直到拐角B點(diǎn)，轉(zhuǎn)向左找測試點(diǎn)，直到拐角C點(diǎn)，最后找到D點(diǎn)。

圖6　干線上的路徑

為了防止誤入支線，要事先確定B點(diǎn)和C點(diǎn)的極坐標(biāo)。當(dāng)測試點(diǎn)的角度小于B點(diǎn)的角度時，只向南移動。測試點(diǎn)的角度大于B點(diǎn)的角度之后，改為向西移動。當(dāng)測試點(diǎn)的角度大于C點(diǎn)之后，改為向北移動。

如果起點(diǎn)在左側(cè)，終點(diǎn)在右側(cè)，干線上的路徑就是從角度大的位置向角度小的位置前進(jìn)。方法類似。

到達(dá)D點(diǎn)之后，開始在終點(diǎn)支線上的移動。在終點(diǎn)支線上的路徑規(guī)劃與起點(diǎn)支線方法相同。

進(jìn)入終點(diǎn)寄存器后，寄存器中沒有靜態(tài)數(shù)字，沒有障礙物，移動數(shù)字在終點(diǎn)坐標(biāo)處的引力作用下，直奔終點(diǎn)，完成全部移動過程。最后幾個數(shù)字會受前面數(shù)字的影響。比如，移動數(shù)字為8個，前5個數(shù)字到達(dá)目的地之后，后3個數(shù)字需要避開它們。前5個數(shù)字相當(dāng)于后3個數(shù)字的障礙物，處理方法與起點(diǎn)寄存器類似。

2　移植到其他3D模型時的問題

2.1對于控制門位置的要求

由于移動數(shù)字在起點(diǎn)支線的初始方向要參照控制門的位置來確定，所以，在建立3D模型時，對控制門的位置有一定的要求。如果起點(diǎn)與控制門之間沒有拐點(diǎn)或者只有一個拐點(diǎn)，移動數(shù)字的初始方向的確定是沒有問題的。

如圖7所示，B處是不能安排控制門的。如果把A處的出口控制門安排在B處，同樣可以實(shí)現(xiàn)對“循環(huán)移位器”出口的控制。但是，在確定移動數(shù)字離開“循環(huán)移位器”的初始方向時，要根據(jù)“循環(huán)移位器”的出口坐標(biāo)E和出口控制門的坐標(biāo)B的連線來決定。這樣就把初始方向算錯了。這種出錯情況的一個特征是E與B之間有兩次相同方向的拐角。

圖7　控制門的位置

由于入口控制門要參與終點(diǎn)支線與干線交匯點(diǎn)的確定過程，所以，入口控制門的位置C也有類似的要求。

圖中C處的入口控制門是可以安排在D處的。雖然D處與入口坐標(biāo)F之間有兩個拐角，但這兩個拐角是不同方向的，所以不影響從入口逆推終點(diǎn)交匯點(diǎn)時的初始方向。在出口控制門也有類似的情況?？傊隹谧鴺?biāo)與出口控制門之間不出現(xiàn)連續(xù)的同向拐角，入口坐標(biāo)與入口控制門之間不出現(xiàn)連續(xù)的同向拐角，就可以正確確定移動數(shù)字的初始方向。

2.2測試點(diǎn)間隔的設(shè)定

在決定下一個局部目標(biāo)點(diǎn)時，要以一個相同的間隔分別向前進(jìn)方向的前、左、右3個方向設(shè)定測試點(diǎn)（比如圖4中的F、L、R 3個測試點(diǎn)）。測試點(diǎn)的間隔有一個合適的范圍，超出范圍會導(dǎo)致錯誤的測試結(jié)果。間隔不能太小，要大于3D模型中支線或干線的寬度。間隔太小會在支線與干線并沒有交匯時，也出現(xiàn)測試點(diǎn)多于一個的情況。間隔也不能太大，不能讓測試點(diǎn)落在另一條支線或干線上。

3　結(jié)束語

本文介紹了一個實(shí)現(xiàn)《微機(jī)原理》CAI課件時面臨的實(shí)時路徑規(guī)劃問題的解決過程。通過分段規(guī)劃的方法，減少了計(jì)算的復(fù)雜度，滿足了實(shí)時性的要求。實(shí)現(xiàn)的課件效果良好。同時，只要修改少量的參數(shù)，課件就可以適用于其它的一些類似的3D模型。如果3D模型差異較大，可能需要修改少量代碼。

［1］單建華.基于行為的實(shí)時路徑規(guī)劃［J］.控制工程，2009，16（3）：367_370.

［2］莊慧忠，李晗，陸震宇.動態(tài)不確定環(huán)境下移動機(jī)器人的在線實(shí)時路徑規(guī)劃［J］.計(jì)算機(jī)應(yīng)用與軟件，2011，28（2）：172_ 175，194.

［3］李天成，孫樹棟，高揚(yáng).基于扇形柵格地圖的移動機(jī)器人全局路徑規(guī)劃［J］.機(jī)器人，2010，32（4）：547_552.

［4］張彪，曹其新，王雯珊.使用三維柵格地圖的移動機(jī)器人路徑規(guī)劃［J］.西安交通大學(xué)學(xué)報(bào)，2013，47（10）：57_61.

［5］馮翔，馬美怡，施尹，等.基于社會群體搜索算法的機(jī)器人路徑規(guī)劃［J］.計(jì)算機(jī)研究與發(fā)展，2013，50（12）：2543_2553.

［6］吳乙萬，黃智.基于動態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法［J］.湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，40（1）：33_37.

Segmented Path Plannlng of lnteractlVe CAI courseWare

SU Wei_1ong
（School of Computer and Communication Engineering，Liaoning University of Petroleum&Chemical Technology，F(xiàn)ushun 113001，China）

In an interactive CAI courseware，a better teaching effect is achieved by responding user's input using program and demonstrating the process of change.A rea1_time path p1anning prob1em is invo1ved when an interactive CAI courseware is designed for the course of″microcomputer princip1e″.Through adopting different path p1anning methods in different stages according to rea1_time requirement of path p1anning，the comp1exity of computation is reduced，whi1e rea1_time requirement is satisfied.

path p1anningjrea1 timejCAIj3D mode1

TN709

A

1674_6236（2016）10_0058_03

2015_05_28稿件編號：201505248

蘇維龍（1965—），男，遼寧新民人，講師。研究方向：計(jì)算機(jī)輔助教學(xué)。