NIST logo
*
Bookmark and Share

PRIDE (Prediction In Dynamic Environments)

Summary:

PRIDE (Prediction In Dynamic Environments) is a hierarchical multi-resolution framework for moving object prediction that incorporates multiple prediction algorithms into a single, unifying framework. PRIDE is based upon the 4D/RCS reference model architecture and provides information to planners at the level of granularity that is appropriate for their planning horizon. This framework supports the prediction of the future location of moving objects at various levels of resolution, thus providing prediction information at the frequency and level of abstraction necessary for planners at different levels within the hierarchy. To date, two prediction algorithms have been applied to this framework, the long-term and the short-term prediction algorithms.

Description:

The PRIDE framework

PRIDE is a hierarchical multi-resolution framework for moving object prediction that incorporates multiple prediction algorithms into a single, unifying framework. PRIDE is based upon the 4D/RCS reference model architecture and provides information to planners at the level of granularity that is appropriate for their planning horizon. This framework supports the prediction of the future location of moving objects at various levels of resolution, thus providing prediction information at the frequency and level of abstraction necessary for planners at different levels within the hierarchy. To date, two prediction algorithms have been applied to this framework, the long-term and the short-term prediction algorithms.

The Prediction Algorithms

At the higher levels of the framework, moving object prediction needs to occur at a much lower frequency and a greater level of inaccuracy is tolerable. At these levels, moving objects are identified as far as the sensors can detect, and a determination is made as to which objects should be classified as “objects of interest”. In this context, an object of interest is an object that has a possibility of affecting our path in the time horizon in which we are planning.

At these levels, PRIDE utilizes a moving object prediction approach based on situation recognition and probabilistic prediction algorithms to predict where that object is expected to be at various time steps into the future. Situation recognition is performed using spatio temporal reasoning and pattern matching with an a priori database of situations that a driver expects to see in the environment.

To date two different approaches to compute long-term predictions are used within PRIDE. The first is a cost-based approach that uses a discretized set of vehicle motions and costs associated with states and actions to compute probabilities of vehicle motion. The second is a fuzzy-logic-based approach that deals with the pervasive presence of uncertainty in the environment to negotiate complex traffic situations.

In these algorithms, we are typically looking at planning horizons on the order of tens of seconds into the future with plan steps at about one second intervals. At this level, we are not looking to predict the exact location of the moving object. Instead, we are attempting to characterize the types of actions we expect the moving object to take and the approximate location the moving object would be in if it took that action. Figure 1 sketches the process flow of the LT prediction algorithm.

Figure 1. Process flow of the LT prediction algorithm
Figure 1. Process flow of the LT prediction algorithm.

At the lower levels, PRIDE utilizes estimation theoretic short-term predictions via an extended Kalman filter-based algorithm to predict the future location of moving objects with an associated confidence measure. The Extended Kalman Filter (EKF) is a well-established recursive state estimation technique where estimates of the states of a nonlinear system are obtained by linearization of the nonlinear state and observation equations. Within the PRIDE framework, the EKF predicts short-term estimate of objects moving at variable speeds and at given look-ahead time instants (every one tenth of a second). It should be noted here that, in contrast to the long-term predictions, the estimation-theoretic short-term prediction algorithm does not incorporate a priori knowledge such as road networks and traffic signage and assumes uninfluenced constant trajectory.

The Road Network Database

To compute the future position of an autonomous vehicle, PRIDE must have knowledge of the environment where the vehicles evolve. For an autonomous vehicle to be able to navigate a road network, it must be aware of and must respond appropriately to any object it encounters. This includes for example, other vehicles, pedestrians, debris, construction, accidents, emergency vehicles, and it also includes the roadway itself. The road network must be described in such a way that an autonomous vehicle knows, with great precision and accuracy, where the road lies, rules dictating the traversal of intersections, lane markings, road barriers, road surface characteristics, and other relevant information. 

All this information is essential for an autonomous vehicle to be able to navigate a road network and can be found in the road network database (RND), developed at the National Institute of Standards and Technology (NIST) as part of the Defense Advanced Research Project Agency (DARPA) Mobile Autonomous Robotics Systems (MARS) Program. 

In PRIDE, an autonomous vehicle is able to get all information from the RND, based on its position in the road network. The PRIDE algorithms consider different information from the road network structure. For instance, the length and the width of a lane are used to compute the future location of the autonomous vehicle within this lane, the curvature center is used so that the vehicle takes the right angle to turn, the autonomous vehicle has to know the speed limit on a particular lane to avoid speed excess, etc. Some components of the RND used by PRIDE are depicted in Figures 2 and 3 and described below.

Figure 2. Lane segments (shaded parts). Figure 3. A lane (shaded part). along curve
Figure 2. Lane segments (shaded parts). Figure 3. A lane (shaded part).


Aggressivity

Different drivers drive in different ways. One driver may be very conservative, only changing lanes when absolutely necessary, never exceeding the speed limit, etc. On the other hand, another driver may drive very aggressively, weaving in and out of lanes, greatly exceeding the speed limit, and tailgating other drivers. In most cases, one would experience both kinds of drivers on any trip (along with many drivers that fall somewhere in the middle), and a moving object prediction framework needs a mechanism to account for all such circumstances. When a driver is first encountered, it is extremely rare that one can instantaneously determine the perceived aggressivity of the driver. This information is often determined after observing the driver for a certain amount of time, characterizing their driving behaviors, and assigning aggressivity. The aggressivity that is assigned greatly impacts PRIDE’s predictions as to where that driver will be at times in the future. For example, we would likely assume that a conservative driver would remain in their lanes whenever possible and stay a safe distance behind the vehicle in front of it. An aggressive driver would have a higher probability of changing lanes.  We may also find that the aggressivity of the driver may change over times. There are times when one can observe a driver for many seconds at a time. In this case, the driver’s aggressivity may change, perhaps they are very aggressively trying to get to a certain lane but become more passive when they get there. The PRIDE framework addresses all of these driver types and all of the situations mentioned above.

Click here to see Video 1. Example of aggressivity.

Situation awareness

In recent years there has been a growing appreciation of the importance of situation awareness (SAw) in a variety of complex task domains, such as aviation, nuclear power plant management, medical decision-making and tactical driving. Since its original conception, numerous definitions of SAw have been proposed. PRIDE uses the formal definition from Endsley where SAw is described as: [An expert’s] perception of the elements in the environment within a volume of time and space, the comprehension of their meaning and the projection of their status in the near future.

To make assumptions of the future positions of moving objects, PRIDE has access to a level of SAw of how other vehicles in the environment are expected to behave considering their own situation. An autonomous vehicle should be able to plan a path while avoiding any collision with obstacles or other moving objects on the road. The autonomous vehicle also requires knowledge of the environment and knowledge on the status of other objects in the environment to be able to drive tactically. Modeling the behaviors of other vehicles is the most important aspect of tactical driving. It is straightforward to model the speed and the relative positions of the vehicles; however, it is a complicated task to model the future behavior of the drivers.

The model of SAw simulated by PRIDE is based on the model provided by Endsley, as sketched in Figure 4.

Endley’s model for situation awareness
Figure 4. Endley’s model for situation awareness
 

  • Perception: this level of awareness is achieved if autonomous vehicles are able to perceive different elements in the environment (e.g., vehicles, roads) as well as their characteristics (e.g., size, color, and location).
  • Comprehension: at this level, autonomous vehicles combine the perceived information with other data to interpret the situation correctly.
  • Projection: at this level, autonomous vehicles are required to anticipate the actions of the elements in the environment and to predict the future states of the environment.
Click here to see Video 2. Traffic negotiation at an intersection.

PRIDE with the MOAST/USARSim Framework

In recent efforts, the PRIDE framework started to the Mobility Open Architecture Simulation and Tools MOAST framework with the Unified System for Automation and Robot Simulation (USARSim) tool to provide more realistic predictions.
To test the performance of intelligent vehicles, the simulation environment has to use specifications as accurate as possible to the components of the real world. The MOAST/USARSim framework incorporates the physics, kinematics and dynamics of vehicles involved in traffic scenarios.

Mobility Open Architecture Simulation and Tools (MOAST)

MOAST provides a baseline infrastructure for the development, the testing, and the analysis of autonomous systems that is guided by three principles: 1) creation of a multi-agent simulation environment and tool set that enables developers to focus their efforts on their area of expertise, 2) creation of a baseline control system which can be used for the performance evaluation of the new algorithms and subsystems, and 3) creation of a mechanism that provides a smooth gradient to migrate a system from a purely virtual world to an entirely real implementation.

Unified System for Automation and Robot Simulation (USARSim) 


Large-scale coordination tasks in hazardous, uncertain, and time stressed environments are becoming increasingly important for fire, rescue, and military operations. Substituting robots for people in the most dangerous activities could greatly reduce the risk to human life. Because such emergencies are relatively rare, there is little opportunity to insert and experiment with robots. USARSim was designed as a high-fidelity simulation of Urban Search And Rescue (USAR) robots and environments intended as a research tool for the study of Human-Robot Interaction (HRI) and multi robots coordination. USARSim is an open source simulation environment which provides realistic environments. The environments are full 3D worlds that have photo-realistic textures and objects (Figure 5).

3D worlds in USARSim. 3D worlds in USARSim 3D worlds in USARSim
Figure 5. 3D worlds in USARSim

 

 

 

 

 

 

 

 

Integration of PRIDE with MOAST/USARSim

The communication between the PRIDE framework and the controller (MOAST) is possible through NML channels at the PRIM level as depicted in Figure 6. The data transfers between these two modules can be summarized as follows: 1) PRIDE queries the NML channels on the status of the autonomous vehicles in the environment (e.g., the number of vehicles) and the characteristics for each vehicle (e.g., orientation, speed). 2) Using this information, the LT algorithm queries the RND on the road structure to identify the position of each autonomous vehicle in the road network. 3) Once the road structure for an autonomous vehicle has been determined (e.g., ID of the road, speed limit on the road), the LT algorithm computes the future positions of the vehicles. 4) The information computed is sent to MOAST as waypoints. The embedded client-server architecture of the Unreal game engine enables USARSim to provide individualized control over multiple robotic systems through discrete socket interfaces. The interfaces provide a generalized representation language that enables the user to query and control the robots’ subsystems. All the communications between the clients (Unreal client and the Controller) and the server are performed through the network. The Unreal Server includes the Unreal Engine, Gamebots to bridge the Unreal Engine with outside applications, the maps and the models (robot models, victims, etc). MOAST first connects to the Unreal Server, and then it sends commands to USARSim to spawn a robot. At this step, MOAST listens to the sensor data and sends commands to control the robot.

Figure 6. System architecture of USARSim, MOAST and PRIDE.
Figure 6. System architecture of USARSim, MOAST and PRIDE.


3D world in USARSim

Lead Organizational Unit:

el

Customers/Contributors/Collaborators:

University of Burgundy, Dijon, France

Contact

General Information:
301 975 3456 Telephone
301 990 9688 Facsimile

100 Bureau Drive, M/S 8230
Gaithersburg, MD 20899-8230