[campus icon] Accesskey [ h ] University of Paderborn - Home
EN english
Die Universität der Informationsgesellschaft

Reactive Navigation in Cluttered Environments


The increasing need of employing robots in high-risk areas hit by natural disasters has attracted the attention of researchers worldwide to develop fully autonomous mobile robots. The main objective of these robots is to carry out the assigned tasks in places where human presence is dangerous or impossible such as: industrial applications, search and rescue, military and exploration, among others. Urban search and rescue (USAR) robot competitions intend to increase awareness of the challenges involved in such areas and promote research and development in this domain. The RoboCup Rescue Robot League is a well-known competition in which robots compete to find disaster victims in a simulated earthquake environment.

Usually, a real world disaster environment is partially or completely unknown and changes over time. Therefore, traditional motion planning techniques which depend on a prede ned map cease to function properly in such environments and the robot is doomed to collide with obstacles. To overcome this limitation the mobile robot should have the capability to explore the unknown area, automatically generate maps and localize itself within this map. This is achieved by on-board sensing devices detecting instantaneous changes in the environment. In addition, it has to recognize victims and correctly label the map with the victims' positions. In all cases it is necessary to have a reactive obstacle avoidance algorithm to safely reach given goal locations and to deal with dynamic changes such as moving obstacles.

Ongoing Research on Mobile Robot Navigation in GET Lab

Many existing reactive navigation methods have problems in dealing with dense and cluttered environments, which is usually the case in most robotic applications. Some drawbacks of these approaches are: the local minima problem, oscillatory behavior, considering robot shapes and motion constraints, and the computational complexity. It is still an open research problem to find an efficient algorithm that enables robots to move safely in such environments.

The major goal of this research project is to contribute to the eff orts by developing a new satisfactory reactive navigation approach for mobile robots moving in cluttered and complex environments. One of the popular approaches designed to deal with such problems is the Nearness-Diagram (ND) Navigation which uses a set of criteria based on analyzing the structure of obstacles surrounding the robot to identify the current situation and then apply the corresponding motion law. Over the years, several ND variants have been developed such as the Smooth Nearness-Diagram Navigation (SND) method which proposes a single motion law to be applicable to all possible configurations of surrounding obstacles. In this regard, the robot trajectory is based on all nearby obstacles, not just the closest two, and this leads to smoother paths. However, a problem of deadlock can appear in the SND in narrow corridors with high threats on one side of the robot and low threats on the other. In this project, we have developed the Closest Gap (CG) approach, which overcame the SND drawback by considering the ratio of threats on the two sides of the robot and providing stricter deviation against the nearest obstacles. Furthermore, a novel algorithm for analyzing openings in front of the robot was introduced that highly reduces their number when compared with the ND technique. Consequently, oscillations are alleviated, the computational complexity is reduced and a smoother behavior is achieved. Afterwards, we have developed the Tangential Closest Gap (TCG) Navigation, which integrates two concepts: The Closest Gap (CG) for fetching and analyzing openings surrounding the robot and the Tangential Escape (TE) for reactive obstacle avoidance navigation. This combination results in faster and less oscillatory robot trajectories than the well known approaches designed for complex scenarios (e.g ND, SND, CG). The TCG has been further developed, and named Smooth Tangential Closest Gap (STCG), by considering all nearby obstacles in identifying the best maneuver to avoid collisions instead of just the closest one. As a consequence, a much more stable and smoother behavior is achieved. Moreover, Motion commands are derived with proven stability in the Lyapunov sense for the control system.

Our current and future research aims to consider the robot shape and non-holonomic constraints, achieving global convergence towards the goal. This approach will be implemented to be the reactive layer in our mobile robot GETbot.

Left image: Analyzing gaps by the CG, TCG, and STCG navigation methods; search for discontinuities in depth measurements between two successive obstacle points (gaps 1 to 7), then delete unnecessary ones (gaps 1 and 6). Finally, choose the one closest to the goal (gap 2). Right image: Modifying the direction of motion according to the angular width of the closest gap with respect to the robot vision

Trajectories followed by (left image) Closest Gap CG, (middle image) Tangential Closest Gap TCG, and (right image) Smooth Tangential Closest Gap STCG.
Velocity Profile for (left image) Closest Gap CG, (middle image) Tangential Closest Gap TCG, and (right image) Smooth Tangential Closest Gap STCG.


Do you have any questions or comments? Please contact: