自律分散型移動ロボットの協調繰り返し搬送における役割分担○里悠太（東京農工大学） 小林祐一 （東京農工大学／理研 RTC）

Division of labor by decentralized mobile robots in cooperative
iterative-transportation∗Yuta Sato (Tokyo University of Agriculture and Technology)，Yuichi Kobayashi (Tokyo
University of Agriculture and Technology/RIKEN RTC)
Abstract– This paper deals with a framework of decentralized approach to division of labor by multiple
mobile robots. An iterative-transportation task by multiple robots with multiple sets of starts (pick-up placeof the object) and goals (put down place) is considered as the task. On each route between a start and agoal, the eﬃciency of transportation improves when the number of robots increases. Due to jams, however,excessive number of robots on the same route causes ineﬃciency. We propose a control law of each robot
to choose an appropriate route so as to optimize the total eﬃciency of the transportation, where each robot
utilizes information which can be obtained only by local observation (without any explicit communication
among robots). The proposed control is based on the estimation of the number of robots on the routes. In
the simulation, it was veriﬁed that the proposed control law realized the similar level of the eﬃciency byappropriately choosing the route, compared with the case where global information can be utilized.
Key Words: division of labor, decentralized autonomous system

1

はじめに群ロボットシステムの適応能力や柔軟性を改善する目的で，分散制御による仕事の分業や役割分担について多くのの研究がなされている．分散制御は，故障やシステムの変更といった環境の変化に対して柔軟に対応できるシステムを構築するという利点を有する．
淺間らは，複数の自律型ロボットが並列的な行動及び協調行動によって作業を行う場合を想定し，作業分担を自律的に，かつ分散的に決定する手法を開発した
1)．具体的な問題として荷片付け作業を例に取り，通信を用いることで作業状況や各ロボットの状況を分散的に管理し，状況応じて協調行動をするアルゴリズムを提案し，シミュレーションにより提案手法の妥当性を検証している．ここでは，通信によって全てのロボットの状態を把握するという仮定の下で研究を行っているが，ロボット数が多ければ処理のための計算量は多くなり，全てのロボットの状況を完全に把握することが難しくなる．本研究では，通信を用いず各ロボットが得る局所的な情報のみを用いた分散制御の実現を目指す．
Mizuguchi et al. は，複数ロボットへの仕事割り当ての手法として確率的オートマトンを用いた比率制御法を提案している 2) ．複数の状態 (仕事) に割り当てられる個体の数に最適な比率が存在するものとして，状態の遷移確率に従って各個体が状態変更をすることで各状態の個体数が目標とする比率になるというものである．状態間の遷移確率を一定とした手法と個体間の相互作用により変化する動的な遷移確率を用いる手法提案し一定の遷移確率によるものと比較している．仮想フェロモンによる情報伝達を行う自律ロボットを用いた検証実験を行い，手法の有用性を確認している．しかし，比率による仕事の分担は有用であるが，作業効率がロボット数に依存して決まる問題では常に良い結果が得られるとは限らない．本研究では，作業効率がロボット数に依存して決まる問題について必要なロボット数を局所情報から推定して行動の選択を行うことでシステム・情報部門学術講演会2009(2009年11月24日～26日・神奈川)

作業分担を行う．
吉村らは，群ロボットによる多数物体の繰り返し搬送作業効率よく行うための搬送アーキテクチャを提案している 3) ．この研究では搬送を経路の生成と搬送形態の獲得という 2 つのサブタスクに分割することにより，搬送効率の向上を実現している．この研究では搬送作業を作業の組み合わせによる階層的なものとして扱っているが，本研究ではすべてのロボットが荷の搬送という同一の作業を並列的に行う場合について考えた．
本研究では，複数の目標への繰り返し搬送において複数のロボットの協調行動により目標への経路が単一な最適経路となっているとする．各ロボットは通信を用いることなく，局所情報のみを用いて経路全体の搬送効率を最大化するような各経路の最適なロボット数を推定し，各ロボットが最適ロボット数となるように経路選択をすることで経路分担を行う．この搬送効率を最適化する分散的な制御による経路分担を行うことが本研究の目的である．

2問題設定

本研究では，複数のロボットがスタートと 2 つのゴールの間で繰り返し荷の搬送を行う問題を扱う．このような搬送問題は，一般には集中管理的な手法で扱われる問題であるが，著者らは，Cheng et al. の局所追跡
アルゴリズム 4) を自律分散型ロボットに適用することで，分散制御でこの問題を扱うことを可能にした 5) ．局
所追跡アルゴリズムとは，アリの採餌行動における経路最適化のモデルから想起された一般的な最適制御問題の解法である．これは，エージェントが群を成して目標へ向かうような状況において，個々のエージェントが前方を進むエージェントを追跡することによって局所的な軌道が最適化され，群全体で追跡行動を繰り返すことで徐々に群全体の成す経路が最適化されるというものである．このアルゴリズムを障害物回避やロボット同士の衝突回避といった問題を考慮してロボットに適用することで，十分に時間が経過すればロボットのとるスタートとゴールの間の経路は障害を避けた- 302 -SY0012/09/0000-0302 (c) 2009 SICE最適 (最短) なものに収束する．この動作例を Fig. 1 に示す．Fig. 1 において，Robo(1) は 1 台目のロボットの経路であり，初期経路を示しており，2，3，7，15 台目と後続のロボットになるにつれ経路が最適化されていることが分かる．
本研究では，局所追跡によってスタートと 2 つのゴールの間の最短経路が求められており，各ゴールに対する経路は 1 つに定まっているものとする．2 つの経路をそれぞれ Route1，Route2 とする．各ロボットは相互通信を行わず，それぞれの得る局所情報のみを利用して経路選択を行う. 各ロボットが持つ情報は，以下の二つである．

20151050-5-10
Robo(1)
Robo(2)Robo(3)Robo(7)Robo(15)-15• Route1，Route2 の経路長：L1 ，L2-20-15• 前方を進むロボットとの距離：d (i = 1, 2, · · · は各ロボットの ID)-10-5051015(i)Fig. 1: Cooporative iterative-transportation.
20velocity
速度(A*tanh(x- a) + A*tanh(a))

この条件での繰り返し搬送における経路分担を，以下の仮定が異なる 3 つの場合に分けて考える．

case 1
各ロボットはリアルタイムで各経路上の正確なロボット数を知らされている (集中管理型制御の場合)．
case 2
自身が現在いる経路のロボット数の推定し，もう一方の経路のロボット数は未知として経路選択を行う (分散制御の場合)．

15105001

234

前方との距離distance between
robot and its forward robot

5Fig. 2: A velocity model.
case 3
1 度通った経路上のロボット数を記憶することで経路全体のロボット数を推定して経路選択を行う(分散制御の場合).
この 3 つの場合において，case 1 は理想的な経路分担を行う場合であり，本研究では case 3 のもとで case 1の結果に近づくような手法を提案する．

2.1 速度モデル
ロボットの速度には上限があり，他のロボットに近づきすぎた場合停止することで衝突を回避するものとする．この速度モデルを，速度が最大・最小となる近辺では徐々に速度を調整するような以下の非線形な関数で定義する．
V (d(i) ) = A tanh(d(i) − a) + A tanh(a)(1)

A，a は正の定数．この速度モデルのグラフを Fig. 2 に示す．この速度モデルは，渋滞学の研究で車の速度モデルとして用いられる OV(Optimal Velocity) モデル
6)と呼ばれるもので，ロボットが過密になると渋滞状態になり，経路内のロボットの移動効率が悪くなるという特性を持つ．この速度設定により，搬送作業に必要なロボット数が定量的に定まるものとして考えることができる．
2.2 ロボットの隔均等間隔配置への収束平面上の同一線形システムを持つ複数のエージェントにおいて，あるエージェントが隣接するエージェントを，エージェント間の距離に比例する速度で追跡する．全てのエージェントがこの動作を繰り返し行うことで，隣接する全てのエージェントのなす間隔が一定となり，エージェント全体の成すフォーメーションが規則的な多角形へと収束するということが cyclic pursuitなどで確認されている 7) ．
本研究では，この概念を用いることで同一経路上の全てのロボット間隔は等しいと仮定するが，本来この概念は線形モデルに対するものであるため，式 (1) の非線形な速度モデルを用る場合この仮定が常に成り立つとは限らない．式 (1) において距離 d(i) がある値を越えると，速度の変化はごく微小になってしまいロボット間の距離は縮まらない．このためロボット数が少ないと、その間隔は均等にならないという問題がある．本
研究ではロボット数が十分に多い場合について考えることで，ロボット同士の間隔は等間隔に収束するものとする．

3

役割分担の方法

各ロボットは得られた局所情報を用いて自身のいる経路のロボット数を推定する．十分に時間が経過すれば経路上の全ロボットの間隔が等しくなるという前提
条件より，経路 m(m = 1, 2) 上のロボット数を nm とすると，経路上で前後に位置するロボット間の理想的な距離 dm は次のようになる．

dm = d(1) = d(2) = · · · = d(nm ) = Lm /nm(2)ここで，各ロボットは分散制御されてことを考えると，実際のロボット間の距離には誤差があると考えられる．
ロボット i が推定する経路 m 上のロボット数の推定値- 303 -

3.2.1 case 1
全てのロボットが，時刻毎の n1 ，n2 を知っている．
ここで，全搬送効率を最大化するするような各経路の最適ロボット数 n∗1 ，n∗2 は，次式より求められる．

65

efficiency

4n∗1 = arg max(E1 (n) + E2 (N − n))3nn∗2 = N − n∗12(8)(9)100510152025
the number of robots

3035n∗m (m = 1, 2) を用いて，nm > n∗m となる場合に経路変更を行う．既知情報である総ロボット数から，全経路の搬送効率の和を最大化するよう経路選択を行う．

40Fig. 3: An eﬃciency.
(i)ñm は次のよう表せる．
ñ(i)
m =

Lmd(i)(3)

各ロボットは，ロボット数の推定値を用いて経路 m の搬送効率を計算し経路選択を行う．

3.1

搬送効率の計算

搬送効率は単位時間当たりにスタートに戻ってくるロボット数であると定義し，経路 m におけるロボットの搬送効率を次式で定義する．

Em =∑nm(i)
i=1 V (d )∑nm (i)i=1 d(4)前後に位置するロボット同士の間隔が均等になるという仮定より，ロボット i が推定する経路 m における搬送効率は次式で表される．

V (d(i) )(i)=Ẽm(i)dEm (n) =Lmn(5)

n(6)

(7)

速度モデルの式 (1) の A = 10，a = 2 とし，L = 20π とした時のロボット数に対する搬送効率のグラフは Fig. 3に示すようになる．

3.2(i)∗ñ1

搬送分担

前述した仮定が異なる 3 つの場合 (case 1，case 2，case 3) について，各ロボットが 2 つの経路から自身の進む経路を選択する方法をについて示す．各ロボットはスタートに戻ったときに経路選択を行うものとする．
2 経路の総ロボット数を N とすると，Route2 のロボット数は n2 = N − n1 と表せる．

(i)(i)= arg max(Ẽ1 (n) + Ẽ2 (Ñ (i) − n))n(i)(10)(i)∗ñ1 を用いて，ñ1 > ñ1 となるように経路変更を行う．ロボット i が Route2 にいる場合も同様にして経路選択を行う．ロボット i が推定する総ロボット数から，全経路の搬送効率の和を最大化するように経路選択を行う．

4

この式 (6) において，経路 m 上の搬送効率を最大化するような最適ロボット数 n∗m は以下の式を満たす値である．

n∗m = arg max(Em (n))

3.2.3 case 3
ロボット i は 1 度通った経路上のロボット数を記憶することで経路全体のロボット数を推定して経路選択を行う．ロボット i が Route1 にいるとするとき，Route1(i)の推定ロボット数は ñ1 であり，記憶している Route2(i)の推定ロボット数を n̂2 とする (Route2 を通った経験(i)が無い場合は，n̂2 = 0 とする) とロボット i が推定す
(i)(i)
る総ロボット数は Ñ (i) = ñ1 + n̂2 として求められる．ロボット i が推定する Route1 の最適ロボット数は(i)∗ñ1 は次式より求められる．

(i)∗

一方，ロボット数を変化させたときの搬送効率は，Lmが定数であるため次式のように表せる．

V ( Lnm )3.2.2 case 2ロボット i は自身が現在いる経路 m のロボット数を推定し，他方の経路のロボット数は未知である．各ロ(i)(i)∗
ボットは，ñm > ñm となる場合に経路変更を行う．
ロボット i がいる経路の搬送効率のみを最大化するよ
うに経路選択を行う．

シミュレーション

前述した仮定が異なる 3 つの場合 (case 1，case 2，case 3) について，複数ロボットによる 2 つの経路への搬送分担のシミュレーションを行った．速度モデルの係数を A = 10，a = 2 とする．左側の経路 Route1 はL1 = 20π ，右側の経路 Route2 は L2 = 10π とする．
このとき，式 (7) より n∗1 = 23，n∗2 = 11 である．また，N = 30 とし，初期状態で全てのロボットは経路Route1 にいるものとする．case 3 で行った時間 1，10，20，100 のシミュレーション図を Fig. 4 に示す．時刻毎の 3 つの場合の搬送効率の結果を Fig. 5 に示す．また，case １，case 2，case 3 での 2 経路のロボット数
n1 ，n2 の時間変化のグラフをそれぞれ Fig. 6，Fig. 7，Fig. 8 に示す．case 1 の結果は全経路の正確なロボット数を知っている場合の結果であり，最適な搬送効率とロボット数分担に収束している．case 2 は単純に自身の経路のロボット数を推定して搬送分担を行うものであり，搬送効率は他の場合に比べて低い値に収束しており，ロボット数も最適な値とは異なっている．case 3の提案手法による結果は最初はロボット数の変化がが激しく，効率も収束しないが，時間の経過と共に最適- 304 -な搬送効率とロボット数分担に収束した．この結果より，提案手法によって 2 つの目標に対しての繰り返し搬送における最適なロボットの経路分担ができることを確認できた．

11efficiency of transportation

512

おわりに

本稿では，2 経路での繰り返し搬送問題において複数のロボットが局所的な情報のみから各経路の最適なロボット数を推定し，経路選択を行うことで経路全体の搬送効率を最大化するような分散制御による経路分担の手法を提案した．シミュレーションによって提案手法の有用性を確認した．本稿では，環境変化の無い状
況でのシミュレーションしか行っていないため，今後は各経路のロボット数が最適な値に収束した後で総ロボット数が変化する場合などにもこの手法が妥当であるかを検証する予定である．また提案手法の妥当性についてもシミュレーションよる検証を行ったのみであるため，今後は数学的な検証を行いたいと考えている．

10987case 1case 2case 3654020406080100timeFig. 5: Eﬃciency of transportation
30参考文献1) 淺間 一, 尾崎 功一, 松元 明弘, 石田 慶樹, 遠藤 勲：通信を用いた分散的管理に基づく複数の自律型ロボットの協調的作業分担決定手法, 日本ロボット学会誌, 10-7,955/963 (1992)

the number of robots

25202) Tsuyoshi Mizuguchi, Ken Sugawara：Proportion Regulation in Task Allocation Systems, IEICE transactions on fundamentals of electronics, communications
and computer sciences, 89-10, 2745/2751 (2006)

15103) 吉村 裕司, 太田 順, 井上 康介, 平野 智一, 倉林 大輔, 新井 民夫：群ロボットによる多数物体の繰返し搬送計画,
日本ロボット学会誌, 16-4, 499/507 (1998)5004) Cheng Shao, Dimitrios Hristu-Varsakelis：Cooperative optimal control : broadening the reach ofbio-inspiration, Bioinspiration and Biomimetics, 1-1,
1/11 (2006)

2040

60

80

100timeFig. 6: Number of robots (case 1)# of robots on route 1
optimal # of robots on route 1# of robots on route 2
optimal # of robots on route 23025
the number of robots

5) 里 悠太, 小林 祐一：生物の行動モデルによる群移動ロボットの協調経路最適化, 第 26 回日本ロボット学会学術講演会第予稿集 (2008)
6) Masako Bando, Katsuya Hasebe, Ken Nakanishi, Akihiro Nakayama, Akihiro Shibata, Yuki Sugiyama：
Phenomenological Study of Dynamical Model of Trafﬁc Flow, Journal de Physique I, 5-11,1389/1399(1995)
7) Joshua A. Marshall, Mireille E. Broucke, Bruce A.
Francis：Formations of Vehicles in Cyclic Pursuit,IEEE transactions on automatic control, 49-11 (2004)# of robots on route 1
optimal # of robots on route 1# of robots on route 2
optimal # of robots on route 2201510

50030

01620

40

1460

80

100timeFig. 7: Number of robots (case 2)30# of robots on route 1
optimal # of robots on route 1# of robots on route 2
optimal # of robots on route 2

the number of robots

25
time: 1

time: 10

20

19

1119

1115

10

500
time: 20

time: 100

2040

60

80

time

Fig. 8: Number of robots (case 3)

Fig. 4: simulation (case 3)- 305 -100