Leonidas J. Guibas Jean-Claude Latombe
Computer Science Department
Stanford University
January 6, 1999
In this report, we describe the realistic models and data structures we have defined for
describing the perception and mobility capabilities of the robots in a parametric form that is usable by our future software modules,
expressing the motion plans to be computed by these modules, and
defining a parametric model of a target's behavior.
The software we plan to develop for the tasks of model building, target finding, and target tracking will be divided into three closely-interacting modules, one for each task. We assume that our modules will interface with the environment by receiving information from and transmitting data to external modules developed by other TMR contractors, e.g. a sensing module that takes the raw data captured by the sensors mounted on the robots and converts it into a high-level form that is usable by our software (e.g., transforming data points acquired by a range sensor into surface patches that are input to our model-building module); a vision module that processes sensor data to identify landmarks and targets; a controller module that converts our high-level path planning commands into low-level commands that control the motors and actuators on the robot.
One of the most important goals of the robots is to build a model (or map) of the indoor environment in which they have been previously introduced by the TMR operators. This map (and subsequent updates to it) must be transmitted to the users. The map is also critical for the efficient navigation of the robots and for accomplishing other tasks, such as finding and tracking human targets.
The map should contain topological information describing how the various portions of the environment are connected to each other, geometric information characterizing the shape of each individual subspace, and other information related to mobility and visibility.
We propose that the map be articulated around a set of 2-D layouts. A 3-D model will be attached with portions of each 2-D layout. Articulating the map around 2-D layouts will facilitate man-machine interaction, since TMR operators can read and interpret 2-D maps faster than 3-D models. 2-D maps are also easier to use for robot navigation and yield faster visibility computation than 3-D models. 3-D models are nevertheless useful since they provide more complete information about the environment.
Each 2-D layout will typically correspond to one floor of the building being scouted. It will contain a geometric description of the major ``obstacles,'' e.g., walls and major pieces of furniture or machines, projected in the horizontal plane. Except when they are destroyed, these obstacles impede mobility and occlude visibility for any human or robot. In addition to these major obstacles, regions in a 2-D layout will be labelled as non-traversable by robots and/or humans, say, because of rubble, mines, or concertina wires. However, these regions may not occlude visibility. Other regions (perhaps partially overlapping the previous ones) will be labelled as visually occluding, though traversable by robots and humans. The distinction between obstacles obstructing motions and obstacles occluding visibility seems critical, but is rather new in environment modeling.
A 2-D layout will classically be represented by polygonal contours. This representation is easy to visualize and easy to use by other programs (e.g., to compute which area is visible from a given point). Other geometric representations may be used in combination with the polygonal representation; for instance, empty space can be approximated by collections of overlapping circles. Such a representation could have significant advantages over the polygonal one, such as being easier/quicker to obtain from sensory data and/or to update.
Each 3-D model will consist of a 3-D mesh representing the external surfaces of the objects in the corresponding subsets of the environment. Clearly, a 3-D model gives more information that a 2-D one, but its construction requires more sophisticated sensors and more computational power. Visualizing 3-D information so that it can be used efficiently by the TMR operator is also more difficult.
We can represent uncertainty in the map by associating with each point in the 2-D layout the probability that the point is occupied by an obstacle. Of course, the real obstacles in the environment should match subsets of points in the 2-D layout which have a high probability of being occupied by an obstacle. In this scenario, the notion of visibility has an interesting extension: along a given ray of sight originating at a point p, visibility is a function decreasing from 1 at p to 0 at infinity; the value of the visibility at a point q along this ray is the probability that q is visible from p, which is equal to the probability that the segment pq intersects an obstacle. We can use a probabilistic occupancy grid to represent such probability distributions. An alternative way of representing uncertainty would be to use a tolerance language similar to those used in design/manufacturing for representing mechanical parts, for example, by saying that the position of each vertex in the 2-D map is uniformly distributed over a small circle.
Depending on which sensors are available, other types of information can be added to the model. For example, if color cameras are available on the robots, digitized video images from selected viewpoints in the 2-D layouts can be included; viewpoints may be selected interactively by users or automatically by software using heuristics (e.g., geometric irregularities). Texture maps can also be added to the 3-D model mesh.
The map data can be processed further to make additional information explicit, for example, by computing places which are good hiding places (i.e., places that are seen from relatively few other points) or, on the contrary, by computing positions that allow the robot to visually control many other places.
For the most part, the tasks of our robots are to gather and organize information that is useful to the TMR operators. Information is acquired by sensing operations. Various sensors may be used by the robots. Since our research does not address the problems of designing/selecting appropriate sensors for the robots and of interpreting raw sensory data (e.g., detecting a human based on heat sensing), we would like our software technology to be general enough to work with different sensors. Clearly, the motion decisions to be made by our software will depend on the available sensors. For instance, the motion plans computed by our software if the robots are equipped with omni-directional cameras should be different from those computed if the robots are only equipped with cameras with narrow fields of view.
To develop technology components (software modules) that are as independent as possible from the characteristics of the sensing systems, we define an abstract parameterized model of the sensing systems for each of the three considered subtasks (map building, target finding, target tracking). Our software modules will take the specific values of the parameters of the sensing systems used as inputs, and they will compute motion commands for the robots accordingly.
For each of the three tasks, we propose a separate model of the sensing systems, since different sensors are useful for different tasks (e.g., a range sensor is very powerful for map building, while a CCD camera is ideal for target tracking). However, the three sensing models are quite similar. In each case, we assume that each sensing system mounted on a robot delivers pertinent information (e.g., location of a target) within a geometric region that we call the "visibility region" (VR) of the sensor. The union of the VRs provided by the various sensors on the same robot defines the VR of the robot. The union of the VRs of the robots defines the VR of the robot team.
The goal of this task is to build a geometric/topological model of the environment. This model is articulated around one of several 2-D layouts. A 3-D model of portions of the environment is attached to these layouts. We have defined the map model in greater detail in Section 2.
We expect some robots to be equipped with a range finder of some sort. The VR of this sensor will be a rectangular cone truncated by two spheres centered at the cone's apex. The radius of the smaller sphere is the minimal range below which the sensor is ineffective. The radius on the bigger sphere is the sensor's maximal range. The sensing system returns a collection of surface patches (planar and non-planar ones) that represent bounding surfaces of the objects in the environment that are in the VR and are visible from the cone's apex according to the elementary line-of-sight visibility model. (A point p sees another point q according to the line-of-sight model if the line segment pq intersects no occluding object.) We expect the sensor to return surface patches covering most of object surfaces visible to the sensor; exceptions will include highly specular surfaces and portions almost tangent to the line of sight.
Several representations are possible for the surface patches. Describing each of them by a mesh and its localization in a coordinate frame attached to the sensor/robot seems the most appropriate. The adjacency of the surface patches may also be given by the sensor, but this does not seem critical.
The parameters of this sensing model are:
The two angles (horizontal and vertical) of the rectangular cone.
The minimal and maximal range of the sensor.
Optional: other information, such as the minimal incidence of a line of sight on an object's surface.
Typical values for the cone angles would be between 30 and 45 degrees, with the minimal and maximal ranges being about 2 and 15 ft. However, we can well imagine a sensor providing a cone with a zero vertical angle. Such a ``degenerate'' sensor provides an outline of the environment and can be used to build a 2-D map. Clearly, an inferior sensor will result in a map with less information and/or will require the robots to execute a more time-consuming motion strategy.
The objective of the target-finding software module is to compute the paths for some number of robots to coordinate their movements around the obstacles in an environment to eventually find any dynamic targets in this environment. The planner is given the restrictions on the sensing capabilities and plans the paths taking the sensing constraints into account. The robots are equipped with sensors to perform two tasks: detecting targets and localizing the robots.
A simple sensor for detecting targets is a CCD camera attached to the robot. The parameters for this sensing model are:
The minimal and maximal range of the sensor.
A possible sensor for computing the positions of the robots in the environment is a range sensor. The parameters of such a sensor are similar to the ones discussed in Section 3.1. We expect that the information gathered by these sensors will be processed by an external module to compute the precise locations of the robots; this information is then input to our target-finding software.
The target tracking planner computes the optimized position of the robot to keep the target in the range of its sensors. The planner calculates the movements according to sensing constraints so the target has less chance of escaping the sensor range. The robots are equipped with sensors to perform two tasks: keeping targets within sensor range and localizing the robots. A simple sensor for tracking a target is a CCD camera attached to the robot. The parameters for this sensing model are:
The minimal and maximal range of the sensor.
A mobility model characterizes the ability of a robot to move in various types of environments. It can be quite complex, especially if legged robots are used. For the purpose of our research, we will use a relatively simple mobility model. We will assume that the environment consists of areas that are traversable (by the robots and any target) and areas that are not traversable (obstacles obstructing motion); we expect this information to be collected during the map-building phase. The robots can only be in the traversable regions. The traversable region will be represented in a manner that takes into account the size of the robot, e.g., if the base of the robot is a disk, we can shrink the traversable regions by the radius of the disk. We will assume that the maximal velocity of a robot is constant over traversable regions. We will not consider acceleration in our software components, that is, we will assume that a robot can achieve maximal velocity almost instantaneously.
We include robot localization as part of the mobility model. Errors in robot localization may have dramatic effects on operations like map building, target finding, and target tracking. Robot localization can be made more accurate by using landmark localization and/or sensor data matching techniques. However, it cannot be perfect. In our research, we will not use sophisticated probabilistic techniques to model robot localization errors; instead, we will assume that the range of possible positions of a robot at any one time is a uniform distribution over a disk of constant radius centered at the robot's estimated position. Similarly, uncertainty on the robot's orientation (if relevant) is an angular interval centered at the estimated orientation.
A standard for plan representation is useful for a couple of reasons. First of all, a single representation allows modular software development. Secondly, the standardized plan can be displayed to the TMR operator for path modification or cancellation. In hazardous environments, it is imperative that the TMR operator be able to override the path computed by the motion planner due to any additional variables not foreseen in the software design stage.
The basic plan representation for each robot is a series of commands ordering the robot to proceed in a certain direction at a specified velocity for a given amount of time. The planner ensures that the robot can execute this command without colliding with obstacles in the environment. Additional information and directives are associated with each such command, depending on the task being performed.
Target finding: The plan computed by the target finding module ensures that the robots move such that they eventually find any moving targets. This plan is computed and specified offline. If the robots move such that they maintain a communication network, two robots may be directed to move in a coordinated fashion so that the communication link between them does not break.
Target tracking: The plan for target tracking consists of real-time updates of the robot's position and direction. This allows the visual system to maintain visibility of the moving target. Since our target-tracking software also specifies which target a robot should track, the plan output by the target-tracking module will also command a robot to start tracking a different target, as and when necessary.
In target finding and tracking, the behavior of the target is assumed to have a maximum velocity bound. As in the robot mobility model, we will not consider acceleration. Instead, we will assume that the target can achieve maximal velocity almost instantaneously. The target is also assumed to be able to change direction instantaneously in any direction, but it must move in a continuous path.
Collaborative Mobile Robots for
High-Risk Urban Missions
Report on Environment, Perception, and Mobility Models and
Plan Representation
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 -show_section_numbers models.
The translation was initiated by T.M. Murali on Wed Jan 6 15:35:49 PST 1999