Integrating Symbolic Discovery with Numerical Machine Learning for Autonomous Swarm Control

Japanese version

Strategic Japanese-French Cooperative Program on Information and Communications Technology Including Computer Sciences

Japan Science and Technology Agency(JST) - Agence nationale de la recherche (ANR)

2008/10/1 - 2012/3/31

Japanese team

Einoshin Suzuki

Leader, Professor

Department of Informatics, ISEE, Kyushu University

Shin Ando

Assistant Professor

Department of Computer Science, Faculty of Engineering, Gunma University

Shigeru Takano

Assistant Professor

Department of Informatics, ISEE, Kyushu University

Nguyen Huy Thach

Doctor course student

Graduate School of Systems Life Sciences, Kyushu University

Shao Hao

Doctor course student

Graduate School of Systems Life Sciences, Kyushu University

Boubou Somar

Doctor course student

Graduate School of Systems Life Sciences, Kyushu University

Asuki Kouno

Doctor course student

Graduate School of Systems Life Sciences, Kyushu University

Theerasak Thanomphongphan

Master course student

Gunma University

Daisuke Hoshino

Master course student

Gunma University

Shouta Nagafuchi

Master course student

Department of Informatics, Graduate School/Faculty of Information Science and Electrical Engineering, Kyushu University

Kouichiro Nishikawa

Master course student

Department of Informatics, Graduate School/Faculty of Information Science and Electrical Engineering, Kyushu University

Emi Matsumoto

Master course student

Department of Informatics, Graduate School/Faculty of Information Science and Electrical Engineering, Kyushu University

Kouhei Takemoto

Doctor course student

Graduate School of Systems Life Sciences, Kyushu University

French team

Michèle Sebag

Leader, Research Director

TAO project, CNRS

Marc Schoenauer

Research Director

TAO project, INRIA

Nicolas Bredèche

Associate Professor

LRI, University of Paris 11

David Meunier

Postdoctoral Researcher

TAO project, INRIA

Jean-Marc Montanier

Doctor course student

LRI, University of Paris 11

本研究は,個体が多数集まって「群れ」をつくることにより,1個体のみでは達成できないタスクを実現するロボットの効率的自律制御機構の設計を目指す. このような制御機構の設計には多大な労力が必要であり,シミュレーション実験と実ロボット実験の間に大きなギャップが存在することが知られている.効率的な設計を実現するために,日本側(九州大学,群馬大学)は記号的学習,データマイニング,背景知識モデリング,フランス側(CNRS, INRIA, パリ第11大学)は確率的学習,統計的最適化と,互いが世界的な水準を誇る相補的な領域を担当する. 研究目的の達成においては,日仏両研究グループのシナジーを実現する.さらに本研究の成果を発表すると共に,機械学習・データマイニングの実ロボットへの応用という新しい研究分野を世界的に確立するため,公開型の国際ワークショップを毎年開催する.

論文発表した主な研究成果は,A.スワームロボットの手配とログデータの生成,B.スワームロボットのログデータ解析,C.スワームロボットの効率的自律制御,D.基盤となるデータマイニング・機械学習手法の開発,E.スワームロボットの効率的自律制御機構の設計に分けられる.
A. はEを達成するための基盤データを得ることに相当する.日本側が実ロボットを6種類製作し,主に6種類のログデータを提供した. 製作したロボットは,AR1.低機能偵察ロボット4台,AR2.縦列行進ロボット6台,AR3.大型ロボット7台,AR4.高機能偵察ロボット10台,AR5.見守りロボット5台,AR6.探索ロボット1台である.生成した主なログデータは,AD1.フィールド集団巡回データ,AD2.縦列行進データ,AD3.オフィス偵察データ,AD4.人回避用データ,AD5.追従データ,AD6.人見守りデータである.
B.はEを達成するための手掛かりを得ることに相当する.4台のAR1ロボットによる集団巡回AD1を主な対象とし,B1.異常行動の特徴づけと検出,B2.正常ログデータに基づき未知の異常行動を発見する手法,B3.偵察タスクを行う群ロボットのクラスタリング解析,B4.軌跡データの離散化とクラスタリングなどを提案して優れた結果を得,データマイニングやエージェント研究において権威ある国際会議などで発表した.
C.はEを達成するための知見を得ることに位置づけられる.C1.オフィス内での人検知と人回避,C2.リフティングウェーブレットによる新規物体の検出,C3.Camshiftアルゴリズムを用いたオフィス内での人追従,C4.縦列行進する群ロボットを提案して,機械学習・データマイニングを制御機構で有効裏に用いる実ロボット群を構築した.スワームロボット研究で権威がある国際会議などで発表した.
D.は中期的・長期的にEに貢献する基礎研究と位置付ける.D1.異常部分グラフ発見手法やD2.拡張MDL原理による転移学習手法などを提案し,グラフに基づく制御機構の異常発見およびロボット制御機構の個人化など汎化への道を拓いた.データマイニングや機械学習で権威ある国際会議・ジャーナルなどに論文が受理された.
E.は複数台のスワームロボットによる集団タスク実現を対象とし,フランス側と日本側がそれぞれ得意とする技術を併せたシナジー効果を実現した.具体的には,日本側とフランス側が協力し合い,5台のAR2ロボットによる縦列行進問題を対象とした.縦列行進はスワームロボットにとってもっとも重要な機能のひとつである移動機能の効率的な形態であり,各ロボットのばらつきや各種ノイズにより挑戦し甲斐のある問題となっている. 各ロボットは,フランス側が考案し提供した統計的最適化法(1+1)Restart-Online 適応アルゴリズムの日本側が改良したバージョンに基づき,縦列行進用の制御機構を実験中に改良する.制御機構のよさを評価するために,AD2のフィールドデータを生成するシステムを用いた.縦列行進を行うフィールドは大小の2種類を用意した.大きいフィールドではロボットが散らばっているために前方ロボットを見失ったときに見つけ直せる可能性が小さく,小さいフィールドに比較して効率的自律制御機構の設計が難しい.実ロボット実験を行うコストの高さから,本問題には分類子などの大域的パターンではなくルールなどの局所パターン発見が適している.ただし局所パターン発見手法が各応用問題において目的とするパターンを発見するとは限らず,本問題でもたとえば標準的な機械学習・データマイニング総合ツールであるWEKAの手法を適用しても,最もよい制御機構を上回る制御機構を構成するためのパターンは発見できない.日本側は,発見されたルールペア間の距離という概念を提案し,類似する発見ルールを統合することにより有用な可能性があるパターンを生成する新方式を考案した.この方式で生成されたルールを各ロボットの制御機構に組み込み,ロボットたちが平均的によい縦列行進を行うことを確認した.特に効率的自律制御機構の設計が難しい大きなフィールドでは,提案手法で設計した制御機構は最良の結果を示し,改良の余地が大きい難しい問題で提案手法の有効性を示した.提案手法で設計された制御機構を解読し,他のロボットを見失わないよう急に曲がらないなど設計者から見ても妥当であることを確認した. 研究成果は,知的エージェント分野で権威がある2011 IEEE/WIC/ACM International Conference on Intelligent Agent Technologyにおいて発表し,聴衆の関心を呼んだ.実スワームロボットの自律的制御機構の設計という困難な問題に対して,日仏の研究グループが協力して統計的最適化,機械学習,データマイニング手法に基づく解決策を提案し,実ロボット実験によってその有効性を示した.なおこの国際会議はフランスのリヨンにて開催されたため,フランス国内への宣伝という点においても有効であった.
当該研究により,可能性は大きいものの,これまでにその難しさからあまり注目を集めてこなかった,実ロボットへの機械学習・データマイニングの適用という新分野が,本研究を契機に盛んになっていくと実感している.今後は,さらなる頑健・長時間・機能高度化および人間との共存を軸に発展させる予定である.小型で安価であり,自律的に推論し移動でき,学習・発見・適応機能を備えたスワームロボットは,中長期的には見守りロボットと呼べる家庭用電化製品に発展すると期待できる.本研究の成果,特にAR5,AD4, AD5, AD6, C1, C3, D2は,その基盤となる.

Organized workshop: LEMIR 2009 International Workshop@Slovenia, LEMIR 2011 International Workshop@Canada

Selected outcomes:
1. Einoshin Suzuki, Hiroshi Hirai, Shigeru Takano: "Toward a Novel Design of Swarm Robots Based on the Dynamic Bayesian Network", Advances in Data Management". Springer Studies in Computational Intelligence, Vol. 223, pp. 299-310, Zbigniew W. Ras and Agnieszka Dardzinska (eds.), Springer-Verlag, November 2009.
2. JianBin Wang, Bin-Hui Chou, Einoshin Suzuki: Finding the k-Most Abnormal Subgraphs from a Single Graph, Discovery Science, Lecture Notes in Artificial Intelligence 5808 (DS), Springer-Verlag, pp. 441-448, October 2009, Porto, Portugal.
3. Einoshin Suzuki, Shigeru Takano, Hiroshi Hirai: Toward Using Symbolic Discovery in Designing Controllers of Autonomous Swarm Robots, Proc. First International Workshop on LEarning and data Mining for Robotics (LEMIR), pp. 1-10, September 2009, Bled, Slovenia.
4. Einoshin Suzuki and Michèle Sebag: Preface, Proc. First International Workshop on LEarning and data Mining for Robotics (LEMIR), p. ii, September 2009, Bled, Slovenia.
5. Swagat Kumar, Nguyen Huy Thach, and Einoshin Suzuki: "Understanding the Behaviour of Reactive Robots in a Patrol Task by Analysing their Trajectories", Proc. 2010 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT), pp. 56-63, September 2010, Toronto.
6. Asuki Kouno, Shigeru Takano, and Einoshin Suzuki: "Constructing Low-cost Swarm Robots that March in Column Formation", Swarm Intelligence (ANTS), LNCS 6234, pp. 556-557, September 2010, Brussels.
7. Hiroshi Hirai, Shigeru Takano, Einoshin Suzuki: Simulating Swarm Robots for a Collision Avoidance Problem based on a Dynamic Bayesian Network, Proc. Tenth European Conference on Artificial Life (ECAL 2009), LNAI 5778, Springer-Verlag, pp.416-423, 2011 (in print).
8. Shin Ando, Theerasak Thanomphongphan, Daisuke Hoshino, Yoichi Seki, and Einoshin Suzuki: "ACE: Anomaly Clustering Ensemble for Multi-perspective Anomaly Detection", Proc. Eleventh SIAM International Conference on Data Mining (SDM), pp. 1-12, Phoenix/Mesa, Arizona, April 2011 (datasets).
9. Shao Hao and Einoshin Suzuki: "Feature-based Inductive Transfer Learning through Minimum Encoding", Proc. Eleventh SIAM International Conference on Data Mining (SDM 2011), pp. 259-270, Phoenix/Mesa, Arizona, April 2011.
10. Shao Hao, Bin Tong, and Einoshin Suzuki: "Compact Coding for Hyperplane Classifiers in Heterogeneous Environment", Machine Learning and Knowledge Discovery in Databases (ECML/PKDD 2011), Part III, LNCS 6913, Springer-Verlag, pp. 207-222, September 2011, Athens.
11. Asuki Kouno, Jean-Marc Montanier, Shigeru Takano, Nicolas Bredeche, Marc Schoenauer, Michele Sebag, and Einoshin Suzuki: "On-board Evolutionary Algorithm and Off-line Rule Discovery for Column Formation in Swarm Robotics", Proc. 2011 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT 2011), pp. 220-227, Lyon, August 2011.
12. Emi Matsumoto, Michele Sebag, and Einoshin Suzuki: "Using SVM to Avoid Humans: A Case of a Small Autonomous Mobile Robot in an Office", Computer and Information Sciences II: 26th International Symposium on Computer and Information Sciences (ISCIS 2011), pp. 283-287, London, September 2011.
13. Somar Boubou, Asuki Kouno, and Einoshin Suzuki: Implementing Camshift on a Mobile Robot for Person Tracking and Pursuit, Proc. Eleventh IEEE International Conference on Data Mining Workshops (ICDMW 2011), pp. 682-688, December 2011, IEEE Computer Society, Vancouver.
14. Shigeru Takano and Einoshin Suzuki: New Object Detection for On-board Robot Vision by Lifting Complex Wavelet Transforms, Proc. Eleventh IEEE International Conference on Data Mining Workshops (ICDMW 2011), pp. 911-916, December 2011, IEEE Computer Society, Vancouver.
15. David Meunier, Michele Sebag, and Shin Ando: Characterizing Anomalous Behaviors and Revising Robotic Controllers, Proc. Eleventh IEEE International Conference on Data Mining Workshops (ICDMW 2011), pp. 705-710, December 2011, IEEE Computer Society, Vancouver.
16. Shin Ando and Einoshin Suzuki: Role-behavior Analysis from Trajectory Data by Cross-domain Learning, Proc. Eleventh IEEE International Conference on Data Mining (ICDM 2011), pp. 21-30, December 2011, Vancouver.
17. Kouhei Takemoto, Shigeru Takano, and Einoshin Suzuki: "Human Detection by a Small Autonomous Mobile Robot", Extraction et Gestion des Connaissances (EGC'2012), pp. 531-536, Bordeaux, France, February 2012.
18. Hao Shao, Bin Tong, and Einoshin Suzuki: "Extended MDL Principle for Feature-based Inductive Transfer Learning", Knowledge and Information Systems, An International Journal, Springer (accepted for publication).