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

蘇維龍

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

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

蘇維龍

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

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

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

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

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

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

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

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

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

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

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

圖2　寄存器出口路徑

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

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

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

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

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

圖3　直線上的路徑

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

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

圖4　拐角的路徑

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

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

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

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

干線是一個(gè)U型的內(nèi)部總線，采用極坐標(biāo)系的人式勢(shì)場(chǎng)法建立路徑。在U型內(nèi)部總線的內(nèi)側(cè)，任選一點(diǎn)作為極坐標(biāo)系的原點(diǎn)，U型內(nèi)部總線的開(kā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)。沿著干線向下找測(cè)試點(diǎn)，直到拐角B點(diǎn)，轉(zhuǎn)向左找測(cè)試點(diǎn)，直到拐角C點(diǎn)，最后找到D點(diǎn)。

圖6　干線上的路徑

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

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

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

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

2　移植到其他3D模型時(shí)的問(wèn)題

2.1對(duì)于控制門(mén)位置的要求

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

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

圖7　控制門(mén)的位置

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

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

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

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

3　結(jié)束語(yǔ)

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

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

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

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

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

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

［6］吳乙萬(wàn)，黃智.基于動(dòng)態(tài)虛擬障礙物的智能車(chē)輛局部路徑規(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稿件編號(hào)：201505248

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