BUG-0, 1, 2 ALGORITHMS AND PETRI NETS’ MODELS

Abstract

In this work, Bug-0, Bug-1 and Bug-2 algorithms proposed by Lumelski and Stepanov for route planning in a 2B environment in a configuration with unknown obstacles, where the coordinates of the reachable target from the starting point are known, are introduced. Observation of the operation of these algorithms is important for understanding and interpreting their effects on the applied systems. In this study, Petri nets which are frequently used in modeling and analysis of discrete event systems in the modeling of such algorithms are also discussed and the functioning of the algorithms is handled through these models which provides major convenience to monitor and predict the operation.

Keywords

• Bug-0-1-2 Algorithms
• Modeling
• Petri Net

BUG-0, 1, 2 ALGORİTMALARI VE PETRİ AĞI MODELLERİ

Abstract

Bu çalışmada öncelikle, 2B bir ortam içerisinde bilinmeyen engellerin bulunduğu, gidilecek hedefin koordinatlarının bilindiği ve bu hedefin bir başlangıç noktasından ulaşılabilir olduğu bir konfigürasyon içerisinde güzergâh planlaması yapılmasına yönelik Lumelski ve Stepanov tarafından önerilen Bug-0, Bug-1 ve Bug-2 algoritmaları tanıtılmıştır. Sözü edilen algoritmaların işleyişinin gözlemlenmesi uygulanacakları sistemler üzerindeki etkilerinin anlaşılması ve yorumlanması açısından önemlidir. Bu çalışmada sözkonusu algoritmaların modellenmesinde kesikli olay sistemlerinin modellenmesi ve analizinde sıklıkla kullanılan Petri ağları ele alınmış ve algoritmaların işleyişi bu modeller üzerinden ele alınarak işleyişin izlenmesi ve öngörülmesinde büyük kolaylık sağlanmıştır.

Keywords

• Bug-0-1-2 Algoritmaları
• Modelleme
• Petri Ağı

References

1. Choset H, Lynch KM ve Hutchinson S. Principles of Robot Motion: Theory, Algorithms, and Implementations. ABD: M.I.T. Press, 2005.
2. Yufka A ve Parlaktuna O. Performance Comparison of the BUG Algorithms for Mobile Robots. 5. “International Symposium on Advanced Technologies” Uluslararası Konferansı; 13–15 Mayıs 2009; Karabük, Türkiye. pp. 61-65.
3. Yufka A ve Parlaktuna O. Performance Comparison of the BUG's Algorithms for Mobile Robots. “International Symposium on INnovations in Intelligent Systems and Applications” Uluslararası Konferansı; 29 Haziran–1 Temmuz 2009; Trabzon, Türkiye. pp. 111-146.
4. Lumelsky VJ ve Stepanov A. Dynamic path planning for a mobile automaton with limited information on the environment. IEEE Transaction Automatic Control 1986; 31: 1058-1063.
5. Sankaranarayanan A ve Vidyasagar M. A New Path Planning Algorithm for Moving a Point Object Amidst Unknown Obstacles in a Plane. “Robotics and Automation” Uluslararası Konferansı; 13–18 Mayıs 1990; Cincinnati, OH, USA: IEEE. pp. 3:1930–1936.
6. Cassandras CG ve Lafortune S. Introduction to Discrete Event Systems, Second Edition. US, ABD: Springer, 2008.
7. M. Zhou ve F. DiCesare, Petri net Synthesis for Discrete Event Control of Manufacturing Systems, Kluwer Academic, Norwell, MA, 1993.
8. Yufka A ve Aybar A. BUG Algorithm Analysis using Petri net. 8’inci “Electrical and Electronics Engineering” Uluslararası Konferansı; 28–30 Kasım 2013; Bursa, Türkiye. IEEE. pp. 507-511.

9. Abelson H ve Disessa A. Turtle Geometry. Cambridge, MA, ABD: M.I.T. Press, 1980.