A Hybrid System for Mapping and Exploration of Unknown Environments

Gil Jones
Swarthmore College




Overview - Reactive Module - Deliberative Module - Further In

Overview

Negotiating the real world is notoriously difficult for mobile robots. The real world changes quickly and unpredictably; it's also cluttered, difficult to sense accurately, and follows few discernable rules. All of these factors make programming robots for the real world a daunting task. A robot designed for operation in the real world must be endlessly adaptable, capable of dealing with many different situations, and able to act intelligently with incomplete information. These qualities are especially true of a mobile robot programmed for exploring and mapping an unknown area. Navigating in real world environments such as office buildings has been an open problem in robotics for many years. This is a difficult problem because of the stringent requirements the real world demands of agents operating in it. This paper explores the issues associated with navigating and exploring unknown spaces with autonomous mobile robots.

The system described on these pages divides the task of exploring an unknown environment into two sub-tasks: selecting a place that needs to explored, and actually physically exploring the area. This division forms the basis of the system's hybrid reactive/deliberative two-layer architecture. A low-level reactive system based on a motor schema approach moves to goal points set by the high-level, mapping-based deliberative module. The low-level module is based on a durable, reactive problem-solving method inspired by animal behavioral observations. When encountering an obstruction interfering with the achievement of a goal point, the reactive module will try a number of approaches to navigating around the obstruction. The upper-level, deliberative system maps the space, and assigns a goal point for the reactive module that will result in the exploration of new space. The deliberative system also has the ability to alter some operating parameters of the low-level system, changing "strategy" when accumulated sensor data suggests the robot is trapped.

The following sections give a more in depth introduction to the reactive and deliberative layers. Following those sections are links to pages that delve further into the architecture and design, as well as experiments performed using the system.

Overview - Reactive Module - Deliberative Module - Further In

The Reactive Module: An Introduction

When considering how to program an agent for navigation in an unknown environment, it seems natural to look at the methods of agents that have highly developed and consistently successful solutions to this problem: animals. Almost all animals depend on the ability to navigate in new or partially known areas for survival. Animals must navigate to forage for food, find shelter, and protect their territory. As navigation is so important to the survival of animals, natural selection has developed highly successful systems for real-world navigation. Consider an ant moving towards a known food source. It moves directly towards the source, but encounters an obstacle. The ant may try to climb over the obstacle, and if that doesn't work may attempt to go to the left of it, the right, or under it. The ant will try a variety of different approaches to circumnavigating the obstacle before it gives up on attaining the food source. It seems likely that the ant doesn't have a complex internal map of the area; it just knows where the food source is, and has an arsenal of different techniques for getting past any obstacle in its path.

The approach for low-level control used in this system tries to emulate this ant-approach to navigation. The reactive navigation system operates with no internal state, merely a knowledge of a goal, and the ability to try a number of different approaches to get around an obstacle in its path. The implementation of the system is based on the kind of reactive problem-solving that gives the ant its impressive abilities to successfully navigate in the real world. If the reactive system is not capable of getting to a goal point, it should mean that the goal point is physically inaccessible from a substantial range around the robot. And even if the robot can't reach a goal point, it should explore a large portion of the area on the path to the goal, allowing the high-level system to accumulate more information about the shape of the world.

The implementation of the reactive system is based on a biologically-inspired behavior-based approach called motor schema. The motor schema approach works on the basis of pushes: an obstacle pushes the robot away, a goal point "pulls" the robot towards it. Other schema can exert a force dependent on what the schema is trying to accomplish. The robot's world is composed of the forces at work upon it, which are summed together to create the behavior of the robot at any given moment.

The motor schema used in the system are designed to handle most situations that will face a robot moving towards a goal point. Simple obstacles are negotiated by the combination of the push towards a goal and away from an obstacle, which causes the robot to skirt the side of a compact obstacle. Longer obstacles, like walls, are negotiated using a schema that turns the robot in one direction. Once the robot is turned, it moves forward, pushing constantly against the wall until it encounters an opening. After a certain length of time, the schema will reverse the direction of the turn, insuring that both ways around the obstacle are explored. Tight spaces, such as doors, exert a special push designed to prompt the robot to move through spaces that might be just larger than the robot.

These simple approaches can get the robot around all but the most complex obstacle. There will be times, however, that a reactive module will not be able to get around an obstacle, even though it may be physically possible. Say, for instance, that a robot is in a room that is completely enclosed, except for a door, slightly ajar, that opens outwards. Most sensible navigation packages are designed so that the robot does not hit obstacles, though in this case, hitting the door would actually allow the robot pass through to the outside. Thus the low-level reactive module is composed of many adjustable parameters, which the high-level module can change when it deems that a new "strategy" will be useful in moving into an unexplored area. A strategy might increase the magnitude of a push to a goal, which would allow the robot to bump into walls, or increase the push away from obstacles in an area that seemed especially hazardous.

Overview - Reactive Module - Deliberative Module - Further In

The Deliberative Module: An Introduction

The reactive, low-level module is designed to move to goal points, exploring an area if the path to a goal point is obstructed, and trying numerous approaches to getting around obstacles. But to truly explore a space, a reactive approach is not enough. A higher-level module must decide where the reactive module should move, and perhaps change reactive strategies to insure that a space is maximally explored. Thus our system also contains a deliberative level, which maps a region as it is explored and plans based on the mapping.

Mapping in the deliberative level is done in two layers. At the lowest level, an evidence grid keeps a likelihood of occupancy for every cell of the space. The occupancies are updated according to the most recent sonar data. As planning using evidence grid data is extremely computationally expensive, a geometric representation of the space is constructed using the evidence grid data. Wherever a number of high-probability occupancy cells have accumulated in a row, the geometric representation fits a line to them, a "wall." Thus the geometric representation is constructed of a number of these walls and indications of what spaces have not been confidently labelled occupied or free.

Finally, a landmark-based topological representation is fit into the geometric representation. The landmarks are of a two kinds: one is designed to help the robot stay localized, and the other to demarcate connectivity in the topological representation. The robot is equipped with the ability to drop small colored "landmarks" periodically, the locations of which it records on the map. Whenever the robot sights a landmark, it consults internal odometry to get a best-guess estimate of which landmark has been sighted. Simultaneous sightings of multiple landmarks can localize the robot even more effectively, giving a position and rotation estimate that is generally quite accurate. The internal odometry of the robot is then updated using the localization information. Keeping an accurate estimate of the robot's current location is imperative for the formation of accurate maps.

Connectivity landmarks have no physical presence in the world. For connectivity the robot basically acts like it is dragging a string through the world. As we are sure that the places the robot actually occupies at any given position are free of other obstacles, the robot leaves a trail of zero-probability occupancies behind it. A new node is created in the connectivity graph if a straight line from the last node has to pass through non-zero probability space, meaning that the robot has turned a corner or veered sharply. Thus any zero-occupancy space on the map either contains a node or can reach a node travelling only over zero-occupancy space.

The planner portion of the deliberative module examines the map, and attempts to select a goal point that would result in exploring area that has not been fully mapped yet. If a likely frontier is far away from a current location, the planner uses breadth-first search to find a topological node from which the unexplored area should be accessible. The geometric wall representation is factored in to planning when considering which frontiers should be accesible from different, previously visited sections of the map. If a desired position is far from the current position, the planner can sequentially guide the robot back to the nearest node, and then to each successive node between the current position and the desired position by just setting the next node as a goal point. The design of the reactive module makes it well suited to this planning approach, as it will take a very direct path to an goal point if there are no obstructions, but can also do frontier exploration where the goal point might not be accessible at all. When the goal point is not easily accessible, the reactive module will attempt a number of different approaches to find the obstacle; thus more area can be explored and mapped even if the goal point is not accessible.

The planner is also capable of realizing when the robot is trapped in a particular space, meaning that there appear to be no robot-sized holes in the geometric wall mapping. In this case, the planner can adjust some parameters of the navigational system, allowing the robot to risk bumping obstacles in an attempt to change the environment in a way that will allow more exploration. Thus two levels of adaptability are built into the system. Reactive adaptability gives the robot the capabilities of dealing with most situations where an internal state is not neccessary to cope with a problem. But for situations where no level of intelligence reactivity seems sufficient to solve a navigation problem, the system also allows planning the ability to alter parameters, changing strategies based on map information.

Finally, the deliberative module may include capabilities associated with task-specific planning. For instance, the robot may have 15 minutes to explore an area, at which point it must make its way to the point of entrance. This type of behavior is easy to implement given the nature of the representations maintained in the deliberative module.

Overview - Reactive Module - Deliberative Module - Further In

Further In

Background Conceptual Information
The robot used in this research (under construction)
Reactivity: The Schema Approach
Reactive and Adaptable Behaviors (under construction)
The deliberative model in greater depth (under construction)
Applications and hopes for the future (under construction>
Bibliography


All material on these pages was created by Gil Jones, Swarthmore College, January 2001
Questions or Comments? gil@sccs.swarthmore.edu
Shameless self-promotion