Research Abstracts - 2007

Introduction

Autonomous robots have many useful applications, including search and rescue missions, surveillance operations, etc. However, autonomous localization, navigation and mapping problems continue to be one of the biggest challenges in the field of robotics, and while significant advances have been made with ground robots, few have attempted to deal with robotics in a 3-D space. Our aim is therefore to develop an autonomous helicopter (with control centralized on the helicopte itself) that is capable of solving localization and navigation problems in a multi-dimensional environment using only an onboard 2D-laser rangefinder as a guide, without relying on GPS.

Figure 1 TRex 450SE Helicopter

Design

Hardware

The helicopter platform (see Figure 1), and other associated hardware, is implemented by Ruijie He and Mikel Graham. Modified from the TRex 450SE Helicopter kit, our model has a payload of 600g using a standard RC motor. The Helicommand autostabilization device ensures a level flight without destabilizing rotations in the yaw, pitch or roll axes, allowing an onboard Hokuyo laser to provide 270-degrees scans over a 4 meter range at 10Hz. For safety purposes, the helicopter is also equipped with an onboard RF switch which allows for instantaneous shutoff of the main motor.

Onboard processing is achieved using an Imote2 Multi-Sensor Board from Intel Research Labs. Equipped with Carmen, an open-source robotics software toolkit, and bluetooth capabilities, this 500MHz computer exerts direct control over the helicopter servos and collects onboard laser data, while simultaneously communicating remotely with the base computer to allow for human piloting and laser display (see Figure 2). Eventually, the Imote2 will allow the helicopter to be completely independent of the base station, allowing laser data collection, online control and autonomous piloting to be processed on-board.

Figure 2. Laser data display on a laptop, while the helicopter is on the ground	Figure 3. Helicopter level in mid-air during a test flight in the CSAIL Holodeck.

Currently, the helicopter is able to fly remotely without human control, and while translational drift persists, the helicopter stays level in flight (See Figure 3). Laser data is collected through the Hokuyo laser and fed back to the base station via the onboard Imote2. Subsequent steps therefore include processing the laser data so as to close the control loop around the laser scans and the Imote2 computer, and once the helicopter is able to maintain a fixed hovering position for a sustained length of time, it will provide an effective, stable platform for implementation of robotics path-planning algorithms.

Software Algorithms

Localization and Mapping Algorithms

The fundamental problem of autonomous navigation is the inherent uncertainty in the robot's position, which increases as it moves through the environment. The most recent advances in research focuses on a special class of algorithms, called simultaneous localization and mapping (SLAM) algorithms [3], [4]. They allow the robot to simultaneously build a full map of its surroundings, and use that map to reliably localize itself in them. For the purposes of our helicopter, we are not interested in building a full 3D map of the environment. We are just interested in improving local environment representation by using an algorithm that can be applied in real-time. One such incremental mapping algorithm is the iterated closest point (ICP) proposed by Besl and McKay [1] and Chen and Medioni [2]. It works by taking the simple onboard laser scan, which is a set of range measurements to the obstacles around the robot, and matches the next scan to the previous one. Since only two scans are involved in each iteration, it is much less memory intensive than the algorithm that keep the entire laser scan history, and therefore it can be implemented in real time as the robot moves around. Initially, the algorithm is implemented using a simulation feature of the Carmen software, but in the future it will be tested with the laser data received from the helicopter.

Navigation Algorithms

Because we are not trying to build a full representation of the surrounding world, we need a way for the robot to achieve path planning using minimal information - no map, no GPS, only a simple laser range scanner. One such fairly new algorithm is the Gap Navigation Algorithm proposed by Benjamin Tovar and Steven LaValle [5], [6]. The "gap" in the gap navigation algorithm stands for a discontinuity in the robotic field of vision. The idea behind an algorithm is that the robot is able to represent each discontinuity as a tree node in a particular order. By moving towards a gap eventually the robot will see the objects/landmarks hidden behind it. These landmarks can be stored as the children of the gap nodes, with a gap marking the object location. The paper demonstrates that the shortest path from one landmark to another can be achieved by following the nodes in the gap navigation tree.

Another direction of our research is to determine the best representation of the 3-D free space within which the helicopter can operate. The map and state-space representations are particularly important in solving path-planning and navigation problems, and existing representations include using 3-D grid cell decomposition methods. We are currently exploring the use of a 2.5-D map representation, where vectors at each (x,y) coordinate denotes the free space within which the helicopter can operate, since this significantly reduces the space requirements for this map representation, especially when most of the environment is free-space. This approach is currently being implemented by re-creating the Stata center in a 2.5-D format.

References:

[1] Paul J. Besl and Neil D. McKay. A Method for Registration of 3D Shapes. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 14 No 2, p. 239, February 1992

[2] Yang Chen and Girard Medioni. Object Modeling by Registration of Multiple Range Images. In Proceedings of the 1991 IEEE International Conference on Robotics and Automations, pp 2724-2729 April 1991.

[3] John J. Leonard and Hugh F. Durrant-Whyte. Simultaneous Map Building and Localization of an Autonomous Mobile Robot. In IEEE/RSJ International Workshop on Intelligent Robots and Systems, pp. 1442-1467, IROS '91, November 1991.

[4] Sebastian Thrun, Dieter Fox and Wolfram Burgard. A probabilistic approach to concurrent mapping and localization for mobile robots. In Machine Learning, Vol. 31, 1998

[5] Benjamin Tovar, L. Guilamo, and Steven M. LaValle. Gap Navigation Trees: A minimal representation for visibility based tasks. In Proceedings Workshop on Algorithmic Foundation of Robotics, p. 1126, 2004.

[6] Benjamin Tovar, Rafael Murrieta-Cid and Steven M. LaValle. Distance Optimal Navigation in an Unknown Environment without Sensing Distances. In IEEE Transactions on Robotics, 2007

[7] Sebastian Thrun, Wolfram Burgard, and Dieter Fox. A Real Time Algorithm for Mobile Robot Mapping with Applications to Multi Robot and 3D Mapping. In Proceedings of the IEEE International Conference on Robotics and Automations, San Francisco, CA, April 2000.

[8] Dirk Hahnel, Wolfram Burgard, and Sebastian Thrun. Learning compact 3D models of indoor and outdoor environments with a mobile robot. In Robotics and Autonomous Systems, p. 1527, Vol 44, 2003.