BACKGROUND

Motion planning is the process of determining how a robot should maneuver in the real world. It is the process of finding a collision-free path from a robot's starting position to a goal state. For example, a robot may wish to move its arm to reach a desired object without colliding with itself or any other object. The ability to perform motion planning to navigate and manipulate objects is critical to dealing with natural environments that are not heavily controlled or engineered. The robot first perceives information about the physical world around it, and then the computer determines how to control the physical robot so that the robot can navigate in this perceived environment.

Motion planning at both high speed and low power is an important and challenging task for many technologies, including autonomous vehicles. Challenges for autonomous vehicles include the ability to avoid collisions with both static (e.g., booms or things left in the road) and dynamic (e.g., bicyclists, pedestrians, or other cars) obstacles, the ability to replan at high frequency, and the ability to deal with the uncertainty about how dynamic obstacles may move.

In many situations, a major constraint of robots, including autonomous vehicles, is their ability to perform real-time motion planning in environments with obstacles. Motion planning algorithms tend to be computationally intensive, requiring a vast number of collision checks for each movement.

BRIEF SUMMARY

Specialized robot motion planning hardware for autonomous vehicles are provided. In addition to the systems and devices for motion planning for autonomous vehicles and other robots, a reconfigurable processor is described that can implement the various specialized robot motion planning hardware for autonomous vehicles and other robots. The reconfigurable processor can perform the motion planning for a particular robot and/or particular scenario and then be reconfigured to solve the motion planning for a different robot and/or scenario. The described specialized robot motion planning hardware can perform motion planning operations of solving collision detection and/or finding a shortest path entirely in hardware circuitry or as software executed by a hardware processor, or as a combination of hardware circuitry and software executed by a hardware processor. The hardware and/or software functionality can be considered embodied by a “motion planning module.”

A system for motion planning for autonomous vehicles can include a plurality of sensors, a plurality of detectors in electrical communication with the plurality of sensors, and a motion planning module in electrical communication with the plurality of detectors and a computing system of an autonomous vehicle. The motion planning module stores a planning graph with each node representing, implicitly or explicitly, time and variables defining a state of the autonomous vehicle, an operating environment, or both the state of the autonomous vehicle and the operating environment. The motion planning module receives perception data and sample trajectories from the plurality of detectors, adjusts a probability of collision along each edge in the planning graph that results in a collision with obstacles in the perception data to account for the sample trajectories, determines a path considering cost and probability of collision, and outputs the path to the computing system. The plurality of detectors can include an object detector and an obstacle tracker. A cost grid can be included that receives an obstacle location from the object detector as given by a stream of voxels, and assigns each voxel a cost modifier, which is then sent to the motion planning module.

The motion planning module can include a hardware processor and memory storage. The memory storage can store a planning graph, such as a lattice or other probability road map, that was generated offline prior to real-time motion planning. In some cases, the motion planning module includes hardware collision detection units to perform parallel collision detection. In some cases, the motion planning module includes reconfigurable collision detection acceleration. The precomputed collision data can be stored at a memory storage of the motion planning module such that during motion planning, as perception data is received, the perception data is compared by a hardware processor of the motion planning module to the precomputed collision data stored in the memory storage to determine collisions.

During run-time operation, the edges of the planning graph can be assigned information of one or more variables. One variable can be cost and the second variable can be risk. The cost information can be obtained from a cost grid associated with object detection (static and, optionally, moving objects with calculatable trajectories) in the environment. The risk information can be obtained from sampling the output of the object tracker. Then, the motion planning module generates a path considering cost and risk, representing a legal motion plan, and outputs the motion plan so that a robot can effectuate motion in accordance with the motion plan.

The motion planning module can be programmed for a wide range of robots and expected task scenarios. The motion planning module can be reused, or reprogrammed, for different robots (i.e., reconfigurable) or the motion planning module can be designed for a specific robot. One type of robot can be an autonomous vehicle.

This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

