JCSE, vol. 2, no. 4, pp.321-338, 2008

DOI:

A Modified Multiple Depth First Search Algorithm for Grid Mapping Using Mini-Robots Khepera

Sally El-Ghoul, Ashraf S. Hussein, M. S. Abdel Wahab U. Witkowski, U. Ruckert
Faculty of Computer and Information Sciences, Ain Shams University, Egypt|System and Circuit Technology, Heinz Nixdorf Institute, Paderborn University, Germany

Abstract: This paper presents a Modified Multiple Depth First Search algorithm for the exploration ofthe indoor environments occupied with obstacles in random distribution. The proposedalgorithm was designed and implemented to employ one or a team of Khepera II mini robots forthe exploration process. In case of multi-robots, the BlueCore2 External Bluetooth module wasused to establish wireless networks with one master robot and one up to three slaves. Messagesare sent and received via the module’s Universal Asynchronous Receiver/Transmitter (UART)interface. Real exploration experiments were performed using locally developed teleworkbenchwith various autonomy features. In addition, computer simulation tool was also developed tosimulate the exploration experiments with one master robot and one up to ten slaves.Computer simulations were in good agreement with the real experiments for the consideredcases of one to one up to three networks. Results of the MMDFS for single robot exhibited 46%reduction in the needed number of steps for exploring environments with obstacles incomparison with other algorithms, namely the Ants algorithm and the original MDFS algorithm.This reduction reaches 71% whenever exploring open areas. Finally, results performed usingmulti-robots exhibited more reduction in the nee

Keyword: No keyword

Full Paper:   241 Downloads, 4082 View