Deterministic path planning for controlling vehicle movement

Abstract

A system for controlling a movement of a vehicle from an initial state of the vehicle and a target state of the vehicle constructs a graph having multiple nodes defining states of the vehicle and including an initial node defining the initial state of the vehicle and a target node defining the target state of the vehicle and determines a path through the graph connecting the initial node with the target node. The system determines the graph using doubletree construction with an initial tree of nodes originating at the initial node and a target tree of nodes originating at the target node. The doubletree construction is configured to select an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expand the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.

Claims

1. A system for controlling a movement of a vehicle from an initial state of the vehicle and a target state of the vehicle, comprising: a motion planner including a processor configured to construct a graph having multiple nodes defining states of the vehicle, wherein the nodes include an initial node defining the initial state of the vehicle and a target node defining the target state of the vehicle, wherein each pair of nodes in the graph is connected with an edge defined by one of collision free primitive motions moving the vehicle between the states of the connected nodes, determine a path through the graph connecting the initial node with the target node, such that the path defines a sequence of primitive motions moving the vehicle from the initial state to the target state; and transmit the sequence of primitive motions to a controller of the vehicle configured to control the movement of the vehicle using the sequence of primitive motions; wherein the motion planner is configured to determine the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node, wherein, to construct the initial tree or the target tree, the motion planner is configured to select an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expand the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node, wherein the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree.

2. The system of claim 1, wherein the cost of the node is indicative of one or combination of a travel time of the vehicle from the initial state to the target state through the state of the node, a distance the vehicle travels from the initial state to the target state through the state of the node, a rate of change of a mode of movement of the vehicle traveling from the initial state to the target state through the state of the node.

3. The system of claim 1, wherein the motion planner, for selecting the expandable node, is configured to test multiple nodes in an order of their respective costs and to select the first of the tested nodes with the collision free primitive motion reducing the cost of the selected node as the expandable node.

4. The system of claim 1, wherein the motion planner, to expand the expandable node, is configured to order a set of primitive motions based on similarity of each of the primitive motion in the set to a primitive motion defining an edge of the graph leading to the expandable node to produce an ordered set of primitive motions; select, from the ordered set of primitive motions, a first collision free primitive motion that reduces the cost of the expandable node; and expand the graph with the first collision free primitive motion.

5. The system of claim 4, wherein the motion planner tests the primitive motions starting with a primitive motion of an edge leading to the expandable node.

6. The system of claim 4, wherein the motion planner tests the primitive motions starting with primitive motions of a driving mode including a primitive motion of an edge leading to the expandable node.

7. The system claim 4, wherein the motion planner tests the primitive motions starting with a primitive motion of the expandable node with a highest priority.

8. The system of claim 7, wherein the priority of the primitive motion of the expandable node increases if the primitive motion leads to a new node having lower cost than the expandable node; and decreases otherwise decreases.

9. The system of claim 8, wherein the increment or decrement of the priority is linearly proportional to difference of costs of the expandable node and the new node.

10. The system of claim 7, wherein the priority of the primitive motion of the expandable node is set to one if the primitive motion leads to the new node having a lower cost than the expandable node; and otherwise the priority of the primitive motion of the expandable node is set to zero.

11. The system of claim 1, wherein the nodes of the graph are non-uniformly distributed with different values of sparsity at different portions of the graph.

12. The system of claim 11, wherein the motion planner selects a value of the sparsity based on a length of a list of expandable nodes, wherein the value of the sparsity is defined by one or combination of an integration time of control actions forming the primitive motions, and a minimum allowed distance between the child node to a nearest node in the graph.

13. The system of claim 1, wherein the second path is determined by selecting its end node from the expandable node list of the target tree, wherein the end node has the lowest cost.

14. The system of claim 1, wherein the second path is determined by selecting its end node from the target tree, wherein the end node has is closest to an end node of the first path.

15. The system of claim 1, wherein the second path is determined by selecting its end node from the target tree, such that the sum of the second cost and third cost is minimized.

16. The system of claim 1, wherein the motion planner stops constructing the graph when the initial tree and the target tree are connected with a collision free Reed-Shepp's path.

17. The system of claim 1, wherein the target state defines a parking space for the vehicle.

18. The system of claim 1, further comprising: a navigation system including at least one sensor to estimate the initial state of the vehicle and the target state of the vehicle.

19. A method for controlling a movement of a vehicle from an initial state of the vehicle and a target state of the vehicle, wherein the method uses a processor coupled with stored instructions implementing the method, wherein the instructions, when executed by the processor carry out steps of the method, comprising: constructing a graph having multiple nodes defining states of the vehicle, wherein the nodes include an initial node defining the initial state of the vehicle and a target node defining the target state of the vehicle, wherein each pair of nodes in the graph is connected with an edge defined by one of collision free primitive motions moving the vehicle between the states of the connected nodes, wherein the graph includes an initial tree of nodes originating at the initial node and a target tree of nodes originating at the target node, wherein, to construct the initial tree or the target tree, the processor is configured to select an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expand the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node, wherein the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree; determining a path through the graph connecting the initial node with the target node, such that the path defines a sequence of primitive motions moving the vehicle from the initial state to the target state; and transmitting the sequence of primitive motions to a controller of the vehicle configured to control the movement of the vehicle using the sequence of primitive motions.

20. A non-transitory computer readable storage medium embodied thereon a program executable by a processor for performing a method, the method comprising: constructing a graph having multiple nodes defining states of the vehicle, wherein the nodes include an initial node defining the initial state of the vehicle and a target node defining the target state of the vehicle, wherein each pair of nodes in the graph is connected with an edge defined by one of collision free primitive motions moving the vehicle between the states of the connected nodes, wherein the graph includes an initial tree of nodes originating at the initial node and a target tree of nodes originating at the target node, wherein, to construct the initial tree or the target tree, the processor is configured to select an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expand the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node, wherein the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree; determining a path through the graph connecting the initial node with the target node, such that the path defines a sequence of primitive motions moving the vehicle from the initial state to the target state; and transmitting the sequence of primitive motions to a controller of the vehicle configured to control the movement of the vehicle using the sequence of primitive motions.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0025] FIG. 1A shows an example of a parking scenario addressed by some embodiments.

[0026] FIG. 1B shows an exemplar schematic of geometrical representation of a vehicle according to some embodiments.

[0027] FIG. 1C shows a map of a parking space corresponding to the parking scenario of FIG. 1A.

[0028] FIG. 2A shows a block diagram of an automated vehicle control system according to one embodiment.

[0029] FIG. 2B shows a block diagram of a general structure of the motion-planning system according to one embodiment.

[0030] FIG. 3A shows a block diagram of a method performed by a motion planner according to some embodiments.

[0031] FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment.

[0032] FIG. 3C shows a block diagram of a method for a motion planning method according to some embodiments.

[0033] FIG. 4A shows a block diagram of a graph construction method according to one embodiment.

[0034] FIG. 4B shows exemplars of data structures representing a graph according to some embodiments.

[0035] FIG. 4C shows a data structure of a node according to one embodiment.

[0036] FIG. 5A shows a flow chart of a method for tuning graph growth parameters according to principles of some embodiments.

[0037] FIG. 5B shows a flow chart of a method for tuning graph growth parameters according to another embodiment.

[0038] FIG. 5C shows a block diagram of a method for selecting an expandable node from the list of expandable nodes according to some embodiments.

[0039] FIG. 5D shows a block diagram of node expansion according to one embodiment.

[0040] FIG. 5E shows a block diagram of several stop criteria used by some embodiments to terminate the iterative graph construction.

[0041] FIG. 6A shows schematics of a method to determine a cost F(X) for a node X when the target tree includes only a target node according to one embodiment.

[0042] FIG. 6B shows the schematics of a method to determine a cost F(X) for a node X when the target tree includes multiple nodes according to one embodiment.

[0043] FIG. 6C shows schematics of examples illustrating benefits of different embodiments.

[0044] FIG. 7A shows a schematic that illustrates primitive motions associated with a set of control actions custom-character and integration times according to some embodiments.

[0045] FIG. 7B shows an ordered list of primitive motions used by some embodiments to expand a node.

[0046] FIG. 8A shows a block diagram of a method for determining a motion primitive or a subset of motion primitives to expand a selected node according to one embodiment.

[0047] FIG. 8B shows a block diagram of a method for selecting a motion primitive during the expansion of the expandable node according to another embodiment.

[0048] FIG. 9 shows a schematic of a system according to one embodiment.

[0049] FIG. 10 shows a block diagram of an automated parking system according to some embodiments.

DETAILED DESCRIPTION

[0050] It is an object of some embodiments to disclose a path and/or motion planning method that allows real-time path generation for automated vehicle control. It is another object of some embodiments to disclose a motion planning method that allows real-time automated vehicle control, e.g., suitable for automated parking system and method. For clarity purposes only, some embodiments are described in relation to automated parking scenario. However, principles explained in relation to parking scenarios are used by alternative embodiments in other automated vehicle control applications.

[0051] FIG. 1A shows an example of a parking scenario addressed by some embodiments. In this example, the boundary of a parking space 150 is represented by a rectangle with a size of LH. The vehicle 100 has an initial state 101 and needs to be parked at a parking spot defined by a target state 102. Each state, e.g., the initial and the target state, define position and orientation of the vehicle. The parking space 150 includes obstacles. The obstacles can be part of the layout of the parking space, i.e., permanent obstacles 103, such as walls and/or columns of the parking space. Dimensions of the permanent obstacles are usually known, or can be estimated to a reasonable extent. FIG. 1A depicts non-limiting examples of such dimensions.

[0052] Additionally, or alternatively, obstacles can include other parked or moving vehicles 104. Geometrical dimensions of the vehicles 104 and the vehicle 100 to be parked can be determined based on the type of the vehicle. For clarity, this disclosure considers a front wheel drive vehicle; although different embodiments are applied to other vehicles including rear wheel drive and full wheel drive vehicles.

[0053] In some embodiments, layout of the parking space and position of the obstacles 103 are specified on the map of the parking space. Such a map can be predetermined or constructed in real time during or before the parking task. Various embodiments determine a kinematic path 105 connecting the initial state and the target state such that the kinematic path is feasible and collision free.

[0054] FIG. 1B shows an exemplar schematic of geometrical representation of a vehicle according to some embodiments. In this example, the vehicle is abstracted as a rectangle 115. The vehicle state includes the position (x,y) 110, which represents the midpoint of its rear wheel axis, and the orientation 120, which denotes the angle between the vehicle body axis and the horizontal axis.

[0055] Path planning is to solve the following problem. Given an initial configuration X.sub.0 custom-character .sub.free, a goal configuration X.sub.f.sub.free, and system (2), find a collision free kinematically feasible path .sub.t which

[0056] starts at X.sub.0 and ends at X.sub.f;

[0057] lies in the collision-free configuration space custom-character .sub.free;

[0058] satisfies the system kinematics (2).

[0059] Let J() be a cost function that assigns to each non-trivial path a non-negative cost. Optimal path planning is to find a collision free kinematically feasible path custom-character *.sub.t: [0,1].fwdarw..sub.free that minimizes J().

[0060] Motion planning of different embodiments determine how the vehicle moves along the path using kinematic and/or dynamic model of the vehicle 100. For example, a dynamic model of a vehicle accounts for time-dependent changes in the state of the vehicle. Dynamic models typically are represented by differential equations. In one embodiment, the dynamic model of the vehicle is fifth order differential equations

[00001] $\begin{matrix} \dot{x} = \cos () .Math. \cos () .Math. v .Math. .Math. \dot{y} = \sin () .Math. \cos () .Math. v .Math. .Math. \dot{} = \sin () .Math. \frac{v}{b} .Math. .Math. \dot{v} = a_{v} .Math. .Math. \dot{} = a_{s}, & (1) \end{matrix}$

where v the velocity of the front wheels, the angle between the front wheels and the vehicle orientation, a.sub.v the translational acceleration, a.sub.s the steering angular velocity, and b the distance between (x,y) and the midpoint of the front wheels.

[0061] In some embodiments, a path is generated according to the dynamic model (1). A dynamically feasible path is a solution of the dynamic model (1). Accordingly, a vehicle state is X=(x,y,,v,) Since a vehicle typically starts and ends with zero velocity and steering angle, thus the initial and target state for the dynamic model (1) is X.sub.0=(x.sub.0,y.sub.0,.sub.0,0,0) and X.sub.f=(x.sub.f,y.sub.f,.sub.f,0,0), respectively.

[0062] Additionally, or alternatively, some embodiments use a kinematic model of the vehicle for the motion planning that describes motion of the vehicle without consideration of mass of the vehicle or forces that caused the motion. In one embodiment, the following kinematic model is considered

{dot over (x)}=cos()u.sub.1

{dot over (y)}=sin()u.sub.1

{dot over ()}=u.sub.1u.sub.2,(2)

where u.sub.1=cos()v the velocity of the midpoint of the rear wheel axis (named after longitudinal velocity of the vehicle), u.sub.2=tan()/b. Without loss of generality, u.sub.2 is referred as a (normalized) steering angle.

[0063] According to this embodiment, a path is kinematically feasible if it is a solution of the kinematic model (2). A vehicle state X=(x,y,) is collision free only if the vehicle located at X does not collide with any obstacle, and lies completely inside the boundary 105. All collision free vehicle states constitute a collision free configuration space custom-character .sub.free. The initial state 101 is abbreviated as X.sub.0=(x.sub.0,y.sub.0,.sub.0), and the target state 102 is denoted by X.sub.f=(x.sub.f,y.sub.f,.sub.f). For a specific parking task with a parking space represented by a rectangle LH, the vehicle state always belongs to a state space X: [0,L)[0,H)[0,2).

[0064] In such a manner, different embodiments can be applied to both the kinematic model and the dynamic model. Without loss of generality, the following description is developed on the basis of the kinematic model.

[0065] A tree custom-character is a union of a node set V.sub.free and an edge set , i.e., =(V,). Without causing confusion, node, configuration, and vehicle state are used interchangeably below. An edge E(X.sub.i,X.sub.j) represents a collision free kinematically feasible path between nodes X.sub.i and X.sub.j. For a finite set V, |V| denotes the number of its elements.

[0066] Some embodiments determine whether a vehicle state is without collision based on a geometric representation of the parking space, which is also referred to as a map of the parking space. The map of the parking space is derived by approximating all obstacles and the boundary of the parking space as simple geometric shapes. In one embodiment, obstacles 103 in the environment (equivalently the parking space) can be approximated as rectangles, which are derived by constructing a minimal bounding box for each obstacle. With geometric approximation of obstacles and boundary of the parking space, the parking space or the environment can be fully described by a list of geometric objects.

[0067] FIG. 1C shows a map 130 of a parking space corresponding to the parking scenario of FIG. 1A. Both types of obstacles are merged together as one type of permanent obstacles 103 using a rectangular representation. An obstacle can be approximated by multiple geometric shapes, depending on computing power of an onboard processor for path planning. For instance, in another embodiment, obstacles can be approximated by constructing a bounding circle for each obstacle if the computing power is not sufficient. Alternatively, an obstacle can be approximated by a polytope, which however may increase computation burden in path planning. Also, obstacles in the parking space might not be approximated by the same geometric shape. In some embodiments, the environmental map is decomposed into a group of cells, each of which corresponds to a configuration and its neighborhood with a certain volume. Cells could have different volumes. Obstacles in the parking space can be represented by a group of cells.

[0068] FIG. 2A shows a block diagram of automated vehicle control system 299 according to one embodiment. Environment mapping and localization block 201 constructs or updates the map of the space, e.g., parking space, and determines the current location of the vehicle by sensing the environment and vehicle operation condition. For example, an inertial measurement unit (IMU), which may include 3-axis accelerometer(s), 3-axis gyroscope(s), and/or magnetometer(s), can be used to sense the vehicle operation. A global positioning system sensor can be used to provide position and velocity of the vehicle. Sensors to sense the environment 200 can be video cameras capturing obstacles including other vehicles, pedestrians, and buildings, ultrasonic/radar and LiDAR sensors detecting distance between the vehicle and obstacles, etc. In one embodiment, the environment map is further processed to generate a geometric representation of the parking space as shown in FIG. 1C.

[0069] Target state selection 202 selects a target state for a parking spot to park the vehicle by identifying parking lot candidates, and submits the target state to a motion planning block 203. In one embodiment, the available parking spots are tracked by a separate system associated with the management of the parking garage. Additionally, or alternatively, the parking spots can be detected using the sensors 230 of the automated system. In one embodiment, the motion planning block 203 checks to determine whether the target state is parkable, i.e., there is a feasible path to the parking spot, or not, and notifies the target state selection block 202 the check result. If the target state is not parkable, the target selection block 202 selects another target state for evaluation. In another embodiment, the target state selection block 201 can also evaluate whether the target state is parkable, and only sends a parkable target state to the motion planning block.

[0070] If the target state is parkable, then the motion planning 203 initiates a complete motion planning procedure to determine a reference trajectory 241 based on one or combination of the vehicle models 210, the initial and target states of the vehicle, and the map of the parking space. The reference trajectory is a sequence of primitive motions of the vehicle. For example, in one embodiment, the reference trajectory defines profiles of the vehicle velocity and steer angle over time. In another embodiment, the reference trajectory defines the profile of the vehicle state (x, y, ) over time. In most of cases, the reference trajectories various forms are equivalent and one trajectory defines another via the vehicle model.

[0071] The motion-planner transmits the reference trajectory determined by the sequence of primitive motions to controller 204 of the vehicle. Given the reference trajectory 241, vehicle controllers and actuators 204 determine and exert control commands to enforce the vehicle state track its reference trajectory 241. In one embodiment, the control commands could be gas pedal pressure and/or steering torque. The vehicle controller/actuators may use signal 243 and 244 to determine control commands. The signal 243 can be a measured steering angle, or measured currents of motors moving the steering wheel or the gas pedal, the output of the IMU, and the current state of the vehicle estimated by the localization block 201.

[0072] FIG. 2B shows a block diagram of a general structure of the motion-planning system 203 according to one embodiment. The motion-planning system 203 includes at least one processor 270 for executing modules of the motion-planning system 203. The processor 270 is connected 271 to a memory 280 that stores geometrical information 281 such as geometry of the vehicle and a map of the parking space. The memory 280 can also store the models of the vehicle 282 such as a kinematic model of the vehicle and/or a dynamic model of the vehicle. The memory 280 can also store the internal information 283 of the motion planner, including, but not limited to, an initial state of the vehicle, a target state of parked vehicle, cost function, values of each computed state, the motion leading up to each state, a geometric graph, a kinematic graph, waypoints, reference trajectory. In some embodiments, the memory 280 can include stored instructions implementing the method for the automated vehicle control, wherein the instructions, when executed by the processor 270 carry out at least some steps of the method.

[0073] FIG. 3A shows a block diagram of a method performed by a motion planner 203 of a system 299 for controlling a movement of a vehicle from an initial state of the vehicle and a target state of the vehicle according to some embodiments. The motion planner is configured to construct 310 a graph having multiple nodes defining states of the vehicle. The nodes include an initial node defining the initial state of the vehicle and a target node defining the target state of the vehicle. Each pair of nodes in the graph is connected with an edge defined by one of collision free primitive motions moving the vehicle between the states of the connected nodes.

[0074] The motion planner also configured to determine 330 a path through the graph connecting the initial node with the target node, such that the path defines a sequence of primitive motions moving the vehicle from the initial state to the target state; and to transmit 335 the sequence of primitive motions to a controller of the vehicle configured to control the movement of the vehicle using the sequence of primitive motions. Having the graph, the path can be determined using various optimization techniques optimizing a parameter of the path, such as one or combination of its cost and smoothness.

[0075] In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.

[0076] As used herein, the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree. In various embodiments, the cost of the node is indicative of one or combination of a travel time of the vehicle from the initial state to the target state through the state of the node, a distance the vehicle travels from the initial state to the target state through the state of the node, a rate of change of a mode of movement of the vehicle traveling from the initial state to the target state through the state of the node.

[0077] Some embodiments are based on intuition confirmed by a number of simulations and experiments, that the obstacles surrounding a space can be more efficiently avoided by constructing an outward tree from the occluded space to a free space, rather than by constructing an inward tree from the free space toward the occluded space. In a number of applications, such as applications of autonomous parking systems, the parking space is typically more occluded than the space in a garage or a parking lot leading toward the parking space. To that end, some embodiments are based on realization that double tree space exploration can be more computationally efficient than a single tree space exploration and better adhere to a human intuition.

[0078] Some embodiments take advantage of computational efficiency of double trees space exploration by selecting the node on the initial or target tree to expand. Specifically, some embodiments select an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.

[0079] FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment. In this example, the graph is constructed from both ends using an initial tree 321, having an initial node 311 corresponding to the initial state 101, and a target tree 322, having a target node 312 corresponding to the target state 102. The initial tree has a node set and an edge set. The target tree also has a node set and an edge set.

[0080] During a current iteration, a node 313 from the initial or the target tree is selected based on its cost. In this example, the node 313 is selected from the initial tree. For example, in one implementation, the nodes from the initial or the target tree are selected interchangeably. The node 313 has the minimum cost for reaching the target node from the initial node through the node 313 among all nodes of the initial tree. This node is aimed to be expanded with a child node, and, thus, this node is referred as an expandable node.

[0081] The node 313 is selected as an expandable node only if there is a collision free motion primitive that can expand the initial tree by adding a child node connected to the expandable node with an edge defined by that collision free primitive motion. Otherwise, the node 313 is not expandable. To that end, in some embodiments, the motion planner, for selecting the expandable node, is configured to test multiple nodes in an order of their respective costs and to select the first of the tested nodes with the collision free primitive motion reducing the cost of the selected node as the expandable node.

[0082] For example, if all primitive motions that can reduce the cost of the node 313 lead to the obstacles 103, then the node 313 is not expandable, and the embodiments select another node, e.g., a node 331 with cost greater than the cost of the node 313 to expand. If the node 331 is expandable, i.e., there is a collision free motion primitive, such as 336 that reduces the cost of the expandable node 331, the embodiment uses the edge 336 defined by this collision free motion primitive to add to the initial tree 321 a child node 337 that have a cost less than the cost of the node 331.

[0083] Next, in some implementations, the embodiment expands the target tree, e.g., from the node 341. For example, some embodiments construct initial and target trees alternatively, i.e. one after another. The graph construction continues until a termination condition is reached. For example, in one embodiment, the motion planner stops constructing the graph when the initial tree and the target tree are connected with a collision free Reed-Shepp's path.

[0084] In such a manner, deterministic selection and expansion of the trees are achieved. In addition, as used herein, cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree (to consider local information around the initial state), a second cost of a second path through nodes of the target tree (to consider local information around the target state), and a third cost of a third path between nodes of the initial tree and the target tree (to consider relationship between initial and target states). Such a selection of expandable nodes allows considering information gleaned from the construction of both trees making the graph extension more computationally efficient. For example, a number of experiments demonstrated that doubletree graph construction determines the graph with less nodes than a singletree graph construction.

[0085] Some embodiments are based on additional realization than a node expansion, in addition to a node selection, can also be performed in a deterministic manner to reduce the need to explore the space around the node with all possible primitive motions. To that end, one embodiment selects a first collision free primitive motion that reduces the cost of the expandable node. To further reduce the computational burden, some embodiments order a set of primitive motions based on similarity of each of the primitive motions to a primitive motion defining an edge of the graph leading to the expandable node and tests the primitive motions in that order. These embodiments encourage smoothness of vehicle movement, as human operator would want, and, in practice, help to reduce the complexity of the constructed graph, because if a motion primitive leading to a node is collision free, it is possible and even likely that the same motion primitive originating at the node is also collision free.

[0086] For example, the edge 336 is created by the same primitive motion defining an edge of the graph leading to the expandable node 331. Even if there are other primitive motions that can even further reduce the cost of the node 331, the first tested primitive motion is selected to expand the node.

[0087] FIG. 3C shows a block diagram of a method for a motion planning method according to some embodiments. Beginning with the geometry of vehicle, the map of the parking space, and initial and target states, the method first initializes 345 a graph custom-character and outputs an initial graph 350. Based on the initial graph and primitive motions 355, the graph is constructed 360 by repeating two steps: node selection and node expansion using prioritized control actions. As a result, a graph 365 connecting the initial state and the target state or growing into an attraction region of the target state is obtained, and used to determine 370 a kinematic or dynamic path 375. A graph is said growing into an attraction region of the target state if it includes a node which is within distance from the target node. The path can include a sequence of primitive motions driving the vehicle from the initial state to the target state. In some embodiments, a reference trajectory is determined 385 on the basis of a kinematic path and the dynamic model of the vehicle 380. In another embodiment a reference trajectory is determined by smoothing the dynamic path 375 based on the dynamic model 380. Reference trajectory 390 is fed into a control module to control 395 the motion of the vehicle such that the vehicle motion follows the reference trajectory, based on sensed signal 391 such as vehicle's current state.

[0088] FIG. 4A shows a block diagram of a graph construction method according to one embodiment. The graph is initialized 345 based on the initial and/or target states, pre-set graph growth parameters are first adjusted 401 according to a combination of several metrics. For example, the growth parameters can include one or combination of a set of motion primitives, sparsity of the graph, order of selecting motion primitive for node expansion. The growth parameters allows to construct the graph with non-uniformly distributed nodes having different values of sparsity at different portions of the graph. In some embodiments, the motion planner selects a value of the sparsity based on a length of a list of expandable nodes. The value of the sparsity is defined by one or combination of an integration time of control actions forming the primitive motions, and a minimum allowed distance between the child node to a nearest node in the graph.

[0089] In some embodiments, the motion planner stores in a memory one or more lists of expandable nodes. If all expandable node lists are empty, the graph construction stops to select different grows parameters or the method returns failure. Otherwise, an expandable node 411 is selected 402 from an expandable node list. The expandable node 411 is further expanded 403, where prioritized control actions are applied to fulfill the node expansion. Based on the map of the parking space, the node expansion 403 determines possibly none, one, or a set of collision-free child nodes of the expandable node, and accordingly none, one, or a set of collision-free edges between the expandable node and its child nodes. These collision-free child nodes and edges are added to the graph. The construction algorithm terminates if the newly constructed graph meets certain stop criteria; otherwise, repeats tuning 401, selection 402, and expansion 403.

[0090] FIG. 4B shows exemplars of data structures representing a graph according to some embodiments. For example, in one embodiment, a graph custom-character includes at least a set 431 of nodes, and a set 432 of edges, where a node is created based on a certain collision-free state of the vehicle X. An edge represents a collision free kinematically/dynamically feasible path between two nodes. In one embodiment, the graph includes at least a list 421 of expandable node custom-character .sub.sg, and a tree .sub.sg 422. what tree? The graph initialization 345 creates an initial node based on the initial state, and adds the initial node to the expandable list .sub.sg. To simplify notation without causing confusion, this description uses node and state interchangeably.

[0091] In one embodiment, the attraction region of a state is its neighborhood which includes all possible states within a certain distance from the state. A primitive motion is represented by a pair of a pre-defined control action A.sub.i and its integration time t.sub.fi, or a sequence of states results from applying the pair (A.sub.i,t.sub.fi) to the vehicle model. In some embodiments, control actions such accelerations are applied to the vehicle dynamic model to obtain states. In another embodiment, control actions such as velocity and steering angle are applied to the vehicle kinematic model to produce the corresponding states.

[0092] In some embodiments, a pre-defined control action for the vehicle is a composition of steering angle and longitudinal velocity. For simplicity, let us normalize the steering angle and the longitudinal velocity so that both take values within [1,1]. Therefore a control action of the vehicle will be defined over a domain [1,1][1,1]. In order to apply methods taught in this invention, the domain needs approximated to produce pre-defined control actions. In one embodiment, an approximation of the domain is obtained by discretizing the range of the steering angle [1,1] into several (e.g. 5) possible actions {1,0.5,0,0.5,+1}; whereas the range of the longitudinal velocity is discretized into several (e.g. 2) possible actions {1,+1}. The discretization induces a pre-defined action set including pre-defined control actions. For example, in one embodiment, the pre-defined action set A includes ten elements: {(1,1),(0.5,1),(0,1),(+0.5,1),(1,1), (1,1),(0.5,1),(0,1),(+0.5,1),(1,1)}. The pre-defined control action A can be any element of A.

[0093] Similarly, the integration time is a finite positive real number. In one embodiment, the integration time is also normalized such that its domain is [0,1]. For example, one embodiment discretizes its domain into several values. For instance, the domain is uniformly discretized into a finite set of five elements TF={0.2,0.4,0.6,0.8,1}, and value of t.sub.fi is selected from the finite set TF.

[0094] Given action set A and integration time set TF, a motion primitive is associated with a pair of (Ai,tfi). In some embodiments, a set of control actions is pre-defined as

custom-character ={A.sub.1, . . . , };

and a set of integration times is denoted

custom-character ={t.sub.f1, . . . , }.

[0095] Accordingly, | custom-character | primitive motions are defined, with the ith primitive motion corresponds to a pair (A.sub.i,t.sub.fi).

[0096] In some embodiment, each action Ai could have the same integration time. That is TF only contains one element. Motion primitives can be defined accordingly.

[0097] In another embodiment, the graph includes a list 425 of expandable node custom-character .sub.s for the initial tree .sub.s 426, and another expandable node list .sub.g 427 for the target tree .sub.g 428. The graph initialization 345 creates a target node based on the target state, and adds the initial node and target node to the list .sub.s and .sub.g respectively.

[0098] FIG. 4C shows a data structure of a node according to one embodiment. A node 441 has properties of a state 441a, node cost 441b, collision probability of motion primitives 441c, priority of motion primitives 441d, and motion primitive with the highest priority 441e. For example, a state 441a describes the vehicle configuration or location; the cost 441b describes an estimated cost of a path which passes through the node and connects the initial and target states; collision probability of a motion primitive specifies the estimated likelihood that the motion primitive leads to collision; priority 441d determines which primitive mostly likely leads to reduction of cost.

[0099] In some embodiment, the collision probability takes a real value on a continuous domain between 0 and 1; and the priority probability takes a real value on a bounded continuous domain. In another embodiment, the collision probability takes a discrete value from a finite set containing two elements {0,1}|; and the priority takes a discrete value from a finite set containing two elements {0,1}.

[0100] In some embodiments, a new child node initially inherits collision probability and priority of motion primitives from its parent, when the node is generated by applying a primitive to the parent. After the parent node is expanded by applying a motion primitive, the collision probability and the priority of the applied primitive is updated according to the outcome of the primitive. For example, if the primitive leads to the new node and a path between the new node and the parent node in collision, then the collision probability of the primitive of the parent node is increased. In an extreme case, the collision probability is set to one. If the primitive leads to the new node giving a lower cost than the parent node, the priority of the primitive of the parent node is increased, otherwise decreased. In some cases, the priority is increased to one or reduced to zero, depending on the cost of the new node. In such a manner, the deterministic approach that takes advantage of the probabilistic estimation of the motion primitives for each expandable node reduces the computational complexity of graph construction.

[0101] In one embodiment, the priority of a motion primitive is increased or decreased by an amount, which is linearly proportional to the difference between costs of the parent node and the new node. This embodiment increases relative priority of other motion primitives with respect to parent motion primitive to better consider various options in deterministic graph expansion.

[0102] Some embodiments are based on realization that deterministic graph construction 360 leads to the reduction in the number of expandable nodes. In turn, reduction of node expansions increases the sparsity of the constructed graph that on one hand improve computation efficiency, while on another hand reduces options for space exploration. To address this problem created by deterministic node expansion, some embodiments vary sparsity of the graph at different portions of the graph. For example, one implementation maintains a list of potentially expandable node in a memory of motion planner and selects a value of the sparsity based on a length of a list of expandable nodes. For example, the value of the sparsity is defined by one or combination of an integration time of control actions forming the primitive motions, and a minimum allowed distance between the child node of the expandable nodes to a nearest node in the graph.

[0103] FIG. 5A shows a flow chart of a method for tuning graph growth parameters 401 for a single tree custom-character .sub.sg of the graph 365 according to principles of some embodiments. The value of the sparsity defining the neighbor of a vehicle state is adjusted 503 according to the length of the expandable node list 502. In particular, if the length of the expandable node list .sub.sg is below a certain threshold (lower bound), the sparsity defining a distance to a neighbor of a vehicle state is reduced to avoid premature termination of the graph construction (which means no path is feasible). In some embodiments, the sparsity is reduced proportionally and recursively. If the node length goes above another threshold (upper bound), the sparsity is increased proportionally and recursively. The sparsity maintain constants when the length of the node list is between the lower and upper bounds.

[0104] FIG. 5B shows a flow chart of a method for tuning graph growth parameter 402, for a doubletree graph custom-character .sub.s,.sub.g according to some embodiments. Some principles of these embodiments are similar to sparsity adjustment of FIG. 5A. The block 402 returns failure only if both expandable node lists .sub.s, .sub.g are empty. Each tree can have the same or different values of growth parameters, depending on the status of its respective expandable node list.

[0105] FIG. 5C shows a block diagram of a method for selecting 402 an expandable node from the list of expandable nodes according to some embodiments. Normally, some embodiments select the node having the lowest estimated cost in the expandable node list. If the expandable node has been fully expanded (all control actions have been tried), the node is removed 523 from the list, and the algorithm ought to find the lowest cost node from the new expandable node list.

[0106] FIG. 5D shows a block diagram of node expansion 403 according to one embodiment. With the selected expandable node X.sub.best, a control action A.sub.i or a subset of control actions custom-character .sub.i with the high priority are selected 541 and applied to determine 542 child nodes candidates X, using primitive motions corresponding to the selected control actions. In some embodiments, a child node candidate can be obtained by integrating the vehicle model with the initial condition X.sub.best and the selected control action A.sub.i for a pre-defined time period [0,t.sub.fi]. Note that t.sub.fi could be different for different control actions.

[0107] In some embodiments, a primitive motion specifies a control action A.sub.i and time period t.sub.fi applied to the vehicle model. A primitive motion is stored in memory either in the form of the pair (A.sub.i,t.sub.fi), or a sequence of states result from the corresponding control action and time period. The sequence of states are obtained by integrating the vehicle kinematic or dynamic model with a zero initial condition and the corresponding primitive motion.

[0108] As shown in FIG. 5D, a child node candidate X and the edge (X.sub.best,X) are added to the node set and the edge set of the graph, respectively, only if the path as a result of the primitive motion between X.sub.best and X is collision free, using the map information 130. A node cost of the child node X is estimated as F(X), and checked 544 whether it is lower than the node cost of X.sub.best. If yes, the node expansion exits; otherwise, which is the case X.sub.best still has the lowest node cost, another control action or a subset of control actions is selected to continue the expansion of the node X.sub.best.

[0109] FIG. 5E shows a block diagram of several stop criteria used 404 by some embodiments to terminate the iterative graph construction. In one embodiment, a test is conducted 551 to check whether the added child node is close enough to X.sub.f (reaches a pre-defined neighbor of X.sub.f). In another embodiment, one tries to construct 552 a standard Reeds-Shepp's path between the added child node and X.sub.f and verifies 552 if the Reeds-Shepp's path is collision free. If it is, then the Reeds-Shepp's path is added to the edge set of the graph, and the graph construction stops. The graph construction can terminate if the number of nodes exceeds a threshold, in which case the method fails to find a feasible path between X.sub.0 and X.sub.f.

[0110] Some embodiments, in order to perform deterministic selection and expansion of the trees determine the cost of the node to expand by taking an advantage from doubletree graph construction. In some embodiments, the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree (to consider local information around the initial state), a second cost of a second path through nodes of the target tree (to consider local information around the target state), and a third cost of a third path between nodes of the initial tree and the target tree (to consider relationship between initial and target states). Such a selection of expandable nodes allows considering information gleaned from the construction of both trees making the graph extension more computationally efficient. For example, a number of experiments demonstrated that doubletree graph construction determines the graph with less nodes than a singletree graph construction.

[0111] In some embodiments, the graph includes two trees custom-character .sub.s and .sub.g, where the former has a root node X.sub.0, and the latter has a root node X.sub.f. Tree .sub.s and .sub.g are alternatively chosen for expansion in 511. That is, block 511 selects the expandable node list by alternatingly choosing list .sub.s and list .sub.g. In some embodiments, for a current node X, its arrival cost (first cost) and estimated cost-to-go (second cost) are determined differently.

[0112] In one embodiment, each node (state) X is assigned a cost through a properly defined function F():

F(X)=g(X.sub.0,X)+h(X,X.sub.f),

where g(X.sub.0,X) represents the arrival cost from the initial node (state), or a first cost, from X.sub.0 to X; and h(X,X.sub.f) denotes the estimated cost-to-go, or a second cost, from X to X.sub.f. The F-value for a node X is an estimated cost of a potential path from X.sub.0 to X.sub.f while passing through the node.

[0113] In one embodiment, the arrival cost g(X.sub.0,X) sums up the costs of all edges from X.sub.0 to X, where a cost of an edge is a path-cost l(X.sub.0,X) representing the length of a collision-free kinematically/dynamically feasible path between X.sub.0 and X. In another embodiment, the arrival cost additionally includes a control-cost c(u(X.sub.0),u(X)) penalizing the change of control actions along the path from X.sub.0 to X, where u(X) denotes the action leading to X.

[0114] FIG. 6A shows schematics of a method to determine a cost F(X) for a node X when the target tree includes only a target node according to one embodiment. In FIG. 6A, the path between X.sub.0 and X.sub.f is represented by edges (X.sub.0,X.sub.1), . . . , (X.sub.best,X), and thus path-cost can be exactly determined by the length of these edges, i.e.,

l(X.sub.0,X)=l(X.sub.0,X.sub.1)+ . . . +l(X.sub.best,X).

[0115] Similarly, the control cost is

c(u(X.sub.0),u(X))=c(0,u(X.sub.1))+ . . . +c(u(X.sub.best),u(X)).

[0116] In some embodiments, the cost-to-go h(X,X.sub.f) captures exactly the path-cost l(X,X.sub.f) representing the length of a collision-free kinematically/dynamically feasible path between X and X.sub.f. Since the graph constructed hasn't reached the target X.sub.f, one could not find a series of edges connecting X to X.sub.f which means l(X,X.sub.f) is unknown. Hence the estimated cost-to-go h(X,X.sub.f) is in place of l(X,X.sub.f). In some implementations, h(X,X.sub.f) is an estimated path-cost l.sub.e(X,X.sub.f) representing a kinematically/dynamically feasible path between X and X.sub.f without considering obstacles and a collision-cost l.sub.c(X,X.sub.f) accounting for the impact that the obstacles impose on the estimated path-cost.

[0117] For example, assume there exists a kinematically/dynamically feasible path 601 between X and X.sub.f and its cost l.sub.e(X,X.sub.f). In fact, the path 601 is in collision with a circular obstacle 103, and thus l.sub.e(X,X.sub.f) is not the true cost-to-go. Instead, the true cost-to-go corresponds to a path 602, which has a higher cost-to-go than l.sub.e(X,X.sub.f). l.sub.e(X,X.sub.f) is used to approximate the difference l(X,X.sub.f)l.sub.e(X,X.sub.f).

[0118] In some embodiments, l.sub.e(X,X.sub.f) is calculated according to a p-norm of the vector XX.sub.f denoted by |X.sub.fX|.sub.p. In another embodiment, l.sub.e(X,X.sub.f) is the length of a Reeds-Shepp's path between X and X.sub.f. In some embodiments, l(X,X.sub.f)l.sub.e(X,X.sub.f) is a monotonic function of a collision metric f.sub.c(). The collision metric can be constructed as a group Gaussian mixture models, where all vertices of each obstacle are used to construct a Gaussian model. For a node, its collision metric can be evaluated as f.sub.c(X). The higher f.sub.c(X) is, the more likely the neutral path between X and X.sub.f ends up with collision.

[0119] FIG. 6B shows the schematics of a method to determine a cost F(X) for a node X when the target tree includes multiple nodes according to one embodiment. As shown in FIG. 6B, expanding X.sub.0 leads to a tree custom-character .sub.s of nodes with subscript s, whereas expanding X.sub.f leads to a tree .sub.g of nodes with subscript g. Assume that .sub.g is selected 511 for growing, and specifically node X.sub.bestg is selected for expansion since it has the lowest cost among .sub.g. Its expansion, with a control action A.sub.g, results in a child node X.sub.g. The cost of the node X.sub.g is given by the sum of its arrival cost and estimated cost-to-go:

F(x.sub.g)=g(X.sub.f,X.sub.g)+h(X.sub.g,X.sub.0).

[0120] Note that the estimated cost-to-go approximates the path-cost between X.sub.g and X.sub.0.

[0121] In some embodiments, h(X.sub.g,X.sub.0) is approximated as l.sub.e(X.sub.g,X.sub.0) and l.sub.c(X.sub.g,X.sub.0) as above. In another embodiment, h(X.sub.g,X.sub.0) is approximated as follows

h(X.sub.g,X.sub.0)=h(X.sub.g,X.sub.bests)+g(X.sub.0,X.sub.bests),

where X.sub.bests is the node of the list custom-character .sub.s having the lowest cost, g(X.sub.0,X.sub.bests) is the arrival cost (third cost) from X.sub.0 to X.sub.bests and is exactly known, and h(X.sub.g, X.sub.bests)=l.sub.e(X.sub.g, X.sub.bests)+l.sub.c(X.sub.g, X.sub.bests)) is an estimate of the cost-to-go between X.sub.g and X.sub.bests. This definition of the estimated cost-to-go has a significant advantage over the previously estimated cost-to-go: h(X.sub.g,X.sub.0)=l.sub.e(X.sub.g,X.sub.0)+l.sub.c(X.sub.g,X.sub.0), because the former only estimates the path-cost between X.sub.g and X.sub.bests.

[0122] In one embodiment, X.sub.bests is the node of the tree custom-character .sub.s which is closest to X.sub.g. In another embodiment, X.sub.bests is the node list .sub.s which is obtained by solving the following optimization problem

X.sub.bests=arg\min.sub.XX.sub.nears(g(X.sub.0,X)+h(X,X.sub.g)

where X.sub.nears is a set defined as follows

X.sub.nears={X:d(X,X.sub.g),X custom-character .sub.s}

[0123] Note that is a positive finite constant, and d(X.sub.i,X.sub.1) is a distance function between arbitrary two nodes X.sub.i and X.sub.j. X.sub.nears contains all nodes on custom-character .sub.s which is within \gamma distance from X.sub.g. X.sub.bests represents the node on the tree .sub.s which gives the minimum estimated cost-to-go h(X.sub.0,X.sub.g).

[0124] As shown in FIG. 6B, kinematically/dynamically feasible paths 612 between X.sub.g and X.sub.bests are, with a higher probability, shorter (thus can be approximated better by l.sub.e(X.sub.g,X.sub.bests)) than kinematically/dynamically feasible paths 611 between X.sub.0 and X.sub.g, and thus a kinematically/dynamically feasible path between X.sub.bests and X.sub.g is much less likely to collide obstacles, and offers much better estimate of the cost-to-go. Similarly, a cost of a node X.sub.s on the tree custom-character .sub.s can be estimated as follows

F(X.sub.s)=g(X.sub.0,X.sub.s)+h(X.sub.s,X.sub.bestg)+g(X.sub.bestg,X.sub.f),

where X.sub.bestg is the node of the list custom-character .sub.g having the lowest cost, g(X.sub.bests,X.sub.f) is the arrival cost (third cost) from X.sub.f to X.sub.bestg and is exactly known, and h(X.sub.s,X.sub.bestg) is the estimated cost-to-go from X.sub.s to X.sub.bestg.

[0125] In one embodiment, X.sub.bestg is the node of the tree custom-character .sub.g which is closest to Xs. In another embodiment, X.sub.bestg is the node list .sub.g which is obtained by solving the following optimization problem

X.sub.bestg=arg min.sub.XX.sub.nears(g(X.sub.s,X)+h(X,X.sub.f)

where X.sub.nearg is a set of nodes on custom-character .sub.g such that

X.sub.nearg={X:d(X,X.sub.s),X.sub.g}.

X.sub.nearg includes all nodes on custom-character .sub.g which is within \gamma distance from X.sub.s. X.sub.bestg represents the node on the tree .sub.g which gives the minimum estimated cost-to-go h(X.sub.s,X.sub.f).

[0126] FIG. 6C shows schematics of examples illustrating benefits of different embodiments. In these examples, the vehicle needs to move from an initial state 101 to a target state 102, within an environment including various obstacles 103. A method without prioritizing control actions leads to a dense and complex tree 621 that includes of 6339 nodes according to a simulation. An embodiment with deterministic node expansion based on prioritized motion primitives achieves the desired motion with a simpler tree 622 that has only 2465 nodes. An embodiment that uses a doubletree construction, achieves the desired motion with an even more simpler tree 623 of only 1325 nodes.

[0127] FIG. 7A shows a schematic that illustrates primitive motions associated with a set of control actions custom-character and integration times according to some embodiments. Given the initial condition X.sub.o 701 of the vehicle model, applying primitive motion 751 corresponding to a left turn movement with a curvature yields a child node 711. Similarly, applying primitive 75i corresponding to a different movement, e.g., a straight movement or a turn movement with different curvature, yields a child node 71i. The set of all control actions custom-character and the set of integration times are designed such that distances between all node candidates of a given expandable node are at least greater than a certain threshold defining sparsity of the graph. In some embodiments, the distance function between two nodes corresponding to states X.sub.i and X.sub.j are defined as a weighted p-norm of the vector X.sub.iX.sub.j: |X.sub.iX.sub.j|.sub.p.

[0128] In some embodiments, the kinematic vehicle model is used to generate node candidates based on the primitive motions, where a primitive motion includes a control action A.sub.i:(s.sub.i,v.sub.i) and integration time t.sub.fi. Specifically, s.sub.i and v.sub.i is a steering angle of the vehicle steering wheel and a longitudinal velocity of the vehicle, respectively. In some embodiment, s.sub.i,1i| custom-character | uniformly distributes over [1,1]; and v.sub.i only takes value on {1,+1}.

[0129] Alternatively, the dynamic vehicle model can be used to generate node candidates based on the primitive motions, where a primitive motion includes a control action A.sub.i:(a.sub.si,a.sub.vi) and integration time t.sub.fi. Specifically, a.sub.si and a.sub.vi is a steering velocity of the vehicle steering wheel and a longitudinal acceleration of the vehicle, respectively.

[0130] Some embodiments perform a node expansion, in addition to a node selection, in a deterministic manner to reduce the need to explore the space around the node with all possible primitive motions. To that end, an embodiment selects a first collision free primitive motion that reduces the cost of the expandable node, i.e., without testing subsequent primitive motions. To further reduce the computational burden, some embodiments order a set of primitive motions based on similarity of each of the primitive motions to a primitive motion defining an edge of the graph leading to the expandable node and tests the primitive motions in that order. These embodiments encourage smoothness of vehicle movement, as human operator would want, and, in practice, help to reduce the complexity of the constructed graph.

[0131] FIG. 7B shows an ordered list 720 of primitive motions used by some embodiments to expand a node. Some embodiments are based on understanding that there is no need to test all possible primitive motions, only one that is collision free and reduces the cost of the node we want to expand. In addition, if one control action reduces the cost of a parent node, similar control action probably also would reduce the cost of the child node. To that end, if a forward right primitive motion of a parent node is collision free, it make sense to start testing the motion primitives in an order governed by the similarity to the control action leading to the parent node.

[0132] To that end, one embodiment tests the primitive motions starting with a primitive motion of an edge leading to the expandable node. Additionally, or alternatively, one embodiments, to increase space awareness of the graph, tests the primitive motions starting with primitive motions of a driving mode including a primitive motion of an edge leading to the expandable node. For example, the driving mode can be a forward driving mode or a backward driving mode, in which the forward driving mode includes forward primitive motions defining a straight movement, a right turn movement, and a left turn movement in a forward direction, and the backward driving mode includes backward primitive motions defining a straight movement, a right turn movement, and a left turn movement in a backward direction. Additionally, or alternatively, the driving mode can be a straight driving mode or a turn driving mode, wherein the turn driving mode includes different primitive motions for turning movements of the vehicle with different curvatures.

[0133] FIG. 8A shows a block diagram of a method for determining 541 a motion primitive or a subset of motion primitives to expand a selected node X.sub.best according to one embodiment. The embodiment selects 802 a motion primitive or a subset of motion primitives according to untried motion primitives, priority of untried motion primitives 803, and collision probability of untried motion primitives 804. The information 803 and 804 can be readily inferred from properties of the node 441c and 441d, as shown in FIG. 4C

[0134] FIG. 8B shows a block diagram of a method for selecting a motion primitive during the expansion of the expandable node X.sub.best according to another embodiment. The embodiment selects 802 a motion primitive among untried motion primitives 801 such that the distance between the motion primitive and the motion primitive with the highest priority 441e is minimal. This rule is based on the realization that the motion primitive with highest priority 441e is more likely to produce a child node having the lowest cost. That is: the highest priority is assigned to the motion primitive, which gives the lowest node cost among all tried motion primitives. In case that no motion primitive has been tried, motion primitive with the highest priority 441e of X.sub.best is inherited from its parent node.

[0135] If a node is the root node of a tree, the collision probability of all motion primitives are zero (meaning all motion primitives are assumed to be collision free), and the priority of motion primitives 441d are initialized to 1 (means all motion primitives have the same priority). For a child node, its priority and collision probability are initially inherited from its parent node.

[0136] In some embodiment, the collision probability of motion primitives of an expandable node is updated 543 according to the outcome of collision check for its child node candidates. Similarly, the priority of motion primitives of an expandable node is updated 544 according to the node cost result from tried motion primitives. For example, among all child nodes of the expandable node X.sub.best, the priority of a motion primitive is defined as a monotonic function of the cost of the resultant child node: the lower the cost of the child node is, the higher the priority of the motion primitive is.

[0137] FIG. 9 shows a schematic of a system according to one embodiment. The system includes a vehicle 901 including a processor 902 configured for performing an automated parking 950. The vehicle also includes at least one sensor, such as a LIDAR 910 and/or a camera 920. The LIDAR sensor 910 is the low-resolution first sensor and the camera 920 is the high-resolution second sensor. The sensor 910 and/or 920 is operatively connected to the processor 902 and is configured for sensing information indicative of the geometry of at least part of the parking space. Using this information, the processor 902 determines and/or updates the map of the parking space 130. To that end, the processor 902 performs the automated parking 950 using the map 130.

[0138] FIG. 10 shows a block diagram of an automated parking system 1000 according to some embodiments. The system 1000 can be implemented internal to the vehicle 901. Additionally, or alternatively, the system 1000 can be communicatively connected to the vehicle 901.

[0139] The system 1000 can include one or combination of a camera 1010, an inertial measurement unit (IMU) 1030, a processor 1050, a memory 1060, a transceiver 1070, and a display/screen 1080, which can be operatively coupled to other components through connections 1020. The connections 1020 can comprise buses, lines, fibers, links or combination thereof.

[0140] The transceiver 1070 can, for example, include a transmitter enabled to transmit one or more signals over one or more types of wireless communication networks and a receiver to receive one or more signals transmitted over the one or more types of wireless communication networks. The transceiver 1070 can permit communication with wireless networks based on a variety of technologies such as, but not limited to, femtocells, Wi-Fi networks or Wireless Local Area Networks (WLANs), which may be based on the IEEE 802.11 family of standards, Wireless Personal Area Networks (WPANS) such Bluetooth, Near Field Communication (NFC), networks based on the IEEE 802.15x family of standards, and/or Wireless Wide Area Networks (WWANs) such as LTE, WiMAX, etc. The system 400 can also include one or more ports for communicating over wired networks.

[0141] In some embodiments, the system 1000 can comprise image sensors such as CCD or CMOS sensors, lasers and/or camera 1010, which are hereinafter referred to as sensor 1010. For example, the sensor 1010 can convert an optical image into an electronic or digital image and can send acquired images to processor 1050. Additionally, or alternatively, the sensor 1010 can sense the light reflected from a target object in a scene and submit the intensities of the captured light to the processor 1050.

[0142] For example, the sensor 1010 can include color or grayscale cameras, which provide color information. The term color information as used herein refers to color and/or grayscale information. In general, as used herein, a color image or color information can be viewed as comprising 1 to N channels, where N is some integer dependent on the color space being used to store the image. For example, an RGB image comprises three channels, with one channel each for Red, Blue and Green information.

[0143] For example, the sensor 1010 can include a depth sensor for providing depth information. The depth information can be acquired in a variety of ways using depth sensors. The term depth sensor is used to refer to functional units that may be used to obtain depth information independently and/or in conjunction with some other cameras. For example, in some embodiments, the depth sensor and the optical camera can be part of the sensor 1010. For example, in some embodiments, the sensor 1010 includes RGBD cameras, which may capture per-pixel depth (D) information when the depth sensor is enabled, in addition to color (RGB) images.

[0144] As another example, in some embodiments, the sensor 1010 can include a 3D Time Of Flight (3DTOF) camera. In embodiments with 3DTOF camera, the depth sensor can take the form of a strobe light coupled to the 3DTOF camera, which can illuminate objects in a scene and reflected light can be captured by a CCD/CMOS sensor in the sensor 410. Depth information can be obtained by measuring the time that the light pulses take to travel to the objects and back to the sensor.

[0145] As a further example, the depth sensor can take the form of a light source coupled to the sensor 1010. In one embodiment, the light source projects a structured or textured light pattern, which can include one or more narrow bands of light, onto objects in a scene. Depth information is obtained by exploiting geometrical distortions of the projected pattern caused by the surface shape of the object. One embodiment determines depth information from stereo sensors such as a combination of an infra-red structured light projector and an infra-red camera registered to a RGB camera.

[0146] In some embodiments, the sensor 1010 includes stereoscopic cameras. For example, a depth sensor may form part of a passive stereo vision sensor, which may use two or more cameras to obtain depth information for a scene. The pixel coordinates of points common to both cameras in a captured scene may be used along with camera pose information and/or triangulation techniques to obtain per-pixel depth information.

[0147] In some embodiments, the system 1000 can be operatively connected to multiple sensors 1010, such as dual front cameras and/or a front and rear-facing cameras, which may also incorporate various sensors. In some embodiments, the sensors 1010 can capture both still and video images. In some embodiments, the sensor 1010 can include RGBD or stereoscopic video cameras capable of capturing images at, e.g., 30 frames per second (fps). In one embodiment, images captured by the sensor 1010 can be in a raw uncompressed format and can be compressed prior to being processed and/or stored in memory 1060. In some embodiments, image compression can be performed by the processor 1050 using lossless or lossy compression techniques.

[0148] In some embodiments, the processor 1050 can also receive input from IMU 1030. In other embodiments, the IMU 1030 can comprise 3-axis accelerometer(s), 3-axis gyroscope(s), and/or magnetometer(s). The IMU 1030 can provide velocity, orientation, and/or other position related information to the processor 1050. In some embodiments, the IMU 1030 can output measured information in synchronization with the capture of each image frame by the sensor 1010. In some embodiments, the output of the IMU 1030 is used in part by the processor 1050 to fuse the sensor measurements and/or to further process the fused measurements.

[0149] The system 1000 can also include a screen or display 1080 rendering images, such as color and/or depth images. In some embodiments, the display 1080 can be used to display live images captured by the sensor 1010, fused images, augmented reality (AR) images, graphical user interfaces (GUIs), and other program outputs. In some embodiments, the display 1080 can include and/or be housed with a touchscreen to permit users to input data via some combination of virtual keyboards, icons, menus, or other GUIs, user gestures and/or input devices such as styli and other writing implements. In some embodiments, the display 1080 can be implemented using a liquid crystal display (LCD) display or a light emitting diode (LED) display, such as an organic LED (OLED) display. In other embodiments, the display 480 can be a wearable display. In some embodiments, the result of the fusion can be rendered on the display 1080 or submitted to different applications that can be internal or external to the system 1000.

[0150] Exemplary system 1000 can also be modified in various ways in a manner consistent with the disclosure, such as, by adding, combining, or omitting one or more of the functional blocks shown. For example, in some configurations, the system 1000 does not include the IMU 1030 or the transceiver 1070. Further, in certain example implementations, the system 1000 include a variety of other sensors (not shown) such as an ambient light sensor, microphones, acoustic sensors, ultrasonic sensors, laser range finders, etc. In some embodiments, portions of the system 400 take the form of one or more chipsets, and/or the like.

[0151] The processor 1050 can be implemented using a combination of hardware, firmware, and software. The processor 1050 can represent one or more circuits configurable to perform at least a portion of a computing procedure or process related to sensor fusion and/or methods for further processing the fused measurements. The processor 1050 retrieves instructions and/or data from memory 1060. The processor 1050 can be implemented using one or more application specific integrated circuits (ASICs), central and/or graphical processing units (CPUs and/or GPUs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), controllers, micro-controllers, microprocessors, embedded processor cores, electronic devices, other electronic units designed to perform the functions described herein, or a combination thereof.

[0152] The memory 1060 can be implemented within the processor 1050 and/or external to the processor 1050. As used herein the term memory refers to any type of long term, short term, volatile, nonvolatile, or other memory and is not to be limited to any particular type of memory or number of memories, or type of physical media upon which memory is stored. In some embodiments, the memory 1060 holds program codes that facilitate the automated parking.

[0153] For example, the memory 1060 can store the measurements of the sensors, such as still images, depth information, video frames, program results, as well as data provided by the IMU 1030 and other sensors. The memory 1060 can store a memory storing a geometry of the vehicle, a map of the parking space, a kinematic model of the vehicle, and a dynamic model of the vehicle. In general, the memory 1060 can represent any data storage mechanism. The memory 1060 can include, for example, a primary memory and/or a secondary memory. The primary memory can include, for example, a random access memory, read only memory, etc. While illustrated in FIG. 4 as being separate from the processors 1050, it should be understood that all or part of a primary memory can be provided within or otherwise co-located and/or coupled to the processors 1050.

[0154] Secondary memory can include, for example, the same or similar type of memory as primary memory and/or one or more data storage devices or systems, such as, for example, flash/USB memory drives, memory card drives, disk drives, optical disc drives, tape drives, solid state drives, hybrid drives etc. In certain implementations, secondary memory can be operatively receptive of, or otherwise configurable to a non-transitory computer-readable medium in a removable media drive (not shown). In some embodiments, the non-transitory computer readable medium forms part of the memory 1060 and/or the processor 1050.

[0155] The above-described embodiments of the present invention can be implemented in any of numerous ways. For example, the embodiments may be implemented using hardware, software or a combination thereof. When implemented in software, the software code can be executed on any suitable processor or collection of processors, whether provided in a single computer or distributed among multiple computers. Such processors may be implemented as integrated circuits, with one or more processors in an integrated circuit component. Though, a processor may be implemented using circuitry in any suitable format.

[0156] Also, the embodiments of the invention may be embodied as a method, of which an example has been provided. The acts performed as part of the method may be ordered in any suitable way. Accordingly, embodiments may be constructed in which acts are performed in an order different than illustrated, which may include performing some acts simultaneously, even though shown as sequential acts in illustrative embodiments.

[0157] Use of ordinal terms such as first, second, in the claims to modify a claim element does not by itself connote any priority, precedence, or order of one claim element over another or the temporal order in which acts of a method are performed, but are used merely as labels to distinguish one claim element having a certain name from another element having a same name (but for use of the ordinal term) to distinguish the claim elements.

[0158] Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.

Deterministic path planning for controlling vehicle movement

Inventors

Cpc classification

Classification Explorer

B60W2710/207

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G06Q10/047

PHYSICS

Classification Explorer

B60W2420/408

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B62D15/0285

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B60W2720/10

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B60W2420/403

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B60W2720/24

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B60W2420/40

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B60W30/06

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G05D1/0217

PHYSICS

Classification Explorer

G05D1/0088

PHYSICS

Classification Explorer

B60W30/09

PERFORMING OPERATIONS; TRANSPORTING

International classification

Classification Explorer

G05D1/02

PHYSICS

Classification Explorer

B60W30/09

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G06Q10/04

PHYSICS

Classification Explorer

B60W30/06

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G05D1/00

PHYSICS

Abstract

Claims

Description