本論文では,多数個の可動物体を初期位置から目標位置へ運ぶ多数物体再配置作業を取り扱う.効率,柔軟性,システムの頑健性の向上のため,移動ロボット群を用いた作業遂行手法の確立を目指す.

多数物体再配置作業では,ロボットが適宜物体を把持,開放する必要があるため,ロボットの動作の自由度は大きくなる.さらに,移動ロボット群を想定する場合にはその傾向が顕著になる.そのため, 1) 達成が容易ないくつかのサブタスクを設定し,2) サブタスクを実行する順序を決め,3) それぞれのサブタスクを実行する,という段階を経て作業を行う手法が一般的である.本論文では,1) の処理を「作業分割」と呼び,2) の処理を「作業割付」と呼ぶ.

これらの処理を行う際には,ロボットが移動するための空間,物体が移動するための空間などの「資源」が作業環境中にどのように配置されているかを考慮することが重要であり,特にそれらの幾何的構造に注目することが必要である.本論文では,上述の資源配置のことを「偏在性」と呼ぶ.

また,実環境でロボットが複雑な作業を行うためには,センサ誤差などの各種誤差を含めた「環境の動的変動」を考慮しつつ,作業の効率性を維持する必要がある.

そこで,本研究では,

・偏在性を考慮した作業分割手法,作業割付手法の構築.

・環境の動的変動に対応する作業遂行手法の構築.

の2つを具体的な研究目的とする.

作業分割手法として,領域法(territorial approach)の考え方に基づいた手法を提案する.この手法によって,各ロボットが移動するための空間を,他のロボットがどのような動きをするかに関わらず,常に確保することができる.作業割付手法として,従来のプロジェクトスケジューリング問題解法(project scheduling problem solver, PSP Solver)を拡張した手法を提案する.物体が移動するための空間同士の関わりを,「サブタスク間の順序制約」という形で顕在化させることによって,デッドロックを起こすことのないサブタスク実行順序を生成する.

多数物体再配置作業は非常に複雑な問題であるため,まず作業完了の保証を得るための計画を立案し,次いで実環境において計画を実現するという作業遂行手法を構築する.実環境での計画実現の際,環境の動的変動を検知し,その都度計画を修正する手法を提案する.実環境での計画実現の際,環境の動的変動を検知し,その都度計画を修正する手法を提案する.

実環境での計画実現の際,環境の動的変動を検知し,その都度計画を修正する手法を提案する.

本論文は,7つの章により構成されている.1章において,研究背景,当該分野における従来研究と残された課題,それらに基づいた研究目標について述べた.

2章では,移動ロボット群による多数物体再配置問題の問題設定について,その定式化,仮定,順序制約の定義に分けて述べた.Manipulationplanningの分野における知見を利用した再配置作業の定式化を行ない,1つの物体を扱うことが1つのサブタスクと位置づけられることを明らかにした.仮定について述べることで,本論文で扱う再配置作業が,1台のロボットで遂行できるサブタスクは同時に1つ(SR),1つのサブタスクに要するロボットは1台(ST),サブタスクに要する作業時間は未知(IA),というクラスに属することを明らかにした.また,順序制約の定義について述べ,「サブタスクAが完了してからサブタスクBを開始しなければならない制約」をA-〈Bと記述できることを明らかにした.

3章では,提案手法の概念設計を行なった.まず,問題規模の大きさに対応するために,1)事前計画,2)動的変動を考慮した計画の実現,の2段階に分けて処理を行う構造を提案した.また,事前計画の段階においては,i)高速な初期作業計画の立案,ii)初期作業計画の改善,の2段階に処理を分けることで,計算時間制約に対応する枠組みを提案した.さらに,初期計画立案の段階に対して,II)作業分割によるサブタスクゐ設定,II)作業割付によるサブタスク実行順序の決定,III)各サブタスクに対する動作計画立案,の3段階に分けて処理を行うことで高速に処理を行う枠組みを提案した.また,実機による作業実現手法について述べた.環境の動的変動に対処するために,作業計画の異なる段階に対して変更を加え,かつ異なる計算時間を要する対処手法を3つ,用意した.つまり,a)ロボット位置を計測することによる移動経路の微修正,b)再計画による移動経路の修正,c)再計画による受け渡し位置の再設定,の3つの手法を提案した.これによって,計量的な誤差に対してはa)の手法で即座に対応することができる.また,環境の動的変動に対してはb),c)の手法により,多少の計算時間をかけたとしても,作業計画を大幅に修正することで,作業が冗長になることを防ぐことができる.

4章では,初期作業計画立案手法について述べた.作業分割の段階では,高速に処理を行うために,離散ボロノイ線図の作図法を用いた領域分けと,ルールによる受け渡し位置設定を行なう手法について述べた.領域を設定することで,各ロボットが他のロボットの動作を考慮することなく,割り付けられたサブタスクを遂行可能である状態を作り出した.また,順序制約の増加を抑えるように作業分割を行なうことで,作業割付の段階で高速に実行可能解が求まる状態を設定した.作業割付の段階では,PSPで扱われていない種類の順序制約と,その計算法について説明し,順序制約を考慮したサブタスク実行順序を生成するための拡張PSPSolverについて説明を行った.さらに,サブタスクに対する動作計画立案の段階では,動作計画問題が2回の経路計画問題に落としこめることに着目し,従来の経路計画手法から適切な手法を選定し直接適用した.また,提案した手法を評価するために実験を行ない,結果,提案手法は実験を行なった3台から4台までの移動ロボット,3個から12個までの可動物体が含まれる8つの環境全てに対して,初期作業計画を適切に立案することができることが分かった.ロボットの大きさに対する作業環境の広さを表す指標としてsparcityを導入し評価を行なった結果,従来手法はsparcityが0以上の場合に適用可能であるのに対して,提案手法はsparcityが-2から4程度の範囲で適用可能であることが分かった.また,提案手法は従来手法より15%短い時間で作業を終えることができる解を出力することが分かった.

5章では,初期作業計画に対して改善を行ない,効率的な作業計画を得る手法について説明した.改善は作業分割を一部やり直す形で行なわれ,1)CPMを用いて全余裕時間を計算する,2)全余裕時間が最大であるサブタスクを選ぶ,という手順で修正対象となるサブタスクを選ぶことを説明した.また,1)他のロボットの搬送経路,他の物体の設置位置に重複しない範囲を算出する,II)その他の位置に対して受け渡し位置を変更した場合のサブタスク実行時間を算出する,III)それに基づいて総作業時間を見積もる,IV)総作業時間を最小化する受け渡し位置を選ぶ,という手順で新たなサブタスクを定義することを説明した.提案した手法を評価するために実験を行い,提案手法は2台から4台までのロボット,3個から12個までの可動物体が含まれる20の作業環境に対して作業計画の改善を行なうことができることが分かった.平均10%以上の作業時間を短縮し,最終的に解を出力するまでの計算時間は平均1分以下であったことから,提案手法の解の質,計算時間両面での有用性を示した.また,全余裕時間を消費するという基本方針を達成し,平均60%以上の全余裕時間を短縮していることを明らかにした.さらに,提案手法の効果が発揮される状況について分析を行い,その結果,提案手法はロボットや物体の密度がそれほど大きくなく,物体受け渡し数に偏りがあるときに,特に効果を発揮することが分かった.

6章では,実環境で作業を実現する手法について述べた.計量的な誤差に対しては即座に対応するために,また環境の大幅な変動に対しても作業が冗長になることを防ぐために,作業計画の異なる段階に対して変更を加え,かつ異なる計算時間を要する対処手法を複数用意することを提案した.また,提案手法を用いて,変動が計量的な誤差に留まる場合と,壁の形状が大幅に変わる場合の双方について,ロボット3台,可動物体が8個の再配置作業を行った.両者において構築した処理が適切に行なわれていることを確認した.また,センシング誤差の取り扱いの問題を除けば,提案した手法は誤差に対して十分に対処できるものであることを示した.

7章では,本論文の結論を述べた.本論文の内容は以下のように結論付けられる.

●環境の局所性を考慮した作業計画立案手法を構築した.領域法によるロボット移動空間配置の影響の排除,順序制約の導出によるサブタスク間の優先関係の顕在化,によって,複雑な問題を,単純な複数の問題へと落とし込むことに成功した.本研究で提案した基本概念は,移動ロボットに関する問題のみならず,問題の分割が困難だと考えられている諸問題にも適用可能であると考えられる.

●実環境における多数物体再配置作業に対して,環境の動的変動への対応手法を,再計画まで含めた形で整備した.

●以上の内容によって,移動ロボットにとって基本的な作業である多数物体再配置作業に対して,局所性が存在する環境であっても,移動ロポット群により効率的に作業遂行ができる手法を構築した.

「移動ロボット群による多数物体再配置作業」は,現実の多くのアプリケーションに含まれる基本的な作業であり,その遂行手法の構築が求められてきた.一方で,多数物体再配置作業は,多数の物体やロボットの自由度が関わる非常に複雑な作業であり,移動ロボティクス分野の従来手法を直接適用することは困難であるとされてきた.これに対し本論文では,従来研究とは異なる指標に基づく問題分割手法,ハードウェア構成までを含めた実世界での作業実現手法を構成することによって,再配置作業遂行手法を提案した.具体的には,以下のことを実現した.

多数物体再配置問題に対する計画立案手法の構築.問題分割の新たな指標として,"環境の偏在性"を提案し,再配置問題における環境の偏在性が"ロボット通過空間の偏り"と"物体配置の偏り"で構成されていることを分析した.ロボット通過空間の偏りに影響されない問題への置換え処理として,ロボット移動経路が交差する可能性を排除する観点からの従来手法の調査を行い,領域法の基本概念が再配置問題に適用可能であると判断した.領域設定が総作業時間へ与える影響を考慮することによる,効率的な領域設定手法を構築した.物体配置の偏りを顕在化するための概念として,再配置問題における順序制約の定義付けを行なった.物体配置の偏りに影響されない問題への置換え処理として,再配置問題における順序制約を遵守する,搬送順序生成手法を新たに構築した.また,実環境における多数物体再配置作業に対して,環境の動的変動への対応手法を,再計画まで含めた形で整備した.

また本論文では,以上の提案手法をシミュレーション実験と,実機実験によってそれぞれ評価した.その結果,以下の結論が得られた.提案した問題分割手法による,計画立案手法の高速性.提案した問題分割の構造により,複雑な再配置問題は,比較的単純な構造を持つ部分問題に分けて処理することができた.それにより,一つの実行可能解を得るまでの計算時間を3分以下(1.08GHzのCPU使用時)に,計画に修正を施し,作業を効率化する段階を含めた場合でも,1分以下(2.8GHzのCPU使用時)に計画立案を完了することができた.これによって,現実のアプリケーションで求められる,ロボットの動作開始までの時間短縮を実現することができた.領域設定手法による,作業効率の向上.作業効率に与える影響を考慮して領域を設定する新たな手法の提案により,作業効率の高い計画を立案することができた.具体的には,以下の点で従来手法に優越した.領域を仮定することによる,手法の適用範囲の向上.領域を仮定し,ロボットの移動経路が交差する可能性を排除した.そのアプローチにより,再配置作業に対する従来手法より多様な環境に対して,実行可能解を出力することができた.具体的には,偏在性を表すsparcityという指標を用いた評価を行った.その結果,従来手法が偏在性の影響が軽度である環境に対してのみ有効であったのに対し,提案手法は偏在性がより厳しい状況においても適用可能であった.受渡し位置修正により,全余裕時間を60%削減し,ロボット間の作業量の隔たりを是正した.作業効率に与える影響を考慮したうえで受け渡し位置を細かく設定する手法を提案し,その結果,ロボット間の作業量の隔たりを表す指標である全余裕時間を,作業効率を考慮しない場合と比較して60%削減した.その点で,領域法の従来手法より定性的に優越する手法を構築することができた.ただし,提案手法は,物体搬送順序を初期値から変化させない範囲での受け渡し位置修正を行なっており,作業効率化の観点からは,なお手法改善の余地がある.順序制約の解決.提案した搬送順序生成手法は,予定した通りの機能を示し,物体配置に伴うデッドロックを回避することができた.従来研究において扱われていなかった順序制約に対する解決手法を提案したため,本論文で得られた知見は,ロボティクス以外のプランニングの分野にも貢献することができると考える.再計画手法による,環境の動的変動への対応能力.提案した再計画手法により,環境の動的変動のうち,作業環境の構造変化には柔軟に対応することができた.

また,移動誤差やセンシング誤差などの,ロボットのハードウェアに起因する誤差について,実験室内の環境においては,提案手法で対応可能な範囲に収まることが確認できた.

以上の内容によって,移動ロボットにとって基本的な作業である多数物体再配置作業に対して,偏在性が存在する環境であっても,移動ロボット群により効率的に作業遂行ができる手法を構築した.

よって本論文は博士(工学)の学位請求論文として合格と認められる。