YILDIZ Team Description Paper for Virtual Robots Competition 2013

Sırma Yavuz, M. Fatih Amasyalı, Muhammet Balcılar, Yücel Uzun, Khudaydad Mahmoodi, Bilge Yaraş, A. Cüneyt Yavuz

Yıldız Technical University Computer Engineering Department Davutpaşa, İstanbul, 34220, Turkey

http://www.ce.yildiz.edu.tr

Abstract This paper is a short review of technologies developed by YILDIZ team for participating in RoboCup 2013 Virtual Robot Competitions. A short description of message routing algorithm, image enhancement, autonomous navigation and victim detection techniques that are being developed and the initial results of the algorithms are given.

1 Introduction

Probabilistic Robotics Group of Yıldız Technical University, which consists of a team of students and academicians, has been working on autonomous robots since its establishment in 2007. Autonomous robots can perform desired tasks without continuous human guidance which is necessary for Urban Search and Rescue area [1, 2]. Last year's world championship was the second experience of our team on Robocup.. We took second place at Mexico Robocup and Iran Open competitions. We have learned a lot of lessons over two years as following:

• Our user interface is very useful.
• We should determine the coordinates of the air-robot.
• We should develop our autonomous exploration algorithm.
• We should develop our image enhancement algorithm.
• We should develop our automatic victim detection algorithm.
• We should develop our message routing protocol

This year, several developments over all of these systems and they are presented at this report.

The system is designed to have a hierarchical structure, containing different modules responsible of different jobs. Every fundamental part of the main problem divided into modules which can function independently. Normally, each of our virtual robots is intelligent enough to explore the area, find the victims and construct a map. Using multiple robots made the system more accurate and robust.

The team members and their contributions are as follows:

Control and monitor interface : Yücel Uzun

Routing Algorithm : Muhammet Balcılar, Khudaydad Mahmoodi

Autonomous control : Yücel Uzun, M. Fatih Amasyalı Victim detection : Yücel Uzun, A. Cüneyt Yavuz

Image Enhancement : Bilge Yaraş

Supervising, system design : Sırma Yavuz, M. Fatih Amasyalı

2 System Overview

The main software modules are user interface, localization, mapping, navigation, communication and victim detection. Robots on their own have all those modules equipped and ready-to-use, there is also a multi-robot coordination module covering them all. As the ground robots we use the Pioneer 3AT and Kenaf models. The sensors to be used are determined as Hokuyo URG04L model laser scanner, camera, ultrasonic, encoder, touch and odometry sensors. We also use Air Robots with only two camera sensors.

3 User Interface

The user interface is developed to control 16 robots at the same time and consists of two forms as shown in Fig. 1 and Fig.2.

At the Form 1 of the user interface (Fig. 1), the thumbnail of all robots' camera views, the camera view and the orientation of the selected robot can be seen.

At the Form 2 of the user interface (Fig. 2), the map of the disaster area, the coordinates and directions of the robots, the scanned areas and obstacles can be seen. The robot to be controlled is selected from the map. The robots can be controlled by the user keyboard or the direction arrows on the Form 1. The speed of the robots can be adjusted by the controller next to the direction arrows.

To generate a map of the environment and to determine the positions of the victims SLAM algorithms are used [3, 4, 5]. For the mapping EKF based FastSLAM [6] algorithm is preferred. A grid-based map is used to represent the environment. The map and pose of the robot are estimated using the range measurements obtained by robot and the control signals that make robot move.

4 Image Enhancement

At disaster areas, the images coming from robot cameras can be very problematic because of the dust, the darkness and the smoke. The same problems exist in the simulation platform. The images coming from robot cameras were investigated on the 2011 competition maps. We noticed that the number of unique colors is very low. In other words, the color histograms are very narrow. This situation reduces image understanding capabilities of the user. To solve this problem, we applied block based histogram equalization on HSI color space. To determine block size, many tests are performed. The larger block size will cause better contrast but high computational cost. The detail of algorithm is proposed in [7]. In Fig. 3, the results of the contrast enhancement algorithm are given. The original image is at the left side. The processed image is at the right side.

In Fig. 3, it can be seen that the processed images are more understandable than the original ones.

5 Autonomous Control and Navigation

Controlling multiple robots is not effective by using turn right, turn left etc. level commands. Another and more useful approach is waypoint control which saying robots only the places where to go [8]. At the last year, we have implemented the waypoint control approach with the theory of Proportional Control [9]. The disadvantage of our implementation was the need of clear way between the current and target coordinates. The more robust and intelligent approach is fully autonomous control. In other words, the robots can determine the waypoints to go. This year, we added a fully autonomous mode control to our robots in addition to the waypoint control mode. In autonomous mode, the robots choose a grid having maximum potential [10].

Our grid selection method is posed as a multi-objective optimization problem with two objectives: minimization of the distance to the goal, and maximization of the number of unsearched neighbor grids. To avoid obstacles, the difficulty of neighbor grids of the obstacles is increased. So, a robot moving on an empty hall is moving on the center of the hall.

6 Victim Detection

While some victims on the area do not have any motion, most of them do have small movements. Detecting motion is actually an easy issue on static camera. But when the camera is non-static, it becomes challenging problem. To solve this problem, the motion of the camera needs to be removed, and then remaining motion can be detected as associated with a moving object.

$I^t$ , $I^{t-1}$ are images of P3AT's camera at time t and t-I respectively. $f^{t-1}$ is n unit feature point's x and y coordinates at image $I^{t-1}$ , extracted by Lucas-Kanade method [11]. $f^t$ is the feature vector at image $I^t$ , extracted by tracking $f^{t-1}$ features. The coefficients of the best transform matrix that transforms $f^{t-1}$ to $f^t$ , are determined using least square error. The form of transform matrix is given in Equation 4 [12].

$$\begin{bmatrix} \hat{f}{x}^{t} \ \hat{f}{y}^{t} \end{bmatrix} = \begin{bmatrix} a_{0}.f_{x}^{t-1} + a_{1}.f_{y}^{t-1} + a_{2}.f_{x}^{t-1}.f_{y}^{t-1} + a_{3} \ a_{4}.f_{x}^{t-1} + a_{5}.f_{y}^{t-1} + a_{6}.f_{x}^{t-1}.f_{y}^{t-1} + a_{7} \end{bmatrix}$$

$\hat{f}^t$ is the estimation of $f^t$ which has minimum estimation error. To estimate $\hat{f}^t$ , all coefficients (eight units in total) must be determined by least square error [13]. Error function (J) of being minimized by least square is given at Equation 5.

$$J = \frac{1}{2} \cdot \sum_{i=1}^{n} \left| f^{t} - \hat{f}^{t} \right|^{2} \tag{5}$$

Once the best transform coefficients are found, the feature point's prediction error is checked against a certain threshold. However, there may be features associated with moving objects which lead to the inference of an inaccurate transformation. So these features should be eliminated to have a better transformation model. If the difference between previous frame's and current frame's point is larger than a threshold value, this feature is eliminated. After the elimination, transformation model is recomputed:

• 1. Compute the initial estimate $\hat{f}$ using the full feature set.
• 2. Partition the feature set into two subsets F_in and F_out as:

$$\begin{cases} f_{i} \in F_{in}, & \text{if} \quad \left| f_{i}^{t} - \hat{f}{i}^{t} \right| < \varepsilon \ f{i} \in F_{out}, & \text{otherwise} \end{cases}$$

• 3. Re-compute the final estimate $\hat{f}$ using only subset $F_{\rm in}$ .

If the prediction error is above this threshold than a moving object feature is detected, otherwise a static environment feature is detected. The threshold value is determined empirically. All feature points and moving feature points are shown at Fig. 4.

To detect non-moving victims, we use a method based on Histogram of Oriented Gradients. The detector has the following attributes: grayscale with no gamma correction; Sobel filter with no smoothing; linear gradient voting into 9 orientation bins in 0°-180°; 20x20 pixel blocks of four 10x10 pixel cells; 120x120 detection window; 5-nearest neighbor algorithm. We constructed a discriminative model based on a training dataset obtained from USARSim environment [14].

7 Routing Protocol

To fully explore and map the area and to find victims, all robots have to be in communication with ComStation at any moment. If ComStation do not access any of the robots, these robots do not receive operator's command. As a result, the robot is forced to act completely autonomous. Thanks to the wireless communication protocol server [15], ComStation generally keeps communicating with other robots.

Robots communicate with each other through the WSS in USARSIM, hence each robot called as mobile wireless sensor, and the network which consists of robots and the ComStation is called as wireless sensor network [16].

Routing algorithm is the most important step in communication protocol and the path way of message packet from source to target determined by routing algorithm [17]. When WSS works on noop-propagation mode, all the robots are always in communication with each other and ComStation that established a direct link with the source message to be transmitted to the target robot. But in other propagation modes, the message should go to the destination by the way of hops.

Blind Flooding routing algorithm is one of our routing methods. According to this method, all messages forwarded to all robots by source node. When any node receives a message, first controls the original receiver of this message. If this message is node's own message then node receives the message and processes it. If the receiver of the message is another node, the message is broadcasted to all nodes [17].

Table-driven routing algorithm is the other routing methods that we implement. During the installation phase, all robots send signal strengths to the ComStation by the way of blind flooding at once. ComStation prepares the effective route by using signal strength for each robot and sends this information to the robots continuously. All the robots that uses this route to send information (sensor and camera image) to the Com-Station.

8 Conclusion

In this paper, we give an overview of what our team developed for this year. We concentrated to the developing of our message routing algorithm, image enhancement, autonomous navigation and victim detection techniques. The experience we gain from virtual robot competition will allow us to improve our algorithms.

References

1. Thrun, S., Burgard, W. and Fox D.: Probabilistic Robotics, The MIT Press, Cambridge, Massachusetts, 2005
2. Wang, J., Balakirsky S., USARSim-manual_3.1.3
3. Özışık O., Yavuz S.: An Occupancy Grid Based SLAM Method", IEEE Computational Intelligence for Measurement Systems and Applications (CIMSA 2008), İstanbul, 2008
4. Kurt Z., "Development of Intelligent SLAM Algorithms, Master Thesis, Yıldız Teknik Üniv., 2007
5. Özışık O.: Simultaneous Localization and Mapping with Robot Team, Master Thesis, Yıldız Teknik Üniv., 2010
6. M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit. FastSLAM: a factored solution to the simultaneous localization and mapping problem. In Proceedings of the AAAI National Conference on Artificial Intelligence, p. 593-598, 2002
7. M. Alwani and A. K. Tiwari, "A Constrast Enhancement Based Algorithm To Improve Visibility Of Colored Foggy Images," in Proceedings of the 4th WSEAS International Converence on Business Administration (ICBA'10), 2010
8. P. Velagapudi, P. Scerri, K. Sycara, H. Wang, M. Lewis, and J. Wang, "Scaling effects in multi-robot control," 2008 IEEERSJ International Conference on Intelligent Robots and Systems, pp. 2121-2126, 2008.
9. B. C. Kuo, Automatic Control Systems. Wiley, 1995, p. 898.
10. J. A. H. Ortiz, K. R. Vázquez, M. A. P Castañeda, F. A.Cosío, "Autonomous robot navigation based on the evolutionary multi-objective optimization of potential fields", Engineering Optimization, Volume 45, Issue 1, 2013
11. B. D. Lucas and T. Kanade, "An iterative image registration technique with an application to stereo vision," International Joint Conference on Artificial Intelligence, vol. 130, no. x, pp. 674-679, 1981.
12. B. Jung and G. S. Sukhatme, "Detecting Moving Objects using a Single Camera on a Mobile Robot in an Outdoor Environment," Proceedings of IAS, pp. 980-987, 2004.
13. H. W. Bode and C. E. Shannon, "A Simplified Derivation of Linear Least Square Smoothing and Prediction Theory," Proceedings of the IRE, vol. 38, no. 4, pp. 417- 425, 1950.
14. Navneet Dalal and Bill Triggs, "Histograms of Oriented Gradients for Human Detection", Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1 - Pages 886-893, 2005.
15. M. Pfingsthorn, "RoboCup Rescue Virtual Robots: Wireless Simulation Server Documentation," October, pp. 1-8, 2008.
16. S. A. Munir, B. Ren, W. Jiao, B. Wang, D. Xie, and J. Ma, "Mobile Wireless Sensor Network: Architecture and Enabling Technologies for Ubiquitous Computing," Network, vol. 2, pp. 113-120, 2007.
17. A. S. Tanenbaum, Computer Networks (4th Edition), no. 2. Prentice Hall, 2002, p. 912.