Eş Zamanlı Konum Belirleme ve Haritalama Probleminde Yeni Bir Durum Tahmin Yöntemi Olarak Parçacık Akış Filtresi

Erol DUYMAZ, Abdullah Ersan OGUZ, Hakan Temeltas
1.155 234

Öz


Günümüzde özellikle askeri uygulamalarda operatörsüz platform kullanımı düşüncesi yaygınlaşmış olmakla birlikte özellikle insansız ya da otonom araçlar geliştirilme amaçlarına uygun olarak verilen görevin tamamını veya bir bölümünü kendi kendine yapması beklenen araçlar olarak ortaya çıkmıştır. Bu isteği karşılayarak güvenli bir otonom seyrüsefer yapabilmenin ön koşulu ise hava aracının konumunun doğru şekilde bilinmesidir. Günümüzde konum belirlemenin en bilinen yöntemi Küresel Uydu Yönbulum Sistemlerinin (KUYS) kullanımıdır. KUYS’nin olmadığı veya erişilemediği ortamlarda araç konumunun ya da seyrüsefer yapılan bölgenin haritasının da bilenmemesi durumunda güvenli konum belirlemek oldukça zor bir problemdir. Eş Zamanlı Konumlama ve Haritalama (EZKH) aynı anda hem platform pozisyonu hem de ortam haritası belirlenmesi yöntemine verilen addır.

 

Son çeyrek yüzyılda ortaya çıkan EZKH problemi, 2000’li yıllardan başlayarak kara, deniz, hava platformları için uyarlanmış olmakla birlikte Kalman Filtresi (KF) tabanlı Genişletilmiş Kalman Filtresi (DKF) ve Dağıtılmış Kalman Filtresi (GKF) gibi parametrik filtre yaklaşımları yanında Parçacık Filtresi (PF) gibi non-parametrik metotlardan oluşan durum tahmin yöntemleri ve model ya da grafik tabanlı üst seviye kontrol amaçlayan özellikle de görüntü işleyen teknikler kullanılmıştır. Platform, araç, sensör tipi ve kara, deniz, hava gibi ortam türü başlıklarında oldukça fazla farklılıklar göstermesi nedeniyle EZKH probleminin sınıflandırma (taxonomy) yoluyla performans analizi ihtiyacından bahsedilebilir.

 

 

Bu çalışmada belirsizlik altında tahmin araçlarının performans analizleri ile birlikte literatürde ilk kez olarak Parçacık Akış Filtresi (PAF) tabanlı bir EZKH yapısı filtrenin matematik temelleri, filtre analizleri, otonom bir yer aracı ve sensör modelini de içerecek şekilde verilmiştir. Benzetim sonuçlarına göre parçacık akış filtresi tabanlı EZKH performansının hesaplama maliyeti nedeniyle bazı gerçek zamanlı uygulamalardaki zorluklarına rağmen literatürde daha önce yer almış diğer tahmin yöntemleriyle karşılaştırıldığında özellikle belirsizlikleri daha düşük algılayıcılar kullanan ölçüm ortamlarında parçacık filtresi yapısında ortaya çıkan dejenerasyon sorununu ortadan kaldırarak daha başarılı sonuçlar verdiği ve bu nedenle tercih edilebileceği görülmüştür.


Anahtar kelimeler


Parçacık Akış Filtresi, Belirsizlik Altında Tahmin, Eş Zamanlı Konumlama ve Haritalama, Olasılıksal Sinyal İşleme, Seyrüsefer

Tam metin:

PDF


Referanslar


R.Smith and P.Cheesman, On the Representation Of Spatial Uncertainty, Int. J. Robot. Res., Vol. 5, No. 4, pp. 56–68, 1987

G.Dissanayake, H.F.Durrant-Whyte and T. Bailey, A Computationally Efficient Solution to the Simultaneous Localisation and Map Building (SLAM) Problem, ICRA, 2000

Tim Bailey and Hugh Durrant-Whyte, Simultaneous Localization and Mapping (SLAM): Part I The Essential Algorithms., IEEE Robotics and Automation Magazine, 2006

Tim Bailey and Hugh Durrant-Whyte, Simultaneous Localisation and Mapping (SLAM): Part II State of the Art., IEEE Robotics and Automation Magazine, September 2006

J.Andrade-Cetto, and A.Sanfeliu, The Effects of Partial Observability in SLAM, IEEE Int. Conf. Robot. Automat., New Orleans, pp.397-402, 2004

M.Bryson, and S.Sukkarieh, Observability Analysis and Active Control for Airborne SLAM, IEEE Transaction on Aerospace and Electronic Systems, Vol.44, No.4, pp.261-280, 2008

G.P.Huang, N.Trawny, A.I.Mourikis and S.I.Roumeliotis, Observability-based consistent EKF estimators for multi-robot cooperative localization, Autonomous Robots, Volume 30, Number 1, pp. 99-122, 2011

T.Vidal-Calleja, J.Andrade-Cetto and A.Sanfeliu, Conditional for Suboptimal Filter Stability in SLAM, IEEE Inernational Conferance on Intelligent Robots and Systems, Sendai Japan, 2004

T.Bailey, J.Nieto, J.Guivant, M.Stevens and E.Nebot, Consistency of the EKF-SLAM Algorithm, IROS’06 IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, China, 2006

J.A.Castellanos, J.Neira, J.Tardos, Limits to The Consistency of EKF-Based SLAM, IAV2004 5th IFAC Symp. on Intelligent Autonomous Vehicles, 2004

J.Kim and S.Sukkarieh, Airborne Simultaneous Localisation and Map Building, IEEE Int. Conf. Robot. Automat., Taipei Taiwan, 2003

J.Kim, S.Sukkarieh, S.Wishart, Real-Time Navigation, Guidance and Control of a UAV Using Low-Cost Sensors, International Conferance of Field and Service Robotics, Yamanashi, Japan, pp.95-100, 2003

J.Kim, S.Sukkarieh, Autonomous Airborne Navigation in Unknown Terrain Environments, IEEE Transaction on Aerospace and Electronic Systems, Vol.40, No.3, pp.1031-1044, 2004

S.Kurnaz, O.Cetin, Autonomous Navigation and Landing Tasks for Fixed Wing Small Unmanned Aerial Vehicles, Acta Polytechnica Hungarica Vol. 7, No. 1, 2010

AntSLAM: Global Map Optization Using Swarm Intelligence in Non-Static Environments, R.Iser, F.M.Wahl, IEEE International Conference on Robotics and Automation, 2010

Simultaneous Localisation and Mapping Using Extended Kalman Filter, S.Yavuz, Z.Kurt, M.S.Biçer, IEEE 17th Signal Processing and Communications Applications Conference, April 2009

Recasting SLAM-Towards Improving Efficiency and Platform Independency, J.H.Kim, S.Sukkarieh, Robotic Research STAR 15, pp.399-408, 2005

Simultaneous Mapping and Localization with Sparse Extended Information Filters, S.Thrun, Y.Liu, D.Koller, A.Ng, Z.Ghahramani, H.Durrant-Whyte, International Journal of Robotics Research, Vol 23, pp.693-716, 2004

Simultaneous Mapping and Localization with Sparse Extended Information Filters; Theory and Initial Results, S.Thrun, S.Sukkarieh, Robotics and Autonomous Systems, Vol 55, pp.62-71, 2007

Mobile robot navigation based on interactive SLAM with an intelligent space , Hashikawa, F. ; Morioka, K.,8th International Conference on Ubiquitous Robots and Ambient Intelligence (URAI), 2011

Autonomous Airborne Navigation in Unknown Terrain Environments, J.Kim, S.Sukkarieh, IEEE Transaction on Aerospace and Electronic Systems, Vol.40, No.3, pp.1031-1044, 2004

An Omni-directional vSLAM based on spherical camera model and 3D modeling 10th World , Guofeng Tong ; Zizhang Wu ; NingLong Weng ; Wenbo Hou,Congress on Intelligent Control and Automation (WCICA), 2012

Mobile robot localization using odometry and kinect sensor , Ganganath, N. ; Leung, H.,IEEE International Conference on Emerging Signal Processing Applications (ESPA), 2012

A video tracking algorithm for UAV based on differential evolution particle filter , Han Yu; Wang Longsheng ; Yu Yunzhi,31st Chinese Control Conference (CCC), 2012

Sparse optical flow regularization for real-time visual tracking , Spruyt, V. ; Ledda, A. ; Philips, W.,IEEE International Conference on Multimedia and Expo (ICME), 2013

Scene matching based EKF-SLAM visual navigation , Li Yaojun ; Pan Quan ; Zhao Chunhui ; Yang Feng, 31st Chinese Publication Control Conference (CCC), Page(s): 5094-5099, 2012

Autonomous Flight in GPS-Denied Environments Using Monocular Vision and Inertial Sensors, Allen D. Wu, Eric N. Johnson, Michael Kaess, Frank and Girish Chowdhary, Journal Of Aerospace Informatıon Systems Vol. 10, No. 4, April 2013

Unmanned Aerial Vehicle Localization Based on Monocular Vision and Online Mosaicking, A New Mapping Framework, F.Caballero, L.Merino, J.Ferruz, A.Ollero, J Intel Robot Systems, Vol 55, pp. 323-343, 2009

J.Welle, D.Schulz,T.Bachran ve A.B.Cremers,”Optimization Techniques for Laser-Based 3D Particle Filter SLAM”, IEEE Internatonal Conference on Robotics and Automation,Alaska,USA, May 2010

Mobile robot parallel PF-SLAM based on OpenMP , Songmin Jia ; Xiaolin Yin ; Xiuzhi Li,IEEE International Conference on Robotics and Biomimetics (ROBIO), 2012

Distributed parallel processing of mobile robot PF-SLAM , Xiuzhi Li ; Songmin Jia; Ke Wang ; Xiaolin Yin, International Conference on Automatic Control and Artificial Intelligence ACAI 2012,

CUDA accelerated robot localization and mapping , Haiyang Zhang, Fred Martin, IEEE International Conference on Technologies for Practical Robot Applications (TePRA), 22-23 April 2013,Woburn, MA

Real-time 3D simultaneous localization and map-building for a dynamic walking humanoid robot,Sukjune Yoona, Seungyong Hyunga, Minhyung Leea, Kyung Shik Roha, SungHwan Ahna, Andrew Geeb, Pished Bunnunb, Andrew Calwayb & Waterio W. Mayol-Cuevasb, Advanced Robotics Volume 27, Issue 10, pages 759-772, 2013

A Hybrid SLAM Representation for Dynamic Marine Environments, C.Bibby, I.Reid, IEEE International Conference on Robotics and Automation, 2010

Implementation of a 4D fast SLAM including volumetric sum of the UAV , Aditya, A.,Sixth International Conference on Sensing Technology (ICST), 2012

Overview on simultaneous localization and mapping for uninhabited aerial vehicle vision 30th , Wang Xi-Bin ; Zhao Guo-Rong ; Pan Shuang,Chinese Control Conference (CCC), 2011

Monocular visual SLAM for small UAVs in GPS-denied environments , Chaolei Wang ; Tianmiao Wang ; Jianhong Liang ; Yang Chen ; Yicheng Zhang ; Cong Wang,IEEE International Conference on Robotics and Biomimetics (ROBIO), 2012

Unscented FastSLAM for UAV, Shi Jianli ; Pan Shuang ; Wu Yugiang ; Wang Xibin, International Conference on Computer Science and Network Technology (ICCSNT), 2011

6DoF SLAM aided GNSS/INS Navigation in GNSS Denied and Unknown Environments, J.Kim, S.Sukkarieh, Journal of Global Positioning Systems, Vol.4, No.1-2, pp.120-128, 2005

Real-Time Implementation of Airborne Inertial-SLAM, J.Kim, S.Sukkarieh, Robotics and Autonomous Systems, Vol 55, pp.62-71, 2007

Extended Kalman Filter Based Airborne Simultaneous Localization And Mapping, A.E. Oguz , H. Temeltas,, Journal of Aeronautics and Space Technologies, Vol.6, No.2, pp.69-74, 2013

The Effect of Partial Observality When Building Fully Correlated Maps, J.Andrade-Cetto, A.Sanfeliu, IEEE Transaction on Robotics, Vol.21, No.4, pp. 771-777, August 2005

Conditional for Suboptimal Filter Stability, T.Vidal-Calleja, J.Andrade-Cetto and A.Sanfeliu, IEEE Inernational Conferance on Intelligent Robots and Systems, 2004

The Effect of Partial Observability in SLAM, J.Andrade-Cetto, A.Sanfeliu, IEEE Conferance on Robotics & Automation, New Orleans, April 2004

Estimator Stability Analysis in SLAM, T.Vidal-Calleja, J.Andrade-Cetto, A.Sanfeliu, IAV2004 5th IFAC Symp. on Intelligent Autonomous Vehicles, 2004

Convergence and consistency analysis for FastSLAM, Liang Zhang ; Xu-jiong Meng ; Yao-wu Chen, IEEE Intelligent Vehicles Symposium, 2009

Consistency of the EKF-SLAM Algorithm, T.Bailey, J.Nieto, J.Guivant, M.Stevens, E.Nebot, International Conference on Intelligent Robots and Systems, October 2006

Convergence Analysis for Extended Kalman Fitler based SLAM, S.Huang, G.Disanayake, IEEE International Conference on Robotics and Automation Beijing, China, May 2006

Analysis and Improvement of the Consistency of Extended Kalman Filter based SLAM, G.Huang, A.I. Mourikis, S.I.Roumeliotis, IEEE International Conference on Robotics and Automation pp.473-479, 2008

A First-Estimates Jacobian EKF for Improving SLAM Consistency, G.Huang, A.I. Mourikis, S.I.Roumeliotis, 11th International Symposium on Experimental Robotics, 2008

Generalized Analysis and Improvement of the Consistency of EKF-based SLAM, G.Huang, A.I. Mourikis, S.I.Roumeliotis, Technical Report, MARS Lab, University of Minnesota, 2008

Simultaneous Localisation and Map Building Using Split Covariance Intersectio, S.J.Julier, J.K.Uhlman, International Conference on Intelligent Robots and Systems, November 2001

Limits to the Consistency of EKF-Based SLAM, J.A.Castellanos, J.Neira, J.D.Tardos, IAV2004 5th IFAC Symp. on Intelligent Autonomous Vehicles, 2004

Convergence and Consistency Analysis for Extended Kalman Filter based SLAM, S.Huang, G.Disanayake, IEEE Transactions on Robotics Vol.23, No.5, pp.1036-1049, 2007

Observability-based Rules for Designing Consistent EKF SLAM Estimators, G.P.Huang, A.I.Mourikis, S.I.Roumeliotis, The International Journal of Robotics Research, Vol.29, No.5, pp. 502-528, April 2010

“On The Consistency Analyzing of A-SLAM for UAVs navigating in GNSS Denied Environment”, A.E.Oguz, H.Temeltas, Acta Polytechnica Hungarica Vol.10, No.4, pp.119-132, 2013Robust Airborne 3D Visual Simultaneous Localization and Mapping with Observability and Consistency Analysis, A.Nemra, N.Aouf, J Intel Robot Systems, Vol 55, pp. 345-376, 2009

Observability-constrained Vision-aided Inertial Navigation, Hesch, J.A. Dimitrios, G.K. Bowman, S.L. ve Roumeliotis, S.I. Technical Report, MARS Lab, University of Minnesota, 2012

Efficient particle filter algorithm for ultrasonic sensor-based 2D range-only simultaneous localisation and mapping application , Yang, P.,IET JOURNALS & MAGAZINES, Wireless Sensor Systems, IET Volume: 2 , Issue: 4, Page(s): 394- 401, 2012

Robocentric map joining: Improving the consistency of EKF-SLAM, J.Castellanos, R.Martinez-Cantin, J.D. Tardos, J. Neira, Robotics and Autonomous Systems, Vol 55, pp.21-29, 2007

Dynamic map building for an autonomous mobile robot, J.Leonard, H.Durrant-Whyte, I.Cox, The International Journal of Robotics Research, Vol.11, No.4, pp. 286–298, 1992

The SPmap: A probabilistic framework for simultaneous localization and map building ,J.A.Castellanos, J.M.M.Montiel, J.Neira, J.D.Tardos, IEEE Transactions on Robotics Automation., Vol.15, No.5, pp.948–953, 1999

Robust Mapping And Localization in Indoor Environments Using Sonar Data, J.D.Tardos, J.Neira, P.Newman, J.Leonard, International Journal Robotics Research, Vol.21, No.4, pp.311–330, 2002

Hierarchical SLAM: Real-Time Accurate Mapping of Large Environments, C.Estrada, J.Neira, J.D.TardosIEEE Transactions on Robotics, 2005

Optimal local map size for EKF-based SLAM, L.M.Paz, J.Neira, IROS’06 IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, China, 2006

EKF SLAM updates in O(n) with Divide and Conquer SLAM, L.M.Paz, P.Jensfelt, J.D.Tardos, J.Neira, ICRA'07 IEEE International Conference on Robotics and Automation, , April 2007

Hierarchical Optimization on Manifolds for Online 2D and 3D Mapping, G.Grisetti, R.Kümmerle, C.Stachniss, U.Frese, C.Hertzberg, IEEE International Conference on Robotics and Automation, 2010

Mapping large scale environments by combining Particle Filter and Information Filter, Mohan, M. ; MadhavaKrishna, K., 11th International Conference on Control Automation Robotics & Vision (ICARCV), 2010

Autonomous Exploration and Mapping of Abandoned Mines, S.Thurn, S.Thayer, W.Whittaker, C.Baker, W.Burgard, D.Ferguson, D.Hahnel, M.Montemerlo, A.Morris, Z.Omohundro, C.Reverte, IEEE Robotics and Automation Magazine, 2004

Multisensors Fusion for Simultaneous Localization and Map Building, J.A.Castellanos, J.Neira, J.D.Tardos, IEEE Transaction on Robotics and Automation, Vol.17, No.6, pp. 908-914, December 2001

A Real-time SLAM Algorithm with Optical Flow based Motion Extraction for Autonomous Robot Navigation, O.Şencan, M.Turanlı, H.Temeltaş, S.Kurnaz, S.Bogosyan, International Unmanned Vehicles Workshop UVW2010, 2010

Real-Time Navigation, Guidance and Control of a UAV Using Low-Cost Sensors, J.Kim, S.Sukkarieh, S.Wishart, International Conferance of Field and Service Robotics, Yamanashi, Japan, pp.95-100, 2003

Optimization of the Simultaneous Localization and Map Building Algorithm for Real Time Implementation, J.Guivant, E.Nebot, IEEE Transaction on Robotics and Automation, Vol.17, No.3, pp. 242-257, 2013

Extending Bayesian RFS SLAM to multi-vehicle SLAM , Moratuwage, D. ; Ba-Ngu Vo ; Danwei Wang ; Han Wang,12th International Conference on Control Automation Robotics & Vision (ICARCV), 2012

Simulation Research on Multi-Robot SLAM of Information Filter, Shan Shan Li, Ya Hong Xu, Xiao Long Xu, Ning Hui Zhu, Advances in Mechatronics and Control Engineering Applied Mechanics and Materials (Volumes 278 280), January 2013

Rao-Blackwellized Particle Filters multi robot SLAM with unknown initial correspondences and limited communication, Carlone, L. ; Ng, M.K. ; Jingjing Du ; Bona, B. ; Indri, M., IEEE International Conference on Robotics and Automation (ICRA), 2010

Simulation Research on Multi-Robot SLAM of Information Filter, Shan Shan Li, Ya Hong Xu, Xiao Long Xu, Ning Hui Zhu, Advances in Mechatronics and Control Engineering Applied Mechanics and Materials (Vomarinelumes 278 280), January 2013

Multi-robot Simultaneous Localization and Mapping using Particle Filters, Andrew Howard, , Localization and Mapping Using Only a Rotating FMCW Radar Sensor, Damien Vivet , Paul Checchin; and Roland Chapuis, Internaional Journal of Robotics Research Sensors, 13, 4527-4552, 2013

Multı-Robot Fast SLAM For Large Domains, C.Koperski, AFIT Master Thesis, Marc 2007

Cooperative vSLAM based on UAV application , Xiaodong Li ; Aouf, N.,IEEE International Conference on Robotics and Biomimetics (ROBIO), 2012

Architectures for Cooperative Airborne Simultaneous Localisation and Mapping, M.Bryson, S.Sukkarieh, J Intel Robot Systems, Vol 55, pp. 267-297, 2009

Experimental Research on Cooperative vSLAM for UAVs , Xiaodong Li ; Aouf, N.,Fifth International Conference on Computational Intelligence Communication Systems and Networks (CICSyN), 2013

Just-in-time cooperative simultaneous localization and mapping, Martin, A. ; Emami, M.R., 11th International Conference on Control Automation Robotics & Vision (ICARCV), 2010

An overview of Robot SLAM problem , Liping Qu ; Hongjian Wang,International Conference on Consumer Electronics, Communications and Networks (CECNet), 2011

An Analysis of Simultaneous Localization and Mapping (SLAM) Algorithms, Naminski, Megan R., Honors Projects.Paper 29., 2013

A comparative study on active SLAM and autonomous exploration with Particle Filters, Du J.; Carlone, L. ; Kaouk Ng, M. ; Bona, B. ; Indri, M.,IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM), 2011

Autonomous navigation among large number of nearby landmarks using FastSLAM and EKF-SLAM - A comparative study , Monjazeb, A. ; Sasiadek, J.Z. ; Necsulescu, D.,16th International Conference on Methods and Models in Automation and Robotics (MMAR), 2011

Technical Analysis and Implementation Cost Assessment of Sigma-Point Kalman Filtering and Particle Filtering in Autonomous Navigation Systems, Rigatos, G.G., IEEE 71st Vehicular Technology Conference (VTC 2010-Spring), 2010

Exact particle flow for nonlinear filters: Seventeen dubious solutions to a first order linear underdetermined PDE, Daum, F. ; Huang, J., Conference Record of the Forty Fourth Asilomar Conference on Signals, Systems and Computers (ASILOMAR), 2010

Particle flow for nonlinear filters , Daum, F. ; Huang, J.,IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2011

Particle flow for nonlinear filters, Bayesian decisions and transport, Daum, F. ; Huang, J., 16th International Conference on Information Fusion (FUSION), 2013

Implementation of the Daum-Huang exact-flow particle filter , Ding T.; Coates, M.J.,IEEE Statistical Signal Processing Workshop (SSP), 2012

Performance comparison of GPU-accelerated particle flow and particle filters , Jilkov, V.P. ; Jiande Wu ; Huimin Chen,16th International Conference on Information Fusion (FUSION), 2013.

Implementation and performance of FPGA-accelerated particle flow filter, Charalampidis D.; Jilkov V. P.; Wu J., SPIE Proceedings Vol. 9596, 2015.

Kaiser-Hamming penceresi ve yenilemesiz sayisal süzgeç tasarimi için performans analizi, Avcı K.; Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 2014.

Wall Follower Autonomous Robot Development Applying Fuzzy Incremental Controller, Hanafi D., Abueejela Y. M., Zakaria M.F., Intelligent Control and Automation Vol. 4 No. 1 (2013) , Article ID: 27701, DOI:10.4236/ica.2013. 41003

Estimation with Applications to Tracking and Navigation, Bar-Shalom Y.; Li X. R.; Kirubarajan T., John Wiley and Sons, 2001, pp. 232-145




Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.