数理解析研究所講究録1093 巻 1999 年 242-247

242

移動ロボットによる長尺物運搬問題に対する分散アルゴリズム 1
A Distributed Algorithm for Carrying a Ladder by Mobile Robots
李春駒 (Chunyan Li)
九州大学大学院システム情報科学研究科 朝廣雄– (Yuichi Asahiro)
九州大学大学院システム情報科学研究科 山下雅史 (Masafumi Yamashita)
鈴木 –郎 (Ichiro Suzuki)
ウィスコンシン大学ミルウォ一キー校Asama)
浅間 $-$ (理化学研究所

九州大学工学部$\mathrm{H}\mathrm{a}\mathrm{j}\mathrm{i}\mathrm{m}\mathrm{e}$概要 :2 台のロボットを分散制御することにより長尺物を運搬する問題を考える. 理論的な最適移動時間から 101% 以内の遅延で動作可能な分散アルゴリズムが, 佐々木達によって提案されている. 本稿では彼らのアルゴリズムに対して, 移動時間の遅延を 72% に短縮できる改良法を提案する.

1はじめに近年, 工場や会社などではロボットが幅広く使われており, さらに高度な利用が期待され協調的に複数台のロボットを動作させることにより, 単体のロボットでは出来ない作業の遂行が可能となることもある. 協調問題の 1 つとして, 複数台の移動ロボットによる物体運搬の問題があり, 大きく分けて, 自律分散制御 [1] と 1) 一ダー追尾型制御 $[2, 3]$ による解決方法が考えられている. 本稿では, 2 台のロボットを分散制御することにより, 橋やている.

ロケットのような長尺物を出来るだけ短い時間で目的地まで運ぶ長尺物運搬問題を扱う.
または最大速度 $V$ のいずれかであるという仮定のもとでロボットの最適動作の軌跡を計算し, その軌跡を各ロボットに与えるという形でこの問題を解くことができる [4]. しかしながら, このいわゆる集中型の解法は以下の 2 点から, 実ロボットのアルゴリズムにはそぐわない. (1) ロボットの速度が最適制御理論を用いることにより, 各ロボットの速度は$0$から急に $V$ になることはなく, また (2) ロボットにはセンサーエラーや制御エラーが存在するために, あらかじめ決まった軌跡に沿ってロボットが動くことはない. これらの問題点を解消するために, 分散制御を用いることが考えられる.
分散制御では各ロボットが現在地と目的地の位置から動的に動作を決定し, 移動や位置に$0$関して多少の誤差が含まれていても徐々に目的地に近寄っていくようなアルゴリズムを実現することができる. そのため, 実際的見地からは分散制御の利用価値は高いと思われる. しかし誤差や故障に対してうまく動くことが保証できても, 運搬に要する移動時間といった性能が著しく悪化するのは避けなければならない.
分散型長尺物運搬アルゴリズムとして, [4] により求められる最適移動時間から 101% 以内の遅延で動作可能な分散型アルゴリズムを佐々木達が提案している [5]. 本稿ではこのアルゴリズムの改良について述べる. 本稿のアルゴリズムは最適移動時間に対して 72% 以内の遅延で動作し, 遅延時間が 29% 改良されている.
1 本研究の-部は文部省科学研究費補助金 No 10205221 と No 09680342, National Science Foundationの補助を受けて行われた.
IRI-9307506, Office of Naval Research No$.\mathrm{N}0001\not\subset 94^{-}1^{-}0284$

243

2長尺物運搬問題とアルゴリズム

21 長尺物運搬問題
2 台のロボットがそれぞれ棒の両端を持って目的地まで時間最適で運ぶことを考える. 2と目的地 $a’,$ ’ が与えられるものとする (図 1 参照). 図中台のロボット $A,$ の出発地を で表している. 長尺物運搬問題は与えられた出発地をから目的地 $a’,$ ’は$B$$A$$\mathrm{O},$$B$$a,$$b$$b$$\bullet$$a,$$b$$b$まで, 最短時間で棒を運ぶ問題である. ここで, ロボットは全方向移動可能とし, 最大速度は $V$ とする.

目的地まで長尺物を運搬するのにかかる時間を移動時間と呼ぶ.

図 1: 長尺物運搬問題の例.

22固定回転アルゴリズム

文献 [5] で提案されたアルゴリズムを紹介する (図 2 参照). 以下ではこのアルゴリズムを固定回転アルゴリズムと呼ぶことにする. 2 台のロボットのうち現在地から目的地までの距(図中屋) はで目的地に向かって移動する. ただし,離が長い方のロボット$V$ である.
(南中 ) は 3 つのベクトル $varrowarrow$ の合成
もう 1 台のロボットのはと垂直方向の向きを持ち, 大きさ方向に速度 $V$ で移動する. ここで,はの速度と平行方向の向きを持ち, 大きさ回転ベクトルである.
$|\vec{V}|=$$\vec{V}$$R_{fa\Gamma}$$\bullet$$R_{n\mathrm{e}a\Gamma}$$\vec{v}_{t}ound$$V_{p}\prec a\mathrm{r}ale\iota$

ベクトルである. ただし,$0\leq c_{1}$, c2$\leq 1$$v_{r\text{。}un}d,$$c_{1}V$$c_{2}\cdot|\vec{V}arall|p\mathrm{e}$$\overline{AB}$をの速度ベクトルはアルゴリズムのパラメータである. ベクトルげは$\vec{V}_{pa\gamma}an\mathrm{e}\iota$

は$v_{\mathrm{p}}a\gamma al\mathrm{e}\iota,$$\overline{AB}$$\dot{V}$$\overline{AB}$$R_{fa\prime}$

向きを持ち, 大きさ $V\cdot d_{nea}’/dya$ ’ の速度ベクトルである.

,に射影したものであり,$R_{nea\mathrm{r}}$$d_{J^{a\prime d_{n\text{。}a}}\prime}$

れの目的地までの距離を表す.

図 2: 固定回転アルゴリズム.

はが目的地に向かう

Rfaf’$Rn\mathrm{e}af$

それぞ244

このアルゴリズムはおおよそうまく動くが, 以下の点で改良の余地があると考えられる.
は, 現在の目的地まで移動する間に, 棒の傾きは少しずつ変化する. 回転ベクトル$\vec{v}_{t\text{。}und}$

棒の傾きを目的地の棒の傾きと -致させるように, 棒を回転させる作用を持つ. 従って, 目を与えること的地の棒の傾きと現在の棒の傾きの差に応じた大きさの回転ベクトルができれば, うまく棒を回転させることが出来るように思われる. しかし, 固定回転アルゴの大きさは不変なので, この大きさが棒の傾きに対して適切でない場合
リズムではにはうまく回転させることができず, 移動時間が長くなる原因の 1 つとなると考えられる.
$v_{1\text{。}und}arrow$$v_{round}arrow$

2.3

可変回転アルゴリズム

回転ベクトルの大きさが可変のアルゴリズムを提案する. このアルゴリズムを可変回転アルゴリズムと呼ぶことにする. 可変回転アルゴリズムは,の大きさを定数 $c_{1}V$ からは目的地と現在地に変更する以外は固定回転アルゴリズムと同じである.
$v_{foun}d$

変数の棒の傾きの差を表す (図 3 参照).
$c_{1}V\cdot\psi/\pi$$\psi$

図 3: 可変回転アルゴリズム.

3

シミュレーションにおけるロボットの動作に対する仮定

固定回転アルゴリズムと可変回転アルゴリズムを比較するためのシミュレーション実験を行った. シミュレーションでは, ロボットの移動に関して以下の仮定を置いた (図 4 参照).
ロボット $A,$の現在地をそれぞれ , とし, アルゴリズムによって与えられるベクトルに$B$$e^{f}$

従って移動しようとする位置をそれぞれ $e’,$ $f$ ’ とする. ロボットは棒で固定されているので, 必ずしも $e’,$ $f$ ’ に移動出来ないことに注意する. このような無理な動きを禁止するために, ロボットは棒から受ける力に対してフィ $-$ ドバック制御を行ない, 両ロボットの間隔が棒の長さと常に等しくなるように保つことが-般的である. 実際のロボットがどのようなフィ一ドバックの制御を行なうかは個々のロボットにより異なるが, 本稿ではこのフィ一ドバックの影響を以下のように仮定する. 位置 $e’,$ $f$ ’ に移動しようとした両ロボットは $e’,$ $f$ ’
は棒の長さでの重心 $G$ からそれぞれ $L/2$ ずつ離れた位置 ”, $f$ ” に移動する. ただし,$e$ある.

$L$

245

$e$”

$. \mathrm{x}_{:}’..\backslash G\sqrt[\prime]{}/^{\mathrm{I}}:’\bigwedge_{\backslash }\backslash \backslash \iota L/2\Leftrightarrow$”I$e$$\iota,,\backslash /f\vee’r/^{\iota}L2$$f\downarrow,$,
図 4: 移動の仮定.

4$-$アルゴリズムの評価

回転ベクトルの大きさを可変にすることの効果について考察するため, 回転ベクトルによる影響が大きいと考えられる回転移動の場合について実験を行った (図 5 参照). ロボット
B(図中の ) の出発地 と目的地 ’ は同じ位置にあり, ロボット A(図中の O) の出発地と目的地をそれぞれ と ’ とする.
は回転角である. 本シミュレーションでは棒の長さ $L=$$100$ , 最大速度 $V=1$ とする.
ロボットが最大速度で移動する場合, 目的地に着くまでに通った距離 (を $V$ で割ったもの) が移動時間になる.
をからまでの範囲で刻みで変化させて実験を行い, 可変回転アルゴリズムによる移動時間を (Chen 達の仮定のもとでの) 最適時間及び固定回転アルゴリズムによる移動時間と比較する.
$b$$\bullet$

$a$

$b$

$a$

$\beta$$V$$\beta$$0^{\mathrm{o}}$$180^{\mathrm{o}}$$5^{\mathrm{O}}$

図 5: 棒の回転実験.

固定回転, 可変回転の両アルゴリズムは , c2 という 2 つのパラメータにより動作が決められる. そこで, これらの値は から 1 まで 0.1 刻みで変化させて実験し, 移動時間が最短となる値を用いた. 具体的には, 可変回転アルゴリズムでは $c_{1}=0\cdot 7,$ $c_{2}=0\cdot 5$ , 固定回転アルゴリズムでは $c_{1}=0\cdot 4,$ $c_{2}=0.5$ とした.
が小さい時には, 両方のアルゴリズムとも$c_{1}$$0$$\beta$が十分に最適値に近い移動時間で動作し, 差がほとんどないので,からの範囲の結果だけを表 1 に示す. 例えば, 表 1 の可変回転アルゴリズムの $\beta=1800$ の時の結果
222(7.2%) は移動時間が 222 であり, 最適時間 207 に対する遅延が 72% であることを意味する.の時に固定回転, 可変回転両アルゴリズムともに最適時間に対する遅延が$\beta$$\beta=180^{\mathrm{O}}$$155^{\mathrm{o}}$$180^{\mathrm{o}}$246

最大となり, それぞれ 101% と 72% となっている. 回転ベクトルの大きさを可変にすることによって, 遅延を 29% 減らすことができた.の時の最適軌跡, 固定回転及び可変回転アルゴリズムそれぞれの軌跡を図 6, 7,
8 に示す. すべての軌跡は, ロボット $A$ はなるべく目的地に向かって直進し, –方, $B$ は一度目的地から離れて再び目的地に戻っている. しかしながら, $A,$ $B$ は共に最短距離を$\beta=180^{\mathrm{o}}$移動することがなく, 互いに譲り合いながら,うまく全体としての (準) 最適動作を実現していることが理解できる.

図 6: 最適な軌跡.

図 7: 固定回転アルゴリズムの軌跡.

図 8: 可変回転アルゴリズムの軌跡.

247

5

おわりに本稿では長尺物運搬問題に対して, [5] のアルゴリズムを改良した可変回転アルゴリズムを提案した. 本稿のアルゴリズムを用いることで最適時間に対する遅延を減らすことができた.

本稿ではシミュレーションにおいてフィードバック制御に対して 4 節で述べた事柄を仮定したが, その結果として, 与えられた最大速度よりも大きい速度でロボットが移動してしまうことがあった. そこでフィードバック制御に対して, より現実的な仮定をおいた研究をすでに開始している [6]. ロボット数を 3 台以上へ拡張することや, 作業場の障害物への対応などは今後の課題である. 本研究が対象とする全方向移動可能ロボットは理化学研究所で開発されており [7], アルゴリズムをこれらのロボットに実装することも考えている.

参考文献[1] N. Miyata, J. Ota, Y. Aiyama, J. Sasaki, and T. Arai, “Cooperative transport systemwith regrasping car-like mobile robots,” Proc. $IEEE/RSJ$ Int. Conf. on IntelligentRobots and Systems, 1754-1761 (1997).

[2] K. Kosuge and T. Oosumi, “Decentralized control of multiple robots handling an object,” Proc. $IEEE/RSJ$ Int. Conf. on Intelligent Robots and Systems, 318-323 (1996).
[3] Y. Nakamura, K. Nagai, and T. Yoshikawa, “Dynamics and stability in coordinationof multiple robotics mechanisms,” The Int. J. of Robotics Research, 8,2,44-60 (1989).
[4] Z. Chen, I. Suzuki, and M. Yamashita, “Time optimal motion of two omnidirectional
robots carrying a ladder under a velocity constraint,” IEEE Trans. Robotics andAutomation, 13,5,721-729 (1997).

[5] Y. Sasaki, I. Suzuki, M. Yamashita, and H. Asama, “Distributed strategies for twoomnidirectional robots carrying aladder,” 1997 年第 15 回日本ロボット学会学術講演会, 881-882 (1997).
[6] Y. Asahiro, H. Asama, S. Fujita, I. Suzuki, and M. Yamashita, “Distributed algorithms for carrying a ladder by omnidirectional robots in near optimal time” (toappear).
[7] H. Asama, M. Sato, L. Bogoni, H. Kaetsu, A. Matsumoto, and I. Endo, “Developmentof an omni-directional mobile robot with 3 DOF decoupling drive mechanism,” Proc.
IEEE Int. Conf. on Robotics and Automation, 1925-1930 (1995).