||A Dynamic Programming-Based Path Planning Method for Mobile Robots in an Indoor Intelligent Environment
||Department of Mechanical Engineering
智慧生活空間近年來因為其潛在應用價值逐漸受到注目，在多國政府的推動之下，其應用產品已出現在市場，其中的關鍵為機器人的發展，而機器人在智慧生活的應用也促使了導航及室內定位技術的發展。此研究提出一個智慧生活空間之架構，由一個室內定位系統以及移動式機器人系統組成，此機器人系統同時能做為其他應用的發展平台。為了賦予機器人導航之能力，一個以動態規劃法為基礎之路徑規劃方法能夠找出閃避障礙物之路徑，並在具有利用位能函數模擬出之靜態及動態障礙物的模擬環境下進行測試。此外，受到室內機器人長時間行走的問題的啟發，路徑規劃法也具備規劃路徑的較短路徑的能力。此次路徑規劃法也與其他路徑規劃法如Potential Field及Bug Algorithm比較，模擬及實驗結果顯示，此方法在提出的模擬環境中能夠規劃出相對較短且避障的路徑。在整合導航方法後，整個系統具潛力於其他應用，如未來雲端機器人技術的加入能夠增加系統應用的穩定及彈性。
Intelligent living space have gained much attention due to its potential application over the past few years. Promoted by the governments around the globe, applications of intelligent environments are becoming more accessible to the public. One of the key enabling technologies is Robotics. With the arrival of domestic robots, technologies such as robot navigation and localization urgent in indoor environments. In this thesis, a structure of intelligent environment with a working robot system is proposed. The structure is composed of a Wiimote Localization System monitoring robot positions and a Mobile Robot System that works as a moving platform, which other robots can be built on. To navigate the robot, a DP-based path planning method is proposed to find an obstacle-free path. The method is tested in a designed simulated environments, where static and dynamic obstacles are simulated using potential functions. In addition, the path-planning method is optimized for finding distance-efficient path, which is inspired by problem of busy commute for indoor robots. The method is compared to other path-planning methods such as Potential Field and Bug Algorithm, and as suggested by simulation and experiment results, it has better performance than both methods in the proposed environment structure. With the integration of navigation methods, the system has the potential to be used in extensive applications. Cloud robotics, a cloud technology-based network can be adopted to make the system more robust and flexible in the future.
List of Figures…………………………………………………….…VII
List of Tables…….…………………………………………………...XIII
List of Symbols and Abbreviations………….…………...XIV
CHAPTER 1 1
1.1 Preliminary 1
1.2 Scenarios 6
1.3 Related Work 8
1.4 Motivations and Goal 12
1.5 Organization 14
CHAPTER 2 16
2.1 Introduction 16
2.2 Intelligent Environments 19
2.3 Principle and Applications of Cloud Robotics 21
2.4 Indoor Localization Methods 23
2.5 Indoor Mobile Robots 29
2.6 Robot Path Planning Methods 32
2.7 Summary and Discussions 38
CHAPTER 3 41
3.1 Introduction 41
3.2 Principle of Dynamic Programming 45
3.3 Design of DP-based Path Planning Method 54
3.4 Summary and Discussions 73
CHAPTER 4 75
4.1 Introduction 75
4.2 Requirement and Robot Analysis 79
4.3 Robot Modification and Manipulation 88
4.4 Performance Test 98
4.5 Summary 101
CHAPTER 5 102
5.1 Introduction 102
5.2 Indoor Maps Construction 105
5.3 Environment Setup in Simulation 107
5.4 Environment Setup in Experiment 112
5.5 Summary and Discussions 118
CHAPTER 6 119
6.1 Introduction 119
6.2 Performance Testing 123
6.3 Case Studying and Comparison 134
6.4 Summary 140
CHAPTER 7 141
7.1 Summary 141
7.2 Intelligent Environment 143
7.3 Robot Navigation and DP-based Path Planning Method 144
7.4 Mobile Robot Manipulation and Performance Test 145
7.5 Achievements and Extensive Discussions 147
CHAPTER 8 149
8.1 Summary 149
8.2 Conclusion 152
8.3 Contribution 154
8.4 Future Work 156
Appendix A: Robot Hardware ............................................................171
Appendix B: Labview Programs ........................................................176
Appendix C: Matlab Programs ..........................................................178
 Intelligent Environment, Wikipedia
 Francois liger
 Caring robot
 O. Khatib, "Real-time obstacle avoidance for manipulators and mobile robots." The international journal of robotics research 5.1 (1986): 90-98.
 Ng, James, Thomas Bräunl, "Performance comparison of bug navigation algorithms."Journal of Intelligent and Robotic Systems” 50.1 (2007): 73-84.
 LaValle, S. M., "Rapidly-Exploring Random Trees A Цew Tool for Path Planning." (1998).
 S. M. Killough and F. G. Pin, "Design of an omnidirectional and holonomic wheeled platform prototype," IEEE International Conference on Robotics and Automation, Vol.1, pp.84-90, 1992.
 W. K. Loh, K. H. Low, and Y. P. Leow, "Mechatronics design and kinematic modelling of a singularityless omni-directional wheeled mobile robot," IEEE International Conference on Robotics and Automation, Vol.3, pp.3237- 3242, 2003.
 Samani, A. H., et al., "Design and development of a comprehensive omni directional soccer player robot." International Journal of Advanced Robotic Systems 1.3 (2004): 191-200.
 L. M. Ni, Y. Liu, Y. C. Lau, and A. P. Patil, "LANDMARC: Indoor location sensing using active RFID," Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, pp.407-415, 2003.
 N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, "The cricket location-support system," in Proc. 6th ACM MOBICOM, Boston, MA 2000.
 R. Want, A. Hopper, V. Falcão, and J. Gibbons, "The active badge location system," ACM Transaction on Information Systems, Vol.40, pp.91-102, 1992.
 M. Maeda, T. Ogawa, T. Machida, and H. Takemura, "Position detection for a navigation support by augmented reality using infrared identifications," Technical Report of the Institute of Electronics, Information and Communication Engineers of Japan, Image Engineering, Vol.102, pp.59-64, 2002.
 G. Mao, B. Fidan, and B. D. O. Anderson, "Wireless sensor network localization techniques," Computer Networks, Vol.51, pp.2529-2553, 2007.
 P. Baronti, P. Pillai1, V. Chook, S. Chessa, A. Gotta, and Y. F. Hu, "Wireless sensor networks: A survey on the state of the art and the 802.15.4 and ZigBee standards," Computer Communications, Vol.30, pp.1655-1695, 2007.
 J. Yick, B. Mukherjee, and D. Ghosal, "Wireless sensor network survey," Computer Networks, Vol.52, pp.2292-2330, 2008.
 S. Yun, J. Lee, W. Chung, E. Kim, and S. Kim, "A soft computing approach to localization in wireless sensor networks," Expert Systems with Applications, Vol.36, pp.7552-7561, 2009.
 Akyildiz, I. F., et al., "Wireless sensor networks: a survey." Computer networks 38.4 (2002): 393-422.
 P. W. Chen, K. S. Chen, "IR Indoor Localization and Wireless Transmission for Motion Control in Robotic Architecture and Intelligent Life Applications Based on Wiimote Technology." National Cheng Kung University, 2010.
 K. Rebai, A. Benabderrahmane, O. Azouaoui, and N. Ouadah, "Moving obstacles detection and tracking with laser range finder," International Conference on Advanced Robotics, pp.1-6, 2009.
 Sim, Robert, and N. Roy, "Global a-optimal robot exploration in slam." Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on. IEEE, 2005.
 GP2D120 – Sharp Microelectronics of the Americas
 Murray, Don, J. J. Little, "Using real-time stereo vision for mobile robot navigation." Autonomous Robots 8.2 (2000): 161-171.
 S. Tilch and R. Mautz, "Current investigations at the ETH Zurich in optical indoor positioning," 7th Workshop on Positioning Navigation and Communication, pp. 174-178, Dresden, Germany, March 2010.
 A. Sanfeliu, N. Hagita, and A. Saffiotti, “Network Robot Systems,” Robotics and Autonomous Systems, vol. 56, no. 10, pp. 793-797, Oct. 2008.
 G. Hu, W. P. Tay, and Y. Wen, “Cloud Robotics: Architecture, Challenges and Applications,” IEEE Network, vol. 26, no. 3, pp. 21-28, May-Jun. 2012.
 B. Kehoe, A. Matsukawa, S. Candido, J. Kuffner, and K. Goldberg, “Cloud-Based Robot Grasping with the Google Object Recognition Engine,” IEEE International Conference on Robotics and Automation, pp. 4263-4270, May 2013.
 Karpov, A. Anatolyevich, A. Lale, and A. L. Ronzhin, "Multimodal assistive systems for a smart living environment." Trudy SPIIRAN19 (2011): 48-64.
 KMD Realitymedia Project
 Center of iNnovation and Synergy for IntelliGent Home and living Technology, National Taiwan University
 Touch Center
 H. Wu, L. Lou, C.-C. Chen, S. Hirche, and K. Kuhnlenz, "Cloud-Based Networked Visual Servo Control," IEEE Transactions on Industrial Electronics, vol. 60, no. 2, pp. 554-566, Feb. 2013.
 Y. C. Liu, K.S. Chen, S. C. Tien, "Cloud-based Mobile Robot Network in Intelligent Life," NSC, 2014.
 Misra, Pratap, P. Enge, "Global Positioning System: Signals, Measurements and Performance Second Edition," Massachusetts: Ganga-Jamuna Press, 2006.
 Titterton, David, J. Weston, "Strapdown Inertial Navigation Technology. 2-nd Edition," The Institution of Electronical Engineers, Reston USA (2004).
 M. F. Wu, K. S. Chen, "Development of Load-Cell Based Smart Floor for Indoor Localization." National Cheng Kung University, 2013.
 Toyota Inc.
 N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, "The cricket location-support system," in Proc. 6th ACM MOBICOM, August 2000.
 Lego ultrasonic sensor EV3
 M.W. Feng, S.L. Wen, K.C. Tsai, Y.C. Liu, and H.R. Lai, "Wireless sensor network and sensor fusion technology for ubiquitous smart living space applications," Second International Symposium on Universal Communication, pp.295-302, December 2008.
 M. Heidari, N. A. Alsindi, and K. Pahlavan, "UDP identification and error mitigation in ToA-Based indoor localization systems using neural network architecture," IEEE Transactions on Wireless Communications, vol.8, pp.3597-3606, July 2009.
 A. S. Paul, and E. A. Wan, "RSSI-Based indoor localization and tracking using sigma-point kalman smoothers," IEEE Journal of Selected Topics in Signal Processing, vol.3, pp.860-873, October 2009.
 A. R. J. Ruiz, F. S. Granja, J. C. P. Honorato, J. I. G. Rosas, "Accurate pedestrian indoor navigation by tightly coupling Foot-Mounted IMU and RFID measurements," IEEE Transactions on Instrumentation and Measurement, vol.61, pp.178-189, January 2012.
 E. DiGiampaolo, and F. Martinelli, "A passive UHF-RFID system for the localization of an indoor autonomous vehicle," IEEE Transactions on Industrial Electronics, vol.59, pp.3961-3970, October 2012.
 RFID Journal
 SunX’s Blog
 N. Kothari, B. Kannan, E. D. Glasgwow, and M. Bernardine Dias, "Robust indoor localization on a commercial smart phone," The International Workshop on Cooperative Robots and Sensor Networks, December 2012.
 Y. H. Seo, S. S. Kwak, and T. K. Yang, "Mobile robot control using smart phone and its performance evaluation," Advanced Communication and Networking - Communications in Computer and Information Science, vol.199, pp.362-369, August 2011.
 Orange Technology
 M. Altini, D. Brunelli, E. Farella, and L. Benini, "Bluetooth indoor localization with multiple neural networks," 5th International Symposium on Wireless Pervasive Computing (ISWPC), pp.295-300, May 2010
 L. Pei, R. Chen, J. Liu, T. Tenhunen, H. Kuusniemi, and Y. Chen, "Inquiry-based Bluetooth indoor positioning via RSSI probability distributions," Second International Conference on Advances in Satellite and Space Communications, pp.151-156, June 2010.
 S. Vicini, S. Bellini, and A. Sanna, "The city of the future living lab," International Journal of Automation and Smart Techonology (AUSMT), vol.2, pp.201-208, December 2012.
 L. Cheng, C.D. Wu, and Y.Z. Zhang, "Indoor robot localization based on wireless sensor networks," IEEE Transactions on Consumer Electronics, vol.57, pp.1099-1104, August 2011.
 Wifi Triangulation
 ZigBee, http://www.nhr.com.tw/product-1.asp?id=721&AA=429
 M.G. Pinto, A.P. Moreira, and P.G. Costa, "Indoor localization system based on artificial landmarks and monocular vision," TELKOMNIKA, vol.10, pp. 609-620, December 2012.
 Strüder, L., et al., "The European photon imaging camera on XMM-Newton: the pn-CCD camera," Astronomy and Astrophysics 365 (2001): L18-L26.
 Siegwart, Roland, I. R. Nourbakhsh, D. Scaramuzza, "Introduction to autonomous mobile robots," MIT press, 2011.
 Nexus robot
 M. H. Chen, K. S. Chen, "Development of Navigation Schemes and Group Autonomous Manipulation for Mobile Robots and Their Applications in Intelligent Living Technology" National Cheng Kung University, 2012.
 Khepera Robot
 D. Leven, M. Sharir, "An efficient and simple motion planning algorithms for a ladder moving in two-dimensional space amidst polygonal barriers," in Proc. 1st ACM Symp. Computational Geometry, Nice, France, 1997, pp. 1208–1213.
 E. Hou and D. Zheng, "Mobile robot path planning based on hierarching hexagonal decomposition and artificial potential fields," J. Robot. Syst., vol. 11, no. 7, pp. 605–614, 1994.
 J. T. Schwartz, M. Sharir, "On the piano movers’ problem: I. The case if a two-dimensional rigid polygonal body moving amidst polygonal barriers," IEEE Trans. Robot. Autom., vol. RA-36, no. 3, pp. 345–398, May 1983.
 Hart, P. E., N. J. Nilsson, B. Raphael, "A formal basis for the heuristic determination of minimum cost paths." Systems Science and Cybernetics, IEEE Transactions on 4.2 (1968): 100-107.
 Li, Z. X., and T. D. Bui, "Robot path planning using fluid model," Journal of Intelligent and Robotic Systems 21.1 (1998): 29-50.
 Oriolo, Giuseppe, G. Ulivi, M. Vendittelli, "Real-time map building and navigation for autonomous robots in unknown environments," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on28.3 (1998): 316-333.
 C. L. Hwang, and C. Y. Shih, "A distributed active-vision network-space approach for the navigation of a car-like wheeled robot," IEEE Transactions on Industrial electronics," vol.56, pp.846-855, March 2009.
 Jung, Seul, T. C. Hsia, R. G. Bonitz, "Force tracking impedance control of robot manipulators under unknown environment," Control Systems Technology, IEEE Transactions on 12.3 (2004): 474-483.
 Zhang, Tao, Y. Zhu, J. Song, "Real-time motion planning for mobile robots by means of artificial potential field method in unknown environment," Industrial Robot: An International Journal 37.4 (2010): 384-400.
 Al-Haddad, A. A., R. Sudirman, C. Omar, “Guiding Wheelchair Motion based on EOG Signals using Tangent Bug Algorithm.” Computational Intelligence, Modelling and Simulation (CIMSiM), 2011 Third International Conference on IEEE, 2011.
 Lumelsky, V. J., Stepanov, A. A., “Dynamic path planning for a mobile automaton with limited information on the environment,” IEEE Trans, Automat. Contr. 31, 1058-1063 (1986).
 I. Kamon, E. Rivlin, E. Rimon, “TangentBug: a range-sensor based navigation algorithm,” J. Robot. Res. 17(9), 934-953 (1998).
 Open Robotics
 D. Delling, P. Sanders, D. Schultes, D. Wagner, "Engineering route planning algorithms," Algorithmics of large and complex networks. Springer. pp. 117–13, 2009.
 R Bellman, "On the Theory of Dynamic Programming," Proceedings of the National Academy of Sciences, 1952.
 Bertsekas, D. P., J. N. Tsitsiklis, "Neuro-dynamic programming: an overview," Decision and Control, 1995, Proceedings of the 34th IEEE Conference on. Vol. 1. IEEE, 1995.
 Sakoe, Hiroaki, et al., "Speaker-independent word recognition using dynamic programming neural networks." Acoustics, Speech, and Signal Processing, 1989. ICASSP-89., 1989 International Conference on. IEEE, 1989.
 Morimoto, Jun, G. Zeglin, C. G. Atkeson, "Minimax differential dynamic programming: Application to a biped walking robot," Intelligent Robots and Systems, 2003.(IROS 2003). Proceedings. 2003 IEEE/RSJ International Conference on. Vol. 2. IEEE, 2003.
 Willms, A. R., S. X. Yang, “An efficient dynamic system for real-time robot-path planning,” Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on 36.4 (2006): 755-766.
 Yang, Simon X., Max Meng, “An efficient neural network approach to dynamic robot motion planning,” Neural Networks 13.2 (2000): 143-148.
 Kala, Rahul, A. Shukla, R. Tiwari, “Robot path planning using dynamic programming with accelerating nodes,” Paladyn 3.1 (2012): 23-34.
 D. Tamilselvi, P. Rajalakshmi, S. M. Shalinie, “Dynamic programming agent for mobile robot navigation with moving obstacles,” Intelligent Agent & Multi-Agent Systems, 2009. LAMA 2009 International Conference on IEEE, 2009.
 R. Bellman, "The theory of dynamic programming," No. P-550. RAND CORP SANTA MONICA CALIF, 1954.
 R. Bellman, R. E., "Dynamic Programming.” Princeton University Press, Princeton, NJ. Republished 2003: Dover, ISBN 0-486-42809-5.
 Manhattan Tourist Problem
 Huang, Qiang, et al., "Planning walking patterns for a biped robot," Robotics and Automation, IEEE Transactions on 17.3 (2001): 280-289.
 Gregorio, Pedro, M. Ahmadi, M. Buehler, "Design, control, and energetics of an electrically actuated legged robot," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on 27.4 (1997): 626-634.
 Harlan, R. M., D. B. Levine, S. McClarigan, "The Khepera robot and the kRobot class: a platform for introducing robotics in the undergraduate curriculum," ACM SIGCSE Bulletin. Vol. 33. No. 1. ACM, 2001.
 Shayang Ye Inc.
 Z. Nehari, "Conformal mapping," Courier Dover Publications, 2012.
 Driscoll, T. A., L. N. Trefethen, "Schwarz-Christoffel Mapping," No. 8. Cambridge University Press, 2002.
 Peirce, C. S., “The new elements of mathematics: Mathematical miscellanea,” Vol. 1. Mouton, 1976.
 List of map projections, Wikipedia.
 H. Bottomley, “Between the Sinusoidal projection and the Werner: an alternative to the Bonne,” Cybergeo: European Journal of Geography (2003).
 Snyder, J. Parr, “Map projections – A working manual,” No. 1395. USGPO, 1987.
 V. Wijk, J. J., "Unfolding the earth: myriahedral projections." The Cartographic Journal” 45.1 (2008): 32-42.
 Deetz, C. Henry, O. S. Adams, "Elements of map projection with applications to map and chart construction," No. 68. US Government Printing Office, 1921.
 Miller, O. Maitland, "Notes on cylindrical world map projections," Geographical Review (1942): 424-430.
 Conformal Transformation: From Circle to Square
 I. Markina, "Potential Theory: The Origin and Application."
 Wiimote, Nintendo
 L. Jones, J. E., "On the Determination of Molecular Fields", Proc. R. Soc. Lond. A 106 (738): 463–477, 1924.