On Multi-Robot Collaboration: Using Arduino-based Roomba as an Example

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：25

、訪客IP：18.191.233.198

姓名

廖科維(Ke-Wei Liao) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(On Multi-Robot Collaboration: Using Arduino-based Roomba as an Example)

相關論文

★ Dynamic Overlay Construction for Mobile Target Detection in Wireless Sensor Networks	★ 車輛導航的簡易繞路策略
★ 使用傳送端電壓改善定位	★ 利用車輛分類建構車載網路上的虛擬骨幹
★ Why Topology-based Broadcast Algorithms Do Not Work Well in Heterogeneous Wireless Networks?	★ 針對移動性目標物的有效率無線感測網路
★ 適用於無線隨意網路中以關節點為基礎的分散式拓樸控制方法	★ A Review of Existing Web Frameworks
★ 將感測網路切割成貪婪區塊的分散式演算法	★ 無線網路上Range-free的距離測量
★ Inferring Floor Plan from Trajectories	★ An Indoor Collaborative Pedestrian Dead Reckoning System
★ Dynamic Content Adjustment In Mobile Ad Hoc Networks	★ 以影像為基礎的定位系統
★ 大範圍無線感測網路下分散式資料壓縮收集演算法	★ 車用WiFi網路中的碰撞分析

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在本文中，我們處理多機器人合作的問題。舉例來說，我們考量
給予一個區域讓多機器合作清潔。這工作由任務初始化、任務執行與
任務重新分派所組成。Arduino 的自走車雛型被設計來實作我們要的
合作系統，而Android 智慧型手機被放置在自走車上來記錄軌跡與跟
其他台可合作的機器交換訊號。實作的結果在不同情境下顯示出：雖
然實際執行時間會比理想情況來的高，但在越多台合作之下任務會更
快。

摘要(英)

In this thesis, we address the issue of multi-robot collaboration.
As a specific example, we consider the collaboration of multiple robots to clean (i.e., cover) a given area.
The proposed work consists of task initialization, task execution, and task re-assignment (i.e., auction).
An Arduino based autonomous car prototype was designed to implement our proposed collaboration system and an Andriod smartphone was installed on the car to log the traces and exchange signals between cars to enable the collaboration.
The experiment results in different scenarios show that, while the actual execution time is longer than the ideal one, more cars in collaboration finish the task faster.

關鍵字(中)

★ 多機器合作

關鍵字(英)

★ multi-robot collaboration
★ auction based algorithm
★ multi-robot task allocation

論文目次

1 Introduction 1
2 Preliminary 3
2.1 Arduino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Android . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Fingerprinting-based positioning system . . . . . . . . . . . . . . . . . . . 6
2.4 Roomba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.5 Voronoi diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Related work 10
3.1 Robot cooperation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Our solution 14
4.1 Problem denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 Task initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Auction for unreachable regions . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 Random walk approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5 Performance 28
5.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.2 Experimental metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6 Conclusions 35
Reference 36

參考文獻

[1] Android developers community http://developer.android.com/about/versions/lollipop.html,
2015.
[2] Atmel Corporation http://www.atmel.com/devices/atmega328p.aspx, 2015.
[3] Interaction Design Institute Ivrea https://interactionivrea.org/, 2015.
[4] Parallax Inc. http://learn.parallax.com/shieldrobot, 2015.
[5] Amit Kumar Jha Girish Kapse Abhishek Pandey, Anirudh Kaushik. A technological
survey on autonomous home cleaning robots. International Journal of Scientific and
Research Publications (IJSRP), Volume 4, Issue 4, April 2014 Edition, 2014.
[6] O.G. Adewumi, K. Djouani, and A.M. Kurien. Rssi based indoor and outdoor distance
estimation for localization in wsn. In Industrial Technology (ICIT), 2013 IEEE
International Conference on, pages 1534{1539, Feb 2013.
[7] J.C. Aguilar Herrera, P.G. Ploger, A. Hinkenjann, J. Maiero, M. Flores, and
A. Ramos. Pedestrian indoor positioning using smartphone multi-sensing, radio
beacons, user positions probability map and indoorosm floor plan representation.
In Indoor Positioning and Indoor Navigation (IPIN), 2014 International Conference
on, pages 636{645, Oct 2014.
[8] Dimitri P. Bertsekas. The auction algorithm for assignment and other network ow
problems: A tutorial. Interfaces, 20(4):133{149, 1990.
[9] S.C. Botelho and R. Alami. M+: a scheme for multi-robot cooperation through
negotiated task allocation and achievement. In Robotics and Automation, 1999.
Proceedings. 1999 IEEE International Conference on, volume 2, pages 1234{1239
vol.2, 1999.
[10] Arduino Community. Arduino https://www.arduino.cc/, 2015.
[11] LEGO NXT Program Community. Lego nxt program
http://www.nxtprograms.com/, 2015.
[12] Android developers. Android https://developer.android.com/index.html, 2015.
[13] M.B. Dias, Robert Zlot, N. Kalra, and A. Stentz. Market-based multirobot coordination:
A survey and analysis. Proceedings of the IEEE, 94(7):1257{1270, July
2006.
[14] David Gale. The theory of linear economic models / [by] David Gale. McGraw-Hill
New York, 1960.
[15] B.P. Gerkey and M.J. Mataric. Sold!: auction methods for multirobot coordination.
Robotics and Automation, IEEE Transactions on, 18(5):758{768, Oct 2002.
[16] Brian P. Gerkey and Maja J. Matari. A formal analysis and taxonomy of task
allocation in multi-robot systems. INTL. J. OF ROBOTICS RESEARCH, page
2004, 2004.
[17] Brian P. Gerkey and Maja J Mataric. Murdoch: Publish/subscribe task allocation
for heterogeneous agents. In in Fourth International Conference on Autonomous
Agents, pages 203{204. ACM Press.
[18] Yanying Gu, A. Lo, and I. Niemegeers. A survey of indoor positioning systems for
wireless personal networks. Communications Surveys Tutorials, IEEE, 11(1):13{32,
First 2009.
[19] Ville Honkavirta, T Perala, S Ali-Loytty, and R Piche. Location fingerprinting methods
in wireless local area networks. Master of Science Thesis, Tampere University of
Technology, Finland, 2008.
[20] iRobot. irobot http://www.irobot.com/, 2015.
[21] Nikolaos M.P. Kakalis and Yiannis Ventikos. Robotic swarm concept for efficient oil
spill confrontation. Journal of Hazardous Materials, 154(13):880 { 887, 2008.
[22] Keisuke Kato and Shigeo Hirose. Development of the quadruped walking robot,
titan-ix mechanical design concept and application for the humanitarian de-mining
robot. Advanced Robotics, 15(2):191{204, 2001.
[23] C. Ronald Kube and Hong Zhang. Collective robotics: From social insects to robots.
Adapt. Behav., 2(2):189{218, September 1993.
[24] Harold W. Kuhn. The hungarian method for the assignment problem. Naval Research
Logistics Quarterly, 2:83{97, 1955.
[25] Benjamin Kuipers and Yung-Tai Byun. A robot exploration and mapping strategy
based on a semantic hierarchy of spatial representations. Robotics and Autonomous
Systems, 8(12):47 { 63, 1991. Special Issue Toward Learning Robots.
[26] Francesco Mondada, Michael Bonani, Xavier Raemy, James Pugh, Christopher
Cianci, Adam Klaptocz, Stphane Magnenat, Jean christophe Zu_erey, Dario Floreano,
and Alcherio Martinoli. The e-puck, a robot designed for education in engineering.
In In Proceedings of the 9th Conference on Autonomous Robot Systems and
Competitions, pages 59{65, 2009.
[27] Atsuyuki Okabe, Barry Boots, and Kokichi Sugihara. Spatial Tessellations: Concepts
and Applications of Voronoi Diagrams. John Wiley & Sons, Inc., New York, NY,
USA, 1992.
[28] Lynne E. Parker. Alliance: An architecture for fault tolerant multirobot cooperation.
IEEE Transactions on Robotics and Automaton, 1998.
[29] E puck Community. E-puck education robot http://www.e-puck.org/, 2015.
[30] Teemu Roos, Petri Myllymki, Henry Tirri, Pauli Misikangas, and Juha Sievnen. A
probabilistic approach to wlan user location estimation. International Journal of
Wireless Information Networks, 9(3):155{164, 2002.
[31] Reid G. Smith. The contract net protocol: High-level communication and control in a
distributed problem solver. Computers, IEEE Transactions on, C-29(12):1104{1113,
Dec 1980.
[32] M. Weiss-Cohen, I. Sirotin, and E. Rave. Lawn mowing system for known areas.
In Computational Intelligence for Modelling Control Automation, 2008 International
Conference on, pages 539{544, Dec 2008.
[33] Robert Michael Zlot. An Auction-Based Approach to Complex Task Allocation for
Multirobot Teams. PhD thesis, Robotics Institute, Carnegie Mellon University, 5000
Forbes Ave, December 2006.

指導教授

孫敏德(Min-Te Sun)

審核日期

2016-1-27

推文