The U.S. Patent and Trademark Office officially published a series of 73 newly granted patents for Apple Inc. today. In this particular report we touch on a major new Project Titan invention that covers systems and algorithms for planning and controlling the motion of autonomous or partially autonomous vehicles. The new system focuses on the use of two key systems known as "The Behavior Planner," and "The Motion Selector."

The work that Apple is doing in respect to autonomous vehicles is nothing short of staggering. Apple has shown that many projects will be able to tie into Project Titan, like the use of a Mixed Reality Head Mounted Device that will take CarPlay into a whole new dimension.  

For Apple fans who happen to also love cars and reading about the future of cars, Apple's latest Project Titan patent certainly makes for some deep reading on the subject in respect to autonomous vehicles having decision-making algorithms to navigate through dangerous roadways at full road speeds.

Today's granted patent is realistic in understanding the daunting task of driving a vehicle by AI alone. There are so many variables that an autonomous vehicle must be able to observe via camera and various radar systems in order to deliver flawless driving performance.

Our report below provides you with just a basic overview of Apple's patent and if it tempts you to read more, then I've provided a link to the full patent below.

Apple's granted patent states that motorized vehicles which are capable of sensing their environment and navigating to destinations with little or no ongoing input from occupants, and may therefore be referred to as "autonomous" or "self-driving" vehicles, are an increasing focus of research and development. Until relatively recently, due to the limitations of the available hardware and software, the maximum speed at which computations for analyzing relevant aspects of the vehicle's external environment could be performed was insufficient to enable non-trivial navigation decisions to be made without human guidance.

Even with today's fast processors, large memories, and advanced algorithms, however, the task of making timely and reasonable decisions (which are based neither on excessively pessimistic assumptions, nor on excessively optimistic assumptions) regarding an autonomous vehicle's trajectory in the context of unpredictable behaviors of other entities (such as other drivers or other autonomous vehicles) and incomplete or noisy data about the vehicle's environment in real-world traffic remains a significant challenge.

Various embodiments of methods and apparatus for decision making to manage the trajectories or motions of an autonomous vehicle are described. According to one embodiment, the decision-making components associated with an autonomous vehicle may comprise at least a behavior planner and a motion selector. One or both of the behavior planner and the motion selector may comprise respective sets of computing devices.

The Behavior Planner

The behavior planner may be configured to generate candidate sequences of conditional actions and associated anticipated state changes for the vehicle for some selected time horizons (e.g., on the order of tens of seconds, or a few minutes) in an iterative fashion, and provide at least some of the sequences generated during various planning iterations to the motion selector.

The sequences may also be referred to as policies. An action may comprise, for example, an acceleration to a particular speed, a lane change, a deceleration to a particular speed, and so on, and may be associated with a brief time period of a few seconds.

A given state may represent the positions, velocities, and/or other attributes of the autonomous vehicle being controlled, information about the road topology including lane lines, stop signs, road surface etc., as well as other vehicles and other entities in the external environment of the autonomous vehicle.

A transition from one state to another, caused by a particular action taken in the first state of the two, may be associated with a conditional probability (as the action may potentially lead to several other next-states).

In at least some embodiments, the behavior planner may be configured to utilize a decision tree-based technique, such as a variant of a Monte Carlo Tree Search algorithm, to generate the policies. In one embodiment, heuristics obtained from one or more machine learning models, such as deep neural network models, may be used to optimize execution of the decision-tree algorithms--e.g., one or more neural networks may be used to limit the breadth of a tree search, while another neural network may be used to limit the depth to which a tree is searched.

The Motion Selector

The motion selector may use the policies, as well as a number of additional inputs, to generate low-level commands or directives which are then transmitted to various motion-control subsystems of the vehicle (such as the braking subsystem, accelerating subsystem, turning subsystem and the like), causing the vehicle to move along a particular trajectory selected by the motion selector.

The commands or directives may typically be issued at a faster rate in some embodiments than the rate at which the motion selector receives the policies from the behavior planner.

In various embodiments, the autonomous vehicle may comprise a number of different types of sensor devices, including for example various kinds of externally-oriented and/or occupant-oriented cameras, Global Positioning System (GPS) devices, radar devices, light detection and ranging (LIDAR) devices and the like.

The output of the sensor devices, indicative of the environment or "world" within which the autonomous vehicle is operating, may be sampled at different rates by the behavior planner and the motion selector in some embodiments.

The motion selector may be considered the final arbiter with respect to realized trajectories of the vehicle, which may for example involve responding to emergency situations and/or unpredicted behaviors of other entities, and the motion selector may therefore sample the sensor data at a faster rate (a higher frequency) than the behavior planner (which makes somewhat longer-term and probabilistic decisions).

One or both decision making components may be configured to be able to deal with incomplete or noisy data sets from the sensors, as in the case when obstacles partially obscure a view.

Apple's patent FIG. 1 below illustrates an example system environment in which decision-making components of an autonomous vehicle may utilize tree search algorithms in combination with neural network models to control the trajectory of the vehicle, according to at least some embodiments.

Apple's patent FIG. 2 below illustrates an example decision making scenario for an autonomous vehicle, as well as general problem characteristics associated with such decision-making scenarios, according to at least some embodiments.

(Click on image to enlarge)

Apple's patent FIG. 3 below provides an overview of a hybrid approach towards decision making for autonomous vehicles, which involves a combination of stochastic, deterministic and learning-based techniques.

(Click on image to Enlarge)

Apple's patent FIG. 7 below illustrates an overview of neural network models which may be used to optimize tree search operations for autonomous vehicle motion control.

(Click on image to Enlarge)

Apple's granted patent 10,769,525 was originally filed in Q3 2017 and published today by the US Patent and Trademark Office. You could review the full patent here.

Apple Inventors

Joshua Castro: AV Systems Engineer

Martin Levihn: Engineering Manager, Special Projects Group. Note the photo chosen for his LinkedIn page. In the background, Apple seems to be working on a giant next-generation automated warrior prototype for the U.S. Army or a robot for an alien movie for Apple TV+. Whatever it is, it's interesting .

(Click on image to Enlarge)

Nicolas Meuleau: Senior Researcher. He spent almost a decade at NASA

Sebastian Brechtel: Machine Learning Engineer