計測自動制御学会東北支部帯179匝】研究集会（1g98．12．14）
資料番号179−5

Bスプラインによる移動ロボットの動的障害物回避軌道の設計
DynamicPathPlanningBased onB−SPline Curve

Considering ObstacleAvoidance丘）rMobileRobots○債田尚九王志東，高橋隆行中野栄二
OTakahiroYokota，Zhi−DoI唱WaIlg，Takay11kiTakahashi，EijiNakano
東北大学

TnholくuUIlivers恒r
キーワード：自律棒動ロボット〔autonomoll＝TehicIcrobot）．軌道生成（traje［＝tOry肝neration）7
障害物b］避（ob呂taCleavoidance），スプライン曲線〔叩Iirtccurvc）

連棉先：〒9呂0一鮎79 仙台市青葉匡荒巻字青葉（〕1東北大学大学院情報科学研究科中野研究室
横田尚九Tel∴（n22）217−7025，抽Ⅹ・：（022）217−7023，

E−mail：takahiro㊥roboti⊂畠．is．tohoku．a⊂．jp

吏性．を有する軌道生成法を提案し，実環境におけ1． はじめにるリアルタイム障害物回避軌道の設計法を提案す

移動ロボットが莫環境において走行することをることである．ただし，ロボットはvision等によ想完すると，ロボットの持つ地区＝電報にはない，り，ある範囲内でなら障害物全体の・大まかな位置

椅子などの静的な障害物，あるいは人などの動的と形を認識できるものとし，その範囲は障害物回な障害物が存在することが多々ある．このような避に十分な距離とする．想定する状況は，ロボッ

環境に移動ロボットが適応するためlこは，軌道のトは地図情報をもっているが，地図情報にはない空間的および時間的な局所変更性が要求される．

静的な障害物が存在する2次元平面を克行するもこのため，ロボットの軌道計画を，環境モデルをのとする．

もとにして，目的地へ至る経路を決定する大域的な計画と，計画された鮮措から某際に移動機構

2．経路および軌道計画を制御するための軌道データを作成する局所的な

まず，障害物が存在しない環境下における経軌道生成とに分けて考える．ここで，経路とはロ路および軌道の生成法を示す．

ボットが空間内で通過する道筋を表L，軌道とは2．1経路・軌道に要求される曲線の性質

ロボットの位置，速度，加速度の時間的な履歴を意味する．つまり，経路設計においては時間的な経路および軌道に要求される曲線の性賓とL拘束は含まれない．て，（1）局所変更が可能，（2）曲線長に関する微分本研究の目的は．空間的および時間的に局所変可能性が任意に指定できる，（3）演算が高速にで−l−きることなどが挙げられる．ユニフォームなBス

志される，凶1に3次のBスプライン曲線におけプライン曲線はこのような要求を満たすため，こる削御点q．才とノット点巧の関係をホす・の曲線を用いて経路および軌道を生成する．
● ConlroIP亡Iimt

2．2 ユニフォームなBスプライン曲線

O lくmlItPIIillt′ヽSplh亡Curve

ユニフォームなBスプライン曲線は，与えられる制御点を拍0，ql，・t・，吼1，曲線パラメータを薫とすると，−1P（り＝∑qj月誹〔f）〔土∈【0，和一た十1］）j＝0として定義できる・ここで基底関数巧誹〕はた囲1鮎IationbetweeIIQj，巧a・ndBrsplinc仁tlrVe

次の多項式であり次式で定義きれる．
た＝1の場合コ．3 程路設計≦青くち＋1）JJJl出・ミ∴ ご二丁〔上記以外）

経路設計では，GIub孔1な制御点でロボットが通た＞1の場合過する道筋を大域的に計画する．ここで，時間的壬−fj

戦ト1（f）月j誹）

な拘束は含まないことを注意しておく．ロボット

ち＋た一ち
ら十た＋l一書の経路は車体の位置および姿勢の空間的変化であ

卑汁1，た・1〔≠）

土汁た＋1一吉井1るので，それをP（占）＝【巾），訂（β），町用rのよう

なお，ちはノットであり，ノットベクトルrは，に表すと，P〔占）は・托＋1個の制御点切により，
門．

r＝［fo，壬1，…，fm＋頼1］＝トた，−（た−1），‥・，m＋1】

P（β）＝∑Qj早津（方）（占∈【0，陀−た＋1］）
j＝0である．パラメータまの変化によって位置ベクトのように表せる．ニこで，占ほ曲線パラメ」タでルPは曲線を措くが，￡が隣接するノット間を変ある．

化するときに生成される曲線の部分は曲線セグメ

2．4 I」OCalな制御点の算出法

ント， ノットに対応する曲線上の点はノット点と呼ばれる．まが0≦t≦丁もーた＋1の範囲で変化

大域的に計画された経路から実際に移動機構をするとき，Pは連続する几−た＋1慣の曲線セグ制御するためのLocaIな削御山を算出する方法につメントから構成される．この曲線はた−1次の導いて述べる．次の節で述べる単位運動により．ロ関数まで連続となり，連続するた＋1個の制御点ボットが経路上を単位時間で移動する距離毎にLo−のみにより定義され，連続するた＋1偶の制御点ca1な制御正を打っていく必要がある．これには．の凸包領域に存在する．このため，制御点を変更

時間に対する速度グラフをもとに，解析的にLocal

した場合，その影響は曲線全体には及ばず，局所な制御点を算出する方法が知られている1）．Lか的に曲線を変更することができる．以下では曲率し，この方法では演算量が多くなってLまうのでまでの連続を考慮し，3次のスプライン曲線を対リアルタイム制御には過さない．そこで，次のよ象とする．このとき，各曲線セグメントは4個のうにしてLo亡alな制御点を求める．すなわち，Lo−連続する制御点拍j−1，qj，q打1，吼十2＝こより決calな制御点をGlobalな制御正閏の曲線パラメー−2

タざを「d／ロ1分割して求められる曲線卜の点とここで，関数Ⅳ毎（り，…，〃帰（りは以下のようするものである．ここで，dはGlobalな制御点間に再帰的に定義される関数である．
ヽJ1．▲一レ

た二J十壬︑−■11ハLⅣ︼

L叫lrレ∩

一一丁舟二叫，た〔り＝﹁⊥二⊥レ

L口CaⅠな制御点の関係を示す．

l

ヽ11一 −

爪・ナし＼I−J−．

鞠︑−111 1︐たが移動する距離である．図2にGlnb且1な制御点とーl〜∧Uのユークリッド距阻 刀は単位時間でロボット

叫−1，た＿1〔り乃木1（f）〔j＝l，2−‥㍉た−1〕
士

朗如何＝ALl打（り山はβた（りにおける変数fを縮尺するための止定数スカラーであり，山の逆数を単位時間r甲と定義すると℃p。はノット古間の移動時間を表すパラメータとなる．
また，境界条件として，＝伽1 ＝恥ヴ1‡ヴ几「−た＋1 ＝＝恥r1 ＝恥r

岡2 RelatioIlbetwcenGloba．landLocalPuirltS のように，移動開始時および惇山時に経路点をた個重ねることにより，ロボットは滑らかに運動を開始L，滑らかに運動を停1Lすることができる．

コ．5 単位運動による軌道生成

単位運動による軌道生成の具体例を示す．図3はデカルト座標系において設計された経路を表高‖lら2）によって提案された単位運動による移動ロボットの軌道生成の概要について述べる．

Lている．丸印はlocalな制御山を表Lており，この手法において，ロボットの位置および姿勢の始点と終山においては多重頂点になっている．同

軌追は，正規化された一棟なB−スプライン関数

4は生成きれた軌道仕方向）を示しており，軌道を重み付けし，それを時間軸についてずらLながは時間軸i・こ対して，単位運動を重ね合わせて牡鹿ら南ね合わせることによって生成される．軌道はされていることがわかる．

ロボットの位置および姿勢の時間的変化であるので，それをp（t）＝［項）拍車〕，叩）】Tのように表すと，p（りは比卜のように生成される．
ip（f）＝∑鮎＋叫鶴（」小一り）（f印盲，f叫］）
j＝よ−た

ただL，郁＝［茸盲コ恥βj】は，Localな制御1■王である・月た（申土，基底関数月j誹）が曲線パラメー…

タ≠に対Lて水平方向に平行棒勤した関係にあることに着目し操作された式で，以下のように定義

仇50 1．00 1．50

される．

Ⅹ［m】

「珊卜津（ト．才）（J≦f＜j＋1，J二0，1，・・・，可図3 PathgenefatedbyUnitMotiollS〔fく01た＋1≦吉）−3−

3．2 衝突物との衝突判定

l．50

頂点の座標がわかっている障害物に対し，設計Lた経路が障害物に衝突Lていないか判定する必要がある．確実判定を高速かつ任意の精度で行う方法を述べる．ニの方法は，Bスプライン曲線

セグメントをBe壷r曲線の制御点で表L，B郎icr曲線を甜分割していくことにより実現される．
ーユ．仰I肌朋D：封M 4．剛l后．00 乳00
Time【s］

凶4 Traje亡tOrygCneratedbyUnitMotions

Beziur曲線は制御点に対L凸包性をもち任意に細分割できる曲線である．
3．2．1Ⅰ】eEierによるBスプライン曲線の表現法
3次のBスプライン曲線の制御点

3．障害物回避経路の設計
ロボットが走行中，静的な障害物を検知した
場合の障害物回避経路の設計法を述べる．ロボッ†qjTlっqj，Qj＋1，qj＋2‡により定義されているBス

プライン曲線セグメントを，Bezier曲線の削御点‡Qら1ql，qち，qら）で表現すると，次式が成り1トニつ・．qJ．7J

十．勺J＋細汁1

十1

O．ロ．q

−．1J

十1ぷ︑廿ト．れ．7J﹂

＋拍j十2

O−

1一亡U2一31一31言U

叩叩／qリ1ある．以下．障害物の表現法，衝突判憩乱 衝突回避法について順次説明Lていく．

＋叩

1リム

害物との衝突を国選する経路を再設計する必要が＋∵′﹁1いないか判断L，もし衝突しているなら動的に障︷＋／nU

ロ．〇：U二日

トはあらかじめ設計した経路が障害物に衝突して幾何的関係を岡6に示す・3辿qゴ1吼，q．jQ汁1，3．1 障害物の表現法
ロボットを慮とみなすことができれば，障害物回避経路の設計は容易になる．そこで，障害物に村し以下のような操作を行い．最終的に得られたものを障害物とみなL，障害物の頂点の座標を求めておく．操作の過程を国5に示す．
1．障害物を凸包で表現する．

図6 RelatioIlbetweenB−Splinc sControIPointF；and B（二Zicr）s ControIPoints

2．ロボットをい1筒近似し，1で得られた障富物にその円筒の半径分だけ障害物を拡大する．
qj＋1亡わ十2

3．2で得られた障害物を凸多角形で近似する．

をそれぞれ3等分すると上辺Q．7・Q．7・＋l

上で吼に近い等分点が別，また吼＋1に近い方の等分山が鶴となる．辺吼1吼上で吼に別画調「近い等分点とqiとを直線で結び，その線分の中点は柵線セグメントの始点で郁となj一丁，また辺吼H吼購・卜で吼＋1

凶5 ExpressionofOl）StaCleに近い方の等分点と留らを直線で結び，その線分の中点は曲線セグメントの終点でqちとなる．このように，Bスプライン曲線

●㈲セグメントをBeヱicr曲線の制御点で表現すると，曲線の存在する領域をより限定することができる．また，BeE壷r肝【棟を細分剤することにより，さらにその領域を小さくすることができる．
3．2．2 衝突判定アルゴリズム
衝突判定は以下の7ルゴリズムにより行う．
躍感Jr曽

1．軌道データをもとに移動しているロボットが叡障害物を検知する．
2．Lora・1な制御点を用いてBスプラインの凸包性を利用した衝突判定をする（図7（a））．衝突Lていないなら7へ進む．
3．Be扇erの出色性を利用Lた衝突判定をする（岡7（b）〕．衝突していないなら7へ進む．

4．凸包領域の面積が開値以下なら6へ進む．
●B−Splin巳亡bIltrOIPoiml

5．B錯ierを甜分割し凸包性を利用Lた衝突判定

静］臥相加rC（lmlr山Poinlをする 洞7（瑚．衝突しているなら4へ戻

Subdivisi山ntdE仁王ier

る．衝突Lていないなら7へ進む．

C（l¶lrl）】Point

6．衝突していると判断L，障害物と衝突Lた極槙を記憶Lておく．
7．衝突していないと判断する．
●●

3．3 衝突回避アルゴリズム

図7 CILaShJud酢I11eIltAlgurithrIl
経路と障害物が衝突Lている場合，障害物を回避するような程路を再設計する必要がある．衝突回避には，図8に示すように，衝突領域に対X Cr鮎hIIqinl

L，制御点のシフトやあらかじめ用意Lている形● Bっp］ineCoTltrOIPoillt
O D亡l亡t亡dP￠i山l叫円・楕円）のあてはめなどが有効であると考えられる．Lかし，これらの方法は，過剰回避が問題となると思われる．そこで，Bスプラインの逆変換を用いた障害物の最小回避経路の設計法について述べる．

5

図呂 ExaIIlpl恍〔）rObstacIcAvoidarlCC

3・3．1Bスプライン曲線の逆変換（a）●3次のBスプライン曲線のノット点（h）●●伽彗（五＝1，2，…，m−1）が与えられて，制御点吼（J＝1，2，…，m〕を求める過密換について述べる．曲線パラメータが整数のとき，次の連立方程式が成り立つ．

損十臣射＝榊この連立方程式は未知数に対L条什数が二二つ少ないので，通常，両端の制御点を多重頂点（曲線の両端の曲率を0とする）とすることで，未知数と条件数を一致させることにより，解くことができる．ただL，この両端の制御点に関する条件設定は任意に決定できる．
X Cr且ShPoiml● Ⅱ−Sp】illeConlr山PDim一

3．3．2：師突回避アルゴリズム

口 Ⅴ亡rteXOrObs由仁l亡A EnoIPoint

衝突回避アルゴリズムは障害物との衝突に寄O Del亡tedl10int

与した制御点の両端点を結ぶ親分が障害物と交わる場合と交わらない場合で分類される．それぞれについて，順次説明Lていく．
（Ⅰ）交わる場合のアルゴリズム（Ca胱1）●

1．障害物との衝突に寄与Lた机御点仇と障害

同9 nbstacleAvoidaIICe（C甜北1）

物の原山を用い，障害物に対L凸包を求める（園9（乱））．
2．1．で求めた凸包卜の瓜をノット点とし逆蛮換（a）●する．ただし．条件設定として，逆変換される両端の制御点を障害物との衝突に寄与−Lなかった両端の制御点軌と 一致させる（囲9（b））．
3．2．で求めた制御点と衝突に寄与しなかった制御点を用い，経路設計をする〔同9（c〕）．
〔ⅠⅠ）交わらない場合のアルゴリズム（Case2）

1．衝突に寄与Lた制御点仇の両端山を桔ぷ線分と障害物の頂点との距離が最短である煩点
X CradlPoi巾tを求める 個10（a）〕．

● 8一再pIineCIInlro‖チoimt

2．1．で求めた頂点と衝突に寄与した制御点の両［コ Ⅴ亡r【亡Ⅹ巾ー（lhsl且亡l亡

0 山elel亡dl｝oimt

端点と衝突に寄与しなかった制御点を用い，経路設計をする 個10（b ．

図10 0bstacle」11rOi血ncc（Case2）

6●qb4． 由わりに
日律移動ロボットの空間的および時間的に局所変更件を有する軌迫生成法を提案し，障害物回避経路の設計法を示した．今後ほ，本研究で提案Lた手法の有効性を実機を用いて検証するとともに，単位運動においてより有効な制御点の選定法を検訂する予定である．

参考文献l〕B．Guellt・eran（1R−Parcnt：ComputiI唱theArc

Ler］gthofParametri仁CllrVeS，IEEEComputer
Graphics＆Applica扇DnS，72／7邑（1990〕
2）高山，狩野：運動の単位に基づくロボットマニピュレータの連動制御．計測自動制御学会第3回
ロボット工学部会研究会資札1／10（1987）

3）森善一：非ホロノミツタな全方向移動ロボットの機構およぴその制御に関する研究，東北大学大学院情報科学研究利一博士学位論文，（1998）
4〕山口富】二夫：コンピュータディスプレイによる形状処理丁二学［11］，69／177，日下lは業新聞社（1992）

5）小森谷．谷汀：スプライン曲線による車輪型移動ロボットの軌道制御，日本ロボット学会誌，昌一2
133／143（199U〕

7