Proposal for a New Bug Algorithm: Combo Bug
Discipline: Computer Sciences and Information Management
Session: 4
Room: 3 - Hanover C
Izabella Valero - The University of Texas Rio Grande Valley
Co-Author(s): Dr. Qi Lu, The University of Texas Rio Grande Valley, Edinburg, TX
Bug algorithms are widely recognized for their ability to navigate environments using local sensor data, offering low computational cost and simplicity. However, their reliance on heuristics like the m-line and basic obstacle-avoidance mechanisms often lead to inefficiencies, including excessive path lengths or entrapment in cyclical loops. This research hypothesizes that combining the structured approach of m-line algorithms with adaptive, ‘common sense’ navigation can create a more efficient and robust algorithm for obstacle avoidance in environments with complex geometries. Such an advancement is particularly significant for robotics applications in time-critical and resource-limited scenarios, such as search and rescue missions.
To test this hypothesis, we implemented various established Bug algorithms, including Bug0, Bug1, Bug, Alg1, Alg2, Rev1 and Rev 2, using state diagrams and simulated tailored environments using Webots. Control environments were created with known traps, obstacle arrangements designed to induce looping behavior. These algorithms were analyzed for their path lengths, ability to escape traps, and computational requirements. Key distinctions were identified, particularly the use of the m-line heuristic for goal-directed navigation and the reliance on local adaptability (common sense’) to avoid traps.
Building on these observations, we developed a new algorithm that integrates a secondary, dynamic m-line to augment ‘common sense’ navigation. The dynamic m-line is constructed in real-time based on environmental feedback, allowing the robot to escape traps where traditional ‘common sense’ methods fail, while maintaining shorter paths in scenarios where m-line algorithms underperform. Simulations demonstrated the hybrid algorithm’s potential in outperforming existing approaches in environments with complex obstacles, achieving reduced path lengths and improved success rates in trap scenarios.
Preliminary results suggest the hybrid algorithm achieves a balance between structured goal-directed behavior and local adaptability, improving efficiency and robustness. Future research will focus on conducting a comparative analysis of the new algorithm against established methods in both simulations and real-world scenarios, assessing metrics such as path length and time-to-goal. Additionally, we aim to explore the algorithm’s scalability to larger, dynamic environments, further validating its utility in robotics applications.
Funder Acknowledgement(s): NSF CISE MSI, NSF Expand AI
Faculty Advisor: Dr. Qi Lu, qi.lu@utrgv.edu
Role: In this research I contributed to the development and simulation of the new bug algorithm aimed at improving obstacle avoidance in complex environments. My work involved analyzing and simulating existing bug algorithms, evaluating their path lengths, trap-escaping abilities and computational demands. Based on these analyses, I formulated and implemented a new algorithm, integrating a dynamic m-line for adaptive navigation. I conducted simulations to further validate the performance and document preliminary results for future analysis.