Invention for Trajectory prediction using temporal logic, tree search and temporal logic of third-party objects
Invented by Marin Kobilarov, Timothy Caldwell, Vasumathi Raman, Christopher Paxton, Zoox Inc
Temporal logic is a formal language used to describe the behavior of systems over time. It provides a way to reason about the temporal relationships between events and actions. In trajectory prediction, temporal logic can be used to specify constraints on the object’s movement, such as speed limits or collision avoidance rules. By incorporating these constraints into the prediction model, the trajectory can be more accurately predicted.
Tree search is a technique used to explore all possible trajectories of an object. It involves generating a tree of possible trajectories and evaluating each one based on a set of criteria, such as the likelihood of collision or the distance from other objects. By exploring all possible trajectories, tree search can identify the most likely path that an object will take.
Temporal logic of third-party objects is a technique used to incorporate information about other objects in the environment into the trajectory prediction model. By considering the behavior of other objects, such as cars or pedestrians, the trajectory prediction can be more accurate. For example, if a pedestrian is walking towards a road, the trajectory prediction model can take this into account and predict that the pedestrian is likely to cross the road.
The market for trajectory prediction using temporal logic, tree search, and temporal logic of third-party objects is growing rapidly. With the increasing demand for autonomous vehicles and robotics, accurate trajectory prediction is becoming more important than ever. Companies such as Waymo, Tesla, and Uber are investing heavily in this technology to improve the safety and efficiency of their products.
In conclusion, trajectory prediction using temporal logic, tree search, and temporal logic of third-party objects is a promising area of research with significant potential for commercial applications. As the demand for autonomous vehicles and robotics continues to grow, the market for this technology is expected to expand rapidly. Companies that invest in this technology now will be well-positioned to take advantage of the opportunities that arise in the future.
The Zoox Inc invention works as follows
Here are the techniques for creating trajectories of autonomous vehicles as well as for predicting trajectories of third-party objects using temporal reasoning and tree search. To determine dynamic and static objects, one can capture perception data. A particular dynamic object can be used to represent a third party vehicle. Predictive trajectories can then be created to show possible trajectories, based on the available options and road rules. Operations can include determining the probability that a third party vehicle will follow a predicted trajectory, and updating these probabilities as time passes. The autonomous vehicle can receive pre-determined trajectories and can issue commands based on these trajectories. A Monte Carlo Tree Search (MCTS), which searches for potential trajectories, can be used to determine a trajectory. Linear Temporal Logic formulas (LTL), are used to validate or reject possible trajectories.
Background for Trajectory prediction using temporal logic, tree search and temporal logic of third-party objects
Autonomous vehicles use a variety of methods, apparatuses and systems to guide them through various environments, including dynamic and static objects. To guide autonomous vehicles through congested areas, such as those with stationary buildings or third-party moving vehicles, including autonomous and non-autonomous vehicles, moving people, and other vehicles, autonomous vehicles use route planning apparatuses, methods, and systems. The autonomous vehicle may not be able to control third-party vehicles and people, making route planning more difficult.
This disclosure describes methods, apparatuses and systems for generating autonomous vehicle trajectories and predicting third-party objects’ trajectories using temporal logic or tree search. Third-party objects can be any objects or vehicles that are not under the control of the autonomous car and/or in communication with it. It is possible to predict the behavior of third-party objects or people with some certainty and incorporate these predictions into the motion planning of the autonomous vehicle.
In certain instances, motion planning can include mission-level planning (e.g. from point A to B), as well as more granular planning such as how the vehicle travels along a section of road surface (e.g., a lane change or how it navigates through an intersection). There are many obstacles and behaviors in an environment like a city. This presents many challenges. For example, accidents and damage can result from inability to navigate an environment correctly. It is possible for autonomous vehicles to anticipate the behavior of third-party objects, which can improve safety and comfort for passengers, drivers, pedestrians, cyclists, etc. “The environment.
As third-party objects increase in proximity to an autonomous vehicle, the number possible trajectories both for them and the autonomous vehicle grows rapidly, often exponentially and without an upper limit. To improve the accuracy and speed of prediction, as well as to provide solutions (e.g., a path) for the autonomous vehicle while traversing an environment, an efficient prediction system is necessary. These and other benefits of the systems, apparatuses and methods are discussed in this article.
A goal for prediction in an autonomous car (also known as a robot), can include predicting all entities or at least all salient entities around the vehicle. As mentioned above, predicting the motion of third-party objects or vehicles (such as pedestrians, cyclists, and moving people) is possible. This can allow for more precise trajectory generation for the autonomous car. A third-party object may include pedestrians, bicyclists or animals. A perception system can record data about a third party object or associated with an environment, such as LIDAR, RADAR, camera, etc. It can also perform segmentation and/or classification on captured data to identify static or dynamic objects. The prediction system may also be able to receive information about static obstacles, such as road lanes or stop areas, in some cases. Based on captured data and/or received data, the prediction system can determine the best trajectories to follow for the third-party object.
The prediction system can also determine the probability that the third-party object will follow each trajectory or determine which trajectors have the greatest impact on the trajectory of an autonomous vehicle. The prediction system can sometimes update the probability that the third party object will choose different trajectories, based on feedback from its perception system. A planner system can provide a list of possible predicted trajectories for the autonomous vehicle, which can then be used to plan a trajectory.
Third-party trajectory prediction may be based in some cases on the measured behavior of the object(s), over time. The prediction system can record motion data, such as speed, heading and acceleration, for the purpose of classifying the behavior of the third party object according to its motion style (e.g. passive, aggressive, normal, or passive). If a third party object is consistently observed traveling above a speed limit in a particular region, the prediction software can increase the probability of a route or trajectory for this object or similar objects with a similar speed.
The prediction system may also include a machine-learning algorithm such as a deep neural net that can be trained on captured motion data in order to predict the behavior of third-party objects based on this captured motion data. The prediction system may also be trained using captured images of third-party objects’ motion over time. This allows it to recognize patterns and suggest possible future actions. If static symbols are associated with an intersection, this could indicate multiple actions (e.g. drive straight, turn left or turn right) and if a second-party object (e.g. a vehicle) slows down and moves to the right of a lanes as it approaches the intersection, the prediction software may extrapolate a prediction that the third party vehicle will turn to the right at that intersection. The prediction system can then predict the trajectory of the third party object using captured data and possible trajectories.
The prediction system can be used in the same way as the decision module of the autonomous vehicle to create a trajectory. The prediction system can employ a tree search (e.g. a Monte Carlo Tree Search), to explore various actions and/or routes that third-party vehicles can follow. It can also use different temporal logic formulas such as linear temporal theory (LTL), signal time logic (STL), and others to determine reasonable predictive trajectories. The prediction system can sometimes associate a probability with a variety of predictive trajectories of the third-party object. In these cases, it can also provide some or all the predictive trajectories of the autonomous car to the decision planner for incorporation into route and/or trajectory planning.
A tree search algorithm like Monte Carlo Tree Search (MCTS), can be used to determine a vehicle’s trajectory. It also uses temporal logic formulas such as Linear Temporal Logic to search for possible trajectories. This allows for verification of whether they comply with road rules. To optimize performance, choose a trajectory. Sometimes, the determination of an autonomous vehicle’s trajectory can also include determining its current state. This can include dynamic symbols representing objects within an environment and static symbols that represent them. Static symbols include, without limitation, stop regions near a stop sign, lane areas defining a lane for an autonomous vehicle to travel, and static objects (e.g. buildings, obstacles, parked cars, etc.). Any region or state in the world (e.g. Washington, California), etc. Other entities can be represented by dynamic symbols, which represent entities whose attributes change over the course of time. Examples include vehicles, pedestrians and bicyclists as well as other dynamic objects like trains, buses, trains, and other vehicles.
Once static and/or dynamic symbols have been determined (e.g. from a map, or a perception systems), processing can include determining features, e.g. temporal logic features, based on these symbols. Sometimes features may include statements that are based on symbols. These statements could return a number such as the determination that an autonomous vehicle lies 5 meters from a stop area.
As the initial state (e.g. a context) is populated by symbols and features, additional elements, known as predicates, can be instantiated based upon the current symbols or features. Predicates may include, without limitation, logical statements that are based on symbols that return value (e.g. Boolean values such a True or False or continuous values that indicate a degree of satisfaction with a statement). A predicate that evaluates True or False depending on whether an autonomous vehicle is within a designated stop area (e.g., close to a stop sign) can be used in this example.
As symbols and features are added to a context, they indicate a state in an environment at an instant. Processing can include determining temporal formulas (e.g. linear temporal (LTL) or signal temporal (STL) formulas) that can be evaluated using the present symbols, features and/or predicates. This disclosure explains that temporal logic can be used for modeling or coding formulas about the future, such as whether certain conditions will become true or false, or whether a condition will remain true until another fact is discovered, etc. For example, temporal logic formulas may include statements about driving behavior that are appropriate for autonomous vehicles. The temporal logic formulas can be used to evaluate candidate routes and trajectories generated for autonomous vehicles. If they do not, trajectories may be rejected or evaluated in relation to other constraints and costs to choose the most efficient.
An LTL formula can sometimes be used to evaluate whether the formula has been violated (e.g. as a Boolean result). Another example is the temporal logic formula STL. This can be used to determine if a condition has been satisfied and to assign a penalty to that state based on how far autonomous vehicles have stopped beyond a stop line. This disclosure also discusses other aspects of temporal logic formulas.
The context in which an autonomous vehicle will operate is known as the environment. This includes all symbols, features, temporal logic formulas, and predicates. Some or all of this context can be used for generating one or more automatons. This can correspond to a finite-state machine that accepts trajectories to determine a trajectory’s cost and/or whether it violates any temporal logic formula associated to the automaton. Referring to “automata” is a term that may be used herein. One or more automatons may be included in the?automata? reference.
Starting with an initial state (e.g. the context or automata), candidate trajectories may be evaluated using one of several tree search algorithms such as a Monte Carlo Tree Search algorithm (MCTS). MCTS searches can model and store various possible trajectories. These can then be compared with the LTL formulas, and/or analyzed to determine the costs associated with different actions. As the MCTS unfolds, a snapshot can be created (e.g. representing the context or automata). This snapshot can then evolve the context based upon changing conditions (e.g. as objects move over time, based upon speculative actions, etc. The snapshot can then be checked for compliance to the LTL formulas. If multiple trajectories do not violate the LTL formula(s), then a trajectory with the lowest cost or highest performance, comfort, etc. will be chosen. You can choose from several possible trajectories. A cost function can be used to penalize acceleration, speed, jerk, and lateral acceleration for different operations or trajectories.
In certain instances, machine learning can help to determine potential trajectories to explore using the MCTS. This is based on the current state and/or the learned trajectories in relation to the tasks and/or states. The MCTS can be used to determine the most likely candidate trajectories based upon current environmental conditions. This includes machine learning to explore and select actions, as well as low-level policies that have been learned (e.g. how to travel on a road lane, change lanes, stop, not tailgate etc.). Learned high-level policies, such as previously selected actions (e.g. trajectories and decisions, commands etc.). Good results. Good outcomes can be described as: “Good outcomes” may refer to the safe completion of tasks (e.g. driving from point A-B) that are efficient, comfortable, and safely.
The prediction system, as mentioned above, can be used in a similar way to the decision module to predict one to three trajectories relative to an autonomous vehicle. The prediction system can identify symbols, features and predicates and generate automata. It can also use tree search algorithms to examine possible trajectories for the third party object. This will determine whether trajectories are in violation of temporal logic formulas and/or rules of road and determine the probability that different trajectories could be implemented by the third party object.
The prediction operations described herein can improve the functioning of a computing device installed in an autonomous car by providing a solid framework for increasing the accuracy of planning models to optimize the vehicle’s performance. Machine learning algorithms can sometimes be used to identify potential trajectories based on relevant situations. Machine learning, as well as tree search algorithms (such MCTS), can be used to quickly determine the possible trajectories for third-party objects. The operations also optimize the trajectory of an autonomous vehicle considering the potential third-party trajectories. In some cases, the use of features, predicates and temporal logic formulas to determine static and dynamic symbols, as well as determining the current state can reduce memory usage and/or improve processing speed by relying on relevant data. Predicting the trajectories and movements of third-party objects in some cases can lead to safer outcomes and/or greater comfort for the occupants of an autonomous car. These and other improvements in the computer’s functioning are discussed here.
The methods, apparatuses and systems described in this document can be implemented in many ways. Below are examples of implementations, with reference to the following images. The methods, apparatuses and systems discussed herein are intended to be used in an autonomous vehicle context, but they can also be applied to other systems that require semi-autonomous or autonomous control, such unmanned aerial vehicles or industrial robots. The methods, apparatuses and systems described herein can be used in various contexts. The techniques described in this article can also be used with real data (e.g. captured using sensor(s), simulated data, or any combination thereof).
FIG. “FIG. The architecture 100 may include computer system(s), 102, which can include various hardware and/or program to implement aspects of these systems, methods and apparatuses. The computer system(s), 102, for example, can contain a route planning module, decision module 106 and trajectory module 108. A data input module 110 is also possible. The architecture 100 may also include a vehicle controller device 114, which can contain various hardware and/or programs to implement the systems, methods and apparatuses described. The vehicle control device 114 may be considered a separate computer system. It can contain an execution module 116 and a fallback determination program 118. A data input module 120 can also be included. The vehicle control device 114 may be included in the computer system.
Click here to view the patent on Google Patents.
