臺灣博碩士論文加值系統

狀態估測為移動式機器人定位之主要問題。為此，已發展高斯與無參數濾波器以解決此問題。在本論文中，比較假設量測雜訊為高斯雜訊之擴展型卡爾曼?波器與未假設量測雜訊機率分佈之粒子濾波器。在案例研究中，應用估測移動式機器人之狀態向量與取得里程計和距離感測元件之量測量。本論文顯示在此種定位案例，粒子濾波器較擴展型卡爾曼?波器擁有改善的表現與更寬廣的應用，但粒子濾波器之計算量相對亦較高。

State estimation is a major problem in mobile robot localization. To this end Gaussian and nonparametric filters have been developed. In this thesis, the extended Kalman filter which assumes Gaussian measurement noise is compared to the particle filter which does not make any assumption on the measurement noise distribution. As a case study, the estimation of the state vector of a mobile robot is used and measurements are available from both odometer and ranger sensors. It is shown that in this kind of localization, the particle filter has improved performance and has wider applications than the extended Kalman filter, at the cost of more demanding computations.

ABSTRACT I
ACKNOWLEDGEMENTS II
TABLE OF CONTENTS III
LIST OF TABLES VI
LIST OF FIGURES VIII
CHAPTER ONE INTRODUCTION 1
1.1 Motivation 1
1.2 Related Work 3
1.3. Contributions of the Work 4
CHAPTER 2 MOBILE ROBOT LOCALIZATION 6
2.1 The Robot Location Problem 6
2.1.1 Problem Statements 6
2.2 Navigational Maps 7
2.2.1 Occupancy Grids 8
2.2.2 Feature Maps 10
2.2.3 Topological Maps 12
2.3 Relative and Absolution Position Measurement 15
2.3.1 Relative Position Measurement 15
2.3.2 Absolute Position Measurement 17
CHAPTER 3 KALMAN FILTER 21
3.1 Kalman Filters 21
3.2 Overview of Kalman filter 22
3.3 Concepts 26
3.3.1 State Estimator 27
3.3.2 Beliefs 27
3.3.3 Prediction-Correction 28
3.4 Assumptions 29
3.4.1 Linear Dynamic System 29
3.4.2 Noise Characteristics 30
3.5 Gaussian Implications 32
3.5.1 System and Measurement Models 33
3.5.2 Gaussian Beliefs 34
3.6 KF Equations 36
3.6.1 Prior Belief 36
3.6.2 Posterior Belief 38
3.7 Linear Kalman Filter 43
3.7.1 Algorithm 43
3.8 Minimum Variance Estimator 48
3.9.1 System Model Revisited 50
3.9.2 Beliefs Revisited 51
3.9.3 KF Prediction Revisited 51
3.10 Extended Kalman Filter Localization 54
3.10.1 Predictive Position Tracking 54
CHAPTER 4 PARTICEL FILTER 72
4.1 Probability Density Functions 72
4.2 Bayesian Reasoning 73
4.3 Particle Filter 75
4.3.1 Prediction. 76
4.3.2 Resembling 81
4.4. Experiment results 83
CHAPTER 5 CONCLUSION AND FUTURE WORK 99
REFERENCES 101

[1] T. Dean and M. Boddy, An analysis of time-dependent planning, In Proc. of the National Conference on Artificial Intelligence, pp. 49–54, 1988.
[2] J. Borenstein, H. Everett, L. Feng, and D. Wehe, Mobile robot positioning: Sensors and techniques, Journal of Robotic Systems, pp. 231-249, 1997.
[3] J. Borenstein and L. Feng, Measurement and correction of systematic odometry errors in mobile robots, IEEE Transactions on Robotics and Automation vol. 12 pp. 869-880, 1996.
[4] M. Grewal and A. Andrews. Kalman filtering: theory and practice. New Jersey Prentice-Hall, Inc., Englewood Cliffs, 1993.
[5] E. T. Boumgartner and J. D. Yoder, Enhancing mobile robot location estimates using sensor fusion, Dynamic Systems and Control Division vol. 57, 1995.
[6] N. Yang, W. F. Tian, Z. H. Jin, and C. B. Zhang. Particle filter for sensor fusion in a land vehicle navigation system, Measurement Science and Technology vol. 16. Institute of Physics Publishing, 2005.
[7] S. Thrun, W. Burgard and D. Fox . Probabilistic Robotics. MIT Press, 2005.
[8] F. Gustafsson, F. Gunnarsson, N. Bergman and U. Forssel, Particle filters for positioning, navigation and tracking, IEEE Transactions on Signal Processing - Special Issue on Monte Carlo Methods for Statistical Signal Processing, vol. 50, no.2, pp. 425-437, 2002.
[9] P. Li and V. Kadirkamanathan, Particle filtering based likelihood Ratio Approach to Fault Diagnosis in Nonlinear Stochastic Systems, IEEE Transactions on Systems, Man and Cybernetics - Part C: Applications and Reviews, vol. 31, no.3, pp. 337-343, 2001.
[10] V. Kadirkamanathan, M. H. Jaward, S.G. Fabri and M. Kadirka-manathan, Particle filters for recursive model selection in linear and nonlinear system identification, Proc. 39th IEEE Conference on Decision and Control, vol. 3, pp. 2391-2396, 2000.
[11] R. Karlsson and M. Norrlof, Bayesian position estimation of an industrial robot using multiple sensors, IEEE International Conference on Control Applications, Taipei, Taiwan, pp. 303-308, 2004.
102
[12] G. W. Ng. Intelligent Systems - Fusion: tracking and control. Research Studies Press Ltd ed., 2003.
[13] R. Smith and P. Cheeseman, On the representation of spatial uncertainty, Journal of Robotics Research, pp. 56-68, 1987.
[14] J. F. Leonard and H. Durrant-Whyte, Mobile robot localization by tracking geometric beacons, IEEE Transactions Robotics and Automations, pp. 376-382, June 1991.
[15] L. Moreno, J.M. Armingol, A. de la Escalera, and M. A. Salichs, Global integration of ultrasonic sensors information in mobile robot localization, In Proceedings of the Ninth Annual Conference on Advanced Robotics, pp. 283-288, October 1999.
[16] J. Z. Sasiadek and P. Hartana, Sensor data fusion using Kalman filter, In Proceedings of the Third International Conference on Information Fusion, vol. 2, pp. 19-25, 2000.
[17] J. S. Guttman, W. Hatzack, I. Herrmann, B. Nebel, F. Rittinger, A. Topor, and T. Weigel, Reliable self-localization, multirobot sensor integration, accurate path-planning and basic soccer skills: playing an effective game of robotic soccer, In Proceedings of the Ninth Annual Conference on Advanced Robotics, pp. 289-296, October 1999.
[18] E. Kiriy, A Localization system for autonomous golf course mowers, Thesis, Dept. of Electrical Engineering, McGill University, November 2002.
[19] R. E. Kalman, A new approach to linear filtering and prediction problems, Transactions of the ASME, pp. 35-45, 1960.
[20] M. Pitt and N. Shephard, Filtering via simulation: auxiliary particle filter, Journal of American Statistical Association, vol. 94, pp. 590-599, 1999.
[21] A. Doucet, J. F. G. de Freitas and N. J. Gordon. Sequential Monte Carlo methods in practice. Springer, 2001.
[22] S. Thrun, D. Fox, W. Burgard, and F. Dellaert, Robust Monte Carlo localization for mobile robots, Artificial Intelligence, vol. 128, pp. 99-141, 2001.
[23] D. Kortenkamp, R. Bonasso and R. Murphy. AI-based Mobile Robots: Case studies of successful robot systems. MIT Press, Cambridge, 1998.
[24] I. J. Cox, Blanche: Position estimation for an autonomous robot vehicle, Autonomous Mobile Robots: Control, Planning, and Architecture , IEEE Computer Society Press, vol. 2, pp. 285-292, 1991.
[25] D. Fox, W. Burgard, and S. Thrun, Markov localization for mobile robots in dynamic environments, Journal of Artificial Intelligence Research 11, pp. 391-427, 1999.
[26] T. Bailey, Mobile robot localisation and mapping in extensive outdoor environments, Ph.D thesis, August 2002.
[27] A. Elfes, Occupancy grids: A stochastic spatial representation for active robot perception, In Sixth Conference on Uncertainty in AI, 1990.
[28] A. C. Schultz and W. Adams, Continuous localization using evidence grids, International Conference on Robotics and Automation, pp. 2833–2839, 1998.
[29] S.T. Pfister, K. L. Kriechbaum, S.I. Roumeliotis, and J.W. Burdick, Weighted range sensor matching algorithms for mobile robot displacement estimation, IEEE International Conference on Robotics and Automation, 2002.
[30] B. Yamauchi, A. Schultz, and W. Adams, Mobile robot exploration and map-building with continuous localization, IEEE International Conference on Robotics and Automation, pp. 3715–3720, 1998.
[31] K. Konolige and K. Chou, Markov localization using correlation, International Joint Conference on Articial Intelligence, pp. 1154–1159, 1999.
[32] F. Dellaert, D. Fox, W. Burgard, and S. Thrun, Monte Carlo localization for mobile robots, IEEE International Conference on Robotics and Automation, pp. 1322–1328, 1999.
[33] E. M. Nebot and D. Pagac, Quadtree representation and ultrasonic information for mapping an autonomous guided vehicle’s environment, International Journal of Computers and Their Applications, vol. 2, pp. 160–170, 1995.
[34] A. D. W. Burgard, D. Fox, and A.B. Cremers, Integrating global position estimation and position tracking for mobile robots: The dynamic markov localization approach, In IEEE/RSJ International Conference on Intelligent Robots and Systems, 1998.
[35] M. S. A.Stevens and H.F. Durrant-Whyte, OxNav: Reliable autonomous navigation, IEEE International Conference on Robotics and Automation, pp. 2607-2612, 1995.
[36] J.J. Leonard, H. F. Durrant-Whyte, and I.J. Cox, Dynamic map building for an autonomous robot, International Journal of Robotics Research, vol. 11, pp. 286-298, 1992.
[37] S. S. Blackman and R. Popoli. Design and analysis of modern tracking systems. Artech House Radar Library, 1999.
[38] J. J. Leonard and H. F. Durrant-Whyte. Directed sonar sensing for mobile robot navigation. Kluwer Academic, 1992.
[39] H. F. Durrant-Whyte, An autonomous guided vehicle for cargo handling applications, International Journal of Robotics Research, vol. 15, 1996.
[40] B. Kuipers and Y. T. Byun, A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations, Journal of Robotics and Autonomous Systems, vol. 8, pp. 47-63, 1991.
[41] Merriam-Webster. Merriam-Webster's Collegiate Dictionary. 10th Edition. Merriam-Webster, Inc. Springfield, 1998.
[42] D. Kortenkamp, L. D. Baker, and T. Weymouth, Using gateways to build a route map, In IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2209-2214, 1992.
[43] O. Aycard, F. Charpillet, D. Fohr, and J.F. Mari, Place learning and recognition using hidden markov models, IEEE International Conference on Intelligent Robots and Systems, pp. 1741-1746, 1997.
[44] S. P. Engelson and D. V. McDermott, Error correction in mobile robot map learning, IEEE International Conference on Robotics and Automation, pp. 2555-2560, 1992.
[45] S. Argamon-Engelson, Using image signatures for place recognition, vol. 19, pp. 941-951, 1998.
[46] I. Ulrich and I. Nourbakhsh, Appearance- based place recognition for topological localization, IEEE International Conference on Robotics and Automation, pp. 1023- 1029, 2000.
[47] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1959.
[48] J. Borenstein, Control and kinematic design of multi-degree-of-freedom robots with compliant linkage, IEEE Transactions on Robotics and Automation, 1995.
105
[49] S. Shoval and J. Borenstein, Measurement of angular position of a mobile robot using ultrasonic sensors , ANS Conference on Robotics and Remote Systems, pp. 26-28, 1999.
[50] A. I. Kentaro Ishii, Greg Saul, Masahiko Inami, and Takeo Igarashi, Active Navigation Landmarks for a Service Robot in a Home Environment, Proceedings of the 5th ACM/IEEE International Conference on Human Robot Interaction, 2010.
[51] A. Singhal. Issues in Autonomous Mobile Robot Navigation. 1997.
[52] S. Thrun, Bayesian landmark learning for mobile robot localization, Machine Learning pp. 41-76, 1998.
[53] P. S. Maybeck. Stochastic models, estimation and control. Academic Press, Inc, 1979.
[54] J. Taylor. An introduction to error analysis. University Science Books, 1997.
[55] R. Smith and P. Cheeseman, On the estimation and representation of spatial uncertainty, International Journal of Robotics Research, pp. 56-68, 1987.
[56] M. Welling. The Kalman Filter. 2000.
[57] G. Welch and G. Bishop. An Introduction to the Kalman Filter. Chapel Hill 2001.
[58] Y. Bar-Shalom, X. R. Li, and T. Kirubarajan. Estimation with applications to tracking and navigation. John Wiley and Sons, 2001.
[59] A. Papoulis. Probability, Random Variables, and Stochastic Processes. McGraw-Hill, 1984.
[60] L.D. Stone, C. A. Barlow, and T.L. Corwin. Bayesian multiple target tracking. Artech House, 1999.
[61] S. M. Bozic. Digital and Kalman filtering. Edward Arnold, 1994.
[62] S. I. Roumeliotis and G. A. Bekey, Bayesian estimation and Kalman filtering: A unified framework for mobile robot localization, IEEE International Conference on Robotics and Automation, pp. 2985-2992, 2000.
[63] N.J. Gordon, D. J. Salmond, and A.F.M. Smith, Novel approach to nonlinear/non-gaussian bayesian state estimation, IEE Proceedings For Radar and Signal Processing, pp. 107-113, 1993.
[64] J. Borenstein, H. R. Everett, and L. Feng. Navigating mobile robots: Systems and techniques. A K Peters, Wellesley, MA, 1996.
[65] J.S. Liu, R. Chen, and Tanya Logvinenko. A theoretical framework for sequential importance sampling and resampling. Springer Verlag, 2001.
[66] J. Liu and R. Chen, Sequential Monte Carlo methods for dynamic systems, Journal of American Statistical Association, vol. 93, 1998.