Detecting principal directions of unknown environments

[0001] The present invention relates to apparatus and methods for detecting principal driving directions within an environment.

[0002] Operation of autonomously navigating vehicles, such as robotic vehicles, preferably includes determination of safe and predictable routes through an environment. A human driver is generally capable of detecting principal directions within an environment, such as drivable passageways through a parking lot. However, this is a challenge for autonomous navigation systems capable of operating with human input.

[0003] The present invention relates to apparatus and methods for detecting principal directions within an environment, such as detecting principal driving directions within unmapped environments to facilitate the autonomous navigation of robotic vehicles.

[0004] Examples of the present invention include apparatus and methods that determine features of an environment, such as principal driving directions for driving through the environment. In this context, a principal driving direction (sometimes referred to more briefly as a “principal direction” in examples below) represents a vehicle direction within the environment that a human-operated vehicle would conventionally use, corresponding to directions that a vehicle would be expected to take through the environment. For example, when driving along a road, the principal direction is parallel to the road. In some examples, the principal direction at a point may be multi-valued, for example orthogonal directions where each direction is parallel to a side of a generally rectangular area. In some examples, the sense of direction may be significant (for example, in order to remain on the correct side of a road), in other examples forwards and backwards along the same line may be equivalent.

[0005] Examples of the present invention allow improved autonomous navigation by vehicles, such as robotic vehicles, particularly in highly structured environments for which an accurate map may not be available. Highly-structured environments may include as parking lots, shopping malls, construction zones, and the like. Examples of the present invention allow an autonomous navigation system to detect drivable lanes and principal directions in such environments, allowing the vehicle to navigate the environment in a safer and more predictable manner.

[0006] The determination of principal directions helps a robotic vehicle to comply with driving rules and conventions, allowing predictable operation and allowing the robotic vehicle to safely share the environment with human drivers.

[0007] Data relating to the environment may be provided from on-board sensors, and/or be obtained from other sources. In one approach, sensor data is collected from a sensor associated with a vehicle, or is otherwise obtained. The sensor data is used to generate a representation of the environment, which may be transformed into a two-dimensional representation of the environment. Linear features are detected within the environment, for example using an edge detection algorithm.

[0008] A probabilistic graphical model is then used to obtain the distribution of principal directions within the environment. The graphical model, such as a Markov random field model, is set up having a plurality of nodes representing spatial locations within the environment. The principal direction for each node is determined probabilistically. For example, the graphical model may be used to find the distribution of principal directions over the environment. The nodes may correspond to spatial locations distributed over a two-dimensional grid laid over the environment. The nodes may have an associated cell, representing an area of the environment local to the node.

[0009] Detected linear features within each cell of the graphical model are used to find the local principal direction. If there are a plurality of linear features proximate the spatial location corresponding to a node, for example a plurality of linear features passing through the associated cell, the node may have associated with it a plurality of local principal directions. These local principal directions associated with one node may have different weights associated with then, and weighting factors may include the length of linear features, temporal persistence, contrast between regions separated by linear features, image recognition of road markings or other features, and the like. Linear features provide local evidence of the principal direction for a given node of the graphical model, for example if a linear feature runs through a cell associated with a node, or is otherwise proximate to the spatial location corresponding to the node.

[0010] For many nodes, there may be no useful local evidence of principal direction obtained from the image of the environment. There may be many nodes for which there are no linear features proximate to the spatial location represented by the node. In such cases, the local principal direction for each node can be determined using a potential function for principal direction changes between nodes. The potential function may be chosen to prevent discontinuous or rapid changes in the principal direction, and/or to allow for smooth transitions in principal direction as a function of spatial position between nodes for which the principal direction can be determined from local evidence. The potential function is used to propagate principal direction determinations from nodes proximate a detected feature to the remaining nodes. Hence, even if linear features are sparse, a principal direction can be assigned to all nodes in a probabilistically most likely fashion. Adjacent nodes may represent closely spaced positions within the environment (for example, points separated by 0.1-10 m), so that the principal direction may not be expected to change greatly from one node to the neighboring node, for example possibly in the range 0-20 degrees).

[0011] For example, suppose a first linear feature is proximate a spatial location corresponding to a first node, and a second linear feature is proximate a spatial location represented by a second node. The principal direction for the first node can be determined from the first linear feature, for example being substantially parallel to the first linear feature. Similarly, the principal direction for the second node can be determined. In this example, the first and second nodes are separated by a plurality of nodes for which there is no local evidence of principal direction. A potential function is selected for changes in principal direction going from one node to a neighboring node, such that the principal direction varies continuously from the first node to the second node. Using this or a similar approach, principal directions can be obtained for all relevant nodes even if the local evidence is sparsely distributed over the environment.

[0012] In some examples, a plurality of linear features are proximate a spatial location corresponding to a first node. The principal direction for the first node can be determined using a combination, such as a weighted average, of angular orientations of the proximate linear features and/or other local evidence for the principal direction. Similarly, a weighted average can be used to determine the principal direction for a second node, and the principal directions for nodes between the first and second nodes, absent other local evidence, can be estimated using the potential function.

[0013] Some areas of the environment may be inaccessible to the vehicle, for example due to obstacles. Obstacles may be physical barriers, changes in surface composition (e.g. water, grass, and the like may be detected as obstacles), and the like. No principal direction need be assigned to nodes corresponding to inaccessible areas of the environment. Obstacle detection may use the same environmental sensor, but image resolution may be greater if desired.

[0014] An example method of determining principal directions for an environment comprises forming a graphical model of the environment (such as a Markov random field model), the graphical model having nodes corresponding to spatial locations within the environment. Principal directions are determined for the nodes using linear features detected within the environment. For nodes proximate one or more detected linear features, principal directions are determined from the angular orientation of the linear features. In some examples, for the node to be considered proximate to the linear feature, the linear features runs through a cell associated with a node. In other examples, different proximity measures may be used, such as distance thresholds between the linear feature and the spatial coordinate represented by the node. For nodes not proximate the linear features, principal directions are determined using a potential function for change in principal direction between neighboring nodes, the potential function being selected to obtain a smooth variation in principal directions between neighboring nodes.

[0015] Nodes may represent an array of spatial coordinates within a two-dimensional image representing the environment, for example a square or rectangular grid. The array may also be triangular or other geometric arrangement of node points used. A sensor system can be located on a vehicle to provide image data. For computational simplicity, the image data may be projected onto a two-dimensional representation, so that the nodes may be a planar grid even in the presence of slight altitude changes.

[0016] The principal directions may then be used to steer the vehicle through the environment. For example, a computer on the vehicle may determine the principal directions using a Markov random field model, and be further operable to select a path from a current location to a target location consistent with the detected principal directions. Preferably, the path is generally parallel to the local principal direction along its length.

[0017] The potential function for change in principal direction between neighboring nodes can be chosen to give a smooth variation in principal direction from a first node proximate a linear feature, over intervening nodes not proximate to a linear feature, so a second node proximate another linear feature.

[0018] In some examples of the present invention, a method of determining principal driving directions within an environment comprises obtaining image data representing the environment, detecting linear features within the image data, forming a graphical model of the environment, the graphical model having a plurality of nodes corresponding to spatial locations within the environment, determining principal directions for nodes proximate the linear features using angular orientations the linear features, and assigning principal directions for other nodes so as to obtain a smooth variation of principal direction between adjacent nodes, the smooth variation being obtained using a potential function for angular changes in principal direction between nodes.

[0019] An example apparatus to assist autonomous navigation of a vehicle through an environment comprises an environment sensor supported by the vehicle, and an electronic circuit such as a computer, receiving sensor data from the environment sensor, the electronic circuit being operable to detect linear features within the environment, and determine principal directions within the environment using a Markov random field model. The electronic circuit may comprise a processor operable to execute algorithms implementing methods such as those described herein, memory, data input configured to receive image data, and a data output. The data output may be used as a control signal for a robotic vehicle, for example a steering and/or acceleration signal. A vehicle may accelerate after successful determination of a path to a target location that is consistent with principal direction data.

[0020] A vehicle may support a sensor system including a lidar sensor, a radar sensor, an optical sensor, an IR sensor, an ultrasound sensor, or other sensor, or a combination of one or more such sensors.

[0030] Examples of the present invention include apparatus and methods for determining principal directions within environments, such as principal driving directions for a vehicle in a vehicle environment. Determination of principal directions allows improved autonomous navigation by a vehicle, such as a robotic vehicle.

[0031] In some environments, such as highway driving, a map can be used to determine principal driving directions, and an automated vehicle may travel along the principal driving directions.

[0032] Example environments include complex environments for which a detailed map may not be available, but in which a vehicle preferably obeys the rules of driving. Such environments may include, for example, parking lots, shopping malls, and construction zones. In such environments, human drivers are usually able to partition the space into drivable lanes and drive appropriately, even in the absence of typical road markings and signs. Examples of the present invention allow a robotic vehicle to determine such partitions and principal directions in such environments, allowing the vehicle to navigate the environment in a safer and more predictable manner.

[0033] A robot operating in such an environment can recognize features of the environment that allow it to drive in accordance with driving rules, for example using data from on-board sensors. The determination of principal directions allows a robotic vehicle to comply with driving rules and driving conventions, allowing predictable operation and allowing the robotic vehicle to safely share the environment with human drivers.

[0034] Examples of the present invention include apparatus and methods that determine features of an environment, such as principal directions for driving through the environment. Determination of the principal directions of the environment allows automatic implementation many high-level driving behaviors, such as driving on the correct side of the road (which is helpful for collision avoidance), and avoiding diagonal paths across parking lots (which is often considered rude and unsafe).

[0035] The maximum likelihood field of principal directions θ(x, y) specifies the orientation of the principal direction at every point x, y in a region of interest. Complex driving environments, such as parking lots, have several principal directions. In examples of the present invention, a statistical approach is used to determine a maximum likelihood field of principal directions using the linear features detected within an image of the environment. The linear features are detected in sensor data representative of the local environment, and are used as local evidence regarding the principal directions of the environment. A graphical model, such as a Markov random field model or Bayesian model may be used. Preferably, the graphical model is a non-directional graphical model, such as a Markov random field model.

[0036] Examples of the present invention allow determination of principal directions using sensor data, for example using data from sensors on-board a robotic vehicle. Using conventional approaches, this is a difficult task, as many environments have several principal directions that vary from point to point. Further, sensor data may be noisy and may give rise to conflicting local hypotheses regarding the global principal directions. Examples of the present invention include improved statistical approaches that allow variations of principal directions to be more reliably determined, and conflicting local evidence to be resolved. Some examples of the present invention allow computation of principal directions in real-time, useful for autonomous vehicle navigation, such as robotic vehicle applications.

[0037] FIG. 1A shows an image of an environment, in this case parking lot 10, having drivable lanes such as 12 and 14, and FIG. 1B shows the drivable lanes such as 12 and 14 indicated using linear demarcations superimposed on the parking lot image. FIG. 1B shows a typical structure imposed on the environment by human drivers. Most people will not have any difficulty detecting main drivable lanes in a parking lot when driving in a parking lot such as shown in FIG. 1A. Principal directions are correlated with expected driving directions, for example as indicated by dashed lines such as 16.

[0038] In examples of the present invention, a field of principal directions is calculated within a probabilistic framework. A Markov random field (MRF) model was formulated that allows inference of a high-likelihood field of principal directions, assuming that at every point in the two-dimensional space of the driving environment there is a main preferred direction of motion. The input to the model may comprise observed evidence provided by the vehicle's on-board sensors.

[0039] FIG. 1C illustrates an example approach, comprising acquiring image data 30, image processing 32 (which may include spatial and/or threshold filtering and edge detection), and linear feature detection 34. The output of the approach within dashed box 36 comprises linear feature data, for example length, position, and angular orientation of linear features within the image. Any appropriate process can be used to provide the linear feature data. The example approach further includes setting up a Markov Random Field (MRF) model 38, determining principal directions by using the linear feature data as local evidence of principal directions within the MRF model (40), and may further include improved path planning for an autonomous vehicle using the principal direction data (42).

[0040] FIG. 1D is a simplified schematic of an apparatus comprising environment sensor 50 (one or more sensors may be used), electronic circuit 52, other sensors 54 (for example, collision warning sensors, and output 56. The electronic circuit may be a computer including a processor operable to execute an algorithm that carries out a method such as shown in FIG. 1C.

[0041] In an example approach, a map of the environment is computed from sensor data, such as data from one or more sensors on the vehicle. Sensor data may comprise radar data, lidar data, visual data, or any type of sensor data that allows characterization of the environment. Local linear features are detected within the map, the linear features providing evidence regarding the principal directions of the environment. An MRF is formulated having nodes forming a 2D grid and representing the global principal direction of the environment at the corresponding locations. A solution to the MRF is obtained using fast numeric-optimization techniques (if an exact solution is impractical), allowing principal directions are determined for the environment.

[0042] Local evidence for an MRF-based approach can be obtained using any type of sensor system. Sensor systems are discussed further elsewhere in this specification. After obtaining image data relating to the environment, linear features can be detected within the environment using any available approach.

Linear Feature Detection

[0043] In an example approach, an environment sensor such as a lidar sensor outputs a 3D point cloud. The ground plane is filtered out and data is integrated over time. Data points are projected onto a plane, leading to a 2D obstacle map. Any line segments in the 2D map (e.g., curbs, other cars) provide local evidence of the principal driving directions (“principal directions”), and conventional computer-vision techniques can be used for finding lines in the 2D data. There are several approaches that can be used for detecting linear features in image data.

[0044] FIGS. 2A-2F show a sequence of transforms that led to satisfactory results in example experiments. FIG. 2A shows lidar image data obtained by a lidar sensor on vehicle 60, including trees 62 and paved regions 64 having boundary 66. FIG. 2B shows an obstacle map obtained from this data, including drivable regions 70, and obstacle edges 72 and 74. An MRF model need not have nodes for non-drivable regions.

[0045] FIG. 2C shows the image data 80 after smoothing using a symmetric 2D Gaussian kernel. FIG. 2D shows the effects of a binary threshold filter (25%) applied to the data of FIG. 2C. The threshold filter removed small amplitude noise from the data, smoothed out jagged lines, and “filled in” small gaps within objects such as 82 and 83 (for example, cars or trees), thereby eliminating extra edges. FIG. 2E shows the application of a Canny algorithm used for edge detection, giving edge data 84. Finally, a randomized Hough transform (RHT) was used to find line segments in the data, shown in FIG. 2F as bold solid lines such as lines 86, 88, and 90.

Markov Random Field for Estimating Global Principal Directions

[0046] The maximum likelihood field of principal directions θ(x, y) specifies the principal orientation at every point x, y in the region of interest. Complex driving environments, such as the parking lot shown in FIG. 1A, do not have a single global orientation, but have several principal directions that differ from point to point. The lines obtained from linear feature detection represent local evidence regarding the principal directions of the environment. In examples of the present invention, a statistical approach is used to determine a maximum likelihood field of principal directions using linear features detected within an image of the environment.

[0047] In a representative example, we formulate a discrete version of the inference problem on a regular 2D grid, associating with each point (x_i, y_i) an MRF node with a scalar continuous value θ_i.

[0048] FIG. 3A illustrates an MRF construction for inferring the field of principal directions of the environment. The nodes θ_i (such as node 100) are the MRF variables, α_ik are the input nodes, corresponding to the angles of the observed linear features (also referred to as lines). In this example, all angles are normalized to [0,π/2), because orthogonal lines (e.g., sides of a car) support the same hypothesis for the principal direction at a point. Each MRF node θ_iε[0,π/2) has associated with it a set of evidence nodes α_ikε[0,π/2), one for the angle of each line segment kε[1, K_i] that crosses the grid cell i.

[0049] FIG. 3A shows linear features are shown at 108, 110, 112, and 114. Each node has an associated grid square. Node 100 has associated grid square 102 and node 104 has associated grid square 106.

[0050] FIG. 3B represents local evidence (angular data related to the linear segments) that is used to find the local principal direction for each node proximate a linear feature. In this example, the principal direction for node 100 is determined using evidence node 120. The principal direction for node 104 is determined from combining three evidence nodes 122, 124, and 126, in this example as a weighted average. There are three evidence nodes (related to linear feature orientation angle) for node 104 as three linear features cross grid box 104. There is no local evidence for the principal direction of node 128, as there are no proximate linear features. However, the principal direction for node 128 can inferred probabilistically using a potential function for principal direction changes between neighboring nodes.

[0051] This example MRF uses two sets of potentials associated with the nodes and edges of the graph in FIG. 3. The first potential function (Ψ) is defined on the nodes of the MRF and ties each θ_i to its local evidence α_ik. It is defined as follows:

[0052] $\begin{array}{cc}\Psi \left(\theta \right)=\sum _i\sum _{k=1}^{K_i}{\lambda }_{\mathrm{ik}}\psi \left({\theta }_i,{\alpha }_{\mathrm{ik}}\right),& \left(1\right)\end{array}$
where λ_ik is the weight associated with line k, and ψ is a distance measure between two angles; both are defined below.

[0053] The second potential function (Φ) is defined on the edges of the MRF and enforces a smoothness relationship between the principal directions at neighboring nodes:

[0054] $\begin{array}{cc}\Phi \left(\theta \right)=\frac{1}{2}\sum _i\sum _{j\in N\left(i\right)}\phi \left({\theta }_i,{\theta }_j\right),& \left(2\right)\end{array}$
where N(i) is the set of neighbors of node i, and φ is a distance measure between two angles (defined below). There are many reasonable choices for the distance measures ψ and φ, as well as the weights λ_ik. Several options were evaluated for each. The length of the corresponding line segment was used for the weights λ_ik, with longer segments representing stronger evidence.

[0055] The distance measures ψ and φ can be selected to obtain desired results for a particular environment. Some distances favor smoother fields (e.g., L₂ norm), whereas others (e.g., L₁ norm) have better discontinuity-preserving properties. We empirically investigated several functions, and found the following to be a good choice of a norm for both evidence and smoothness potentials:
ψ(β,γ)=φ(β,γ)=sin²(2(β−γ)).  (3)

[0056] This measure behaves quadratically for small β−γ, and has natural wrap-around properties for our angles in the interval [0,π/2).

[0057] Finally, the distribution of the MRF variables θ for a specific set of observed α is given by a Gibbs distribution:

[0058] $\begin{array}{cc}P\left(\theta |\alpha \right)=\frac{1}{Z}\exp \left(-\left(w_{\psi }\Psi +w_{\phi }\Phi \right)\right),& \left(4\right)\end{array}$
where w_ψ and w_φ are weights, and Z is a normalizer or the partition function. Our goal is to find the maximum-likelihood field of principal directions θ, given the observed evidence α:

[0059] $\begin{array}{cc}{\theta }_{\alpha }^{*}=\arg \underset{\theta }{\max }P\left(\theta |\alpha \right),& \left(5\right)\end{array}$
or, in other words, find θ that minimizes the Gibbs energy U=w_ψΨ+w_φΦ.

[0060] An exact maximum-likelihood solution to the MRF may be computationally impossible for anything but the simplest problems. A typical MRF for a realistic environment will have between several thousand and tens of thousands of nodes. A high-probability mode of the posterior can be computed using conjugate-gradient (CG) optimization. See for example: J. Diebel and S. Thrun, “An application of Markov random fields to range sensing”, In Y. Weiss, B. Scholkopf, and J. Platt, editors, Advances in Neural Information Processing Systems 18, pages 291-298. MIT Press, Cambridge, Mass., 2006; J. R. Diebel, S. Thrun, and M. Bruenig, A bayesian method for probable surface reconstruction and decimation”, ACM Trans. Graph., 25(1):39-59, 2006, which also includes a discussion of discussion of different norms in optimization; and M. R. Hestenes and E. Stiefel, “Methods of conjugate gradients for solving linear systems”, Journal of Research of the National Bureau of Standards, 49:409436, 1952.

[0061] A CG approach works best when an analytical gradient of the energy is specified, which is easily computed for our MRF potentials:

[0062] $\begin{array}{cc}\frac{\partial \Psi }{\partial {\theta }_i}=4\sum _k^{K_i}{\lambda }_{\mathrm{ik}}\sin \left(2\left({\theta }_i-{\alpha }_{\mathrm{ik}}\right)\right)\cos \left(2\left({\theta }_i-{\alpha }_{\mathrm{ik}}\right)\right),& \left(6\right)\\ \frac{\partial \Phi }{\partial {\theta }_i}=-\frac{\partial \Phi }{\partial {\theta }_j}=2\sin \left(2\left({\theta }_i-{\theta }_j\right)\right)\cos \left(2\left({\theta }_i-{\theta }_j\right)\right).& \left(7\right)\end{array}$

[0063] Given the above potentials and the gradient, the implementation of conjugate gradient is standard. The output of the optimization is a high-likelihood field θ(x_i, y_i) that corresponds to the observed lines α.

[0064] An algorithm was tested using a vehicle equipped with an Applanix pose estimation GPS-IMU system and a Velodyne 3D lidar. Representative examples of executing our method are shown in FIGS. 4A-4L. These fields of principal directions were determined during real driving experiments, the fields of principal direction being generated from lidar sensor data using a method such as described herein. Environment image data was collected using the 3D lidar.

[0065] In FIG. 4A-4L, generally the left column of images shows the 2D obstacle map obtained from the vehicle sensors. The center column shows the linear features detected in the obstacles map using a method such as described above, these linear features serve as the input to the MRF. The right column of shows the resulting field of principal directions computed by conjugate-gradient optimization.

[0066] FIGS. 4A-4C show a nearly ideal scenario: a parking lot 140 with two main orthogonal principal directions, e.g. linear boundary 142, which was easily computed by the algorithm.

[0067] FIGS. 4D-4F show data for another, more complex, parking lot 150. This image included trees and a second, differently oriented, parking lot 152 in the bottom-left part of the map. Despite these challenges, the MRF computes a very good estimate of the preferred driving directions 154 for this environment.

[0068] FIGS. 4G-4I show the ability of the algorithm to handle environments with gradually-changing orientations. The field of principal directions correctly follows the curved road segment 160.

[0069] FIGS. 4J-4L show another challenging situation with a curved street 170, an intersection, and an adjacent parking lot 172. A parking lot with diagonally-parked cars is located in upper-right corner of the map at 174. In this situation, the parked cars, whose sides are usually detected as lines, and features of the parking lots themselves (e.g., curbs) present conflicting evidence regarding the principal orientation of the environment.

[0070] FIG. 5 shows a building 182 located very close to a parking lot, the building being oriented at a different angle and providing bad evidence for the MRF. However, as can be seen from the vector field 180 in FIG. 5, the MRF is able to compute the correct orientation for the drivable area, despite the fact that the curb separating the corner of the building from the parking lot is not detected. Linear features are shown, such as features 184 and 186.

[0071] FIG. 6 shows partition of a drivable path for vehicle 190 into left and right sides by considering the relative orientation of the vector towards a Voronoi edge. One side is shown as circular nodes 192, the other as gray squares 194. Line 196 represents the edge of the road. The detected center line is shown as dashed line 198.

[0072] The computation of principal directions was done on a 3 GHz Intel Core-2 PC. Timing results were obtained for experiments run with the following parameters: the obstacle grid was 200 m×200 m with 10 cm resolution, the MRF evidence grid was 200 m×200 m with 5 m resolution (resulting in an MRF with 1600 nodes). The performance of the algorithm was usually dominated by the running time of the conjugate gradient algorithm, and with the average update computation time of around 400 ms, the method is well suited for real-time path planning since it is usually not necessary to update the field of principal directions during every planning cycle.

Path Planning

[0073] Global path planning can be accomplished using algorithms such as continuous forward search via path sampling or discrete search as representative examples. Assuming that a rough global plan has been computed, the field of principal directions can be used in a path-smoothing phase of planning. Given a global plan, the smoothing problem can be formulated as a continuous optimization on the coordinates of the vertices of the trajectory. In this example, smoothness and compliance with principal directions are considered. In other examples, other important aspects of a realistic path smoother such as kinematic constraints of the vehicle and collision-avoidance terms can be included. For a given trajectory {(x_l, y_l)}, the smoothness of the trajectory and the bias towards driving alone principal directions can then be expressed as:

[0074] $\begin{array}{cc}f=w_{\mathrm{sm}}\sum _{l=1}^{N-1}{\left(\Delta x_{l+1}-\Delta x_l\right)}^2+w_{\mathrm{pd}}\sum _{l=1}^N\mu \left(\theta \left(x_l,y_l\right),{\sigma }_l\right),& \left(8\right)\end{array}$
where θ(x_l, y_l) is the principal direction at the MRF node closest to (x_l, y_l); w_sm and w_pd are the weights on smoothness and the principal-direction bias, respectively; μ is a potential on the difference of two angles, which can be defined in a variety of ways, for example:
μ(θ(x_l,y_l),σ_l)=1−cos(2(θ(x_l,y_l)−σ_l))  (9)

[0075] This smoothing problem can be solved using several efficient numerical techniques. One approach is to use a conjugate-gradient algorithm.

[0076] FIGS. 7A-7C illustrates the effect of principal directions on path planning. FIG. 7A shows path planning where principal directions are not used, showing building 202 and curb 204. FIGS. 7B and 7C show path planning favoring trajectories that are aligned with the principal direction (modulus π/2). FIG. 7C uses a higher weight on the principal direction component than the path shown in FIG. 7B.

[0077] FIG. 7A minimizes the quadratic-curvature term in Equation 8, subject to constraints on collision avoidance and kinematics of the car, but w_pm=0 and principal directions are ignored. The driving style exemplified by such a trajectory (200) is often considered sub-optimal. Turning on the bias for aligning the trajectory with the principal directions leads to solutions shown in FIG. 7B (trajectory 206) and FIG. 7C (trajectory 208, where FIG. 7C has a higher w_pm than FIG. 7B). Such compliance with the orientation of the environment can be useful in many driving situations.

Environmental Sensors and Images

[0078] Environment image data can be collected using a lidar environmental sensor associated with the vehicle. However, other sensors can be used, including radar transceivers, optical and/or IR image sensors (including cameras and video sensors), ultrasound devices, and the like. A vehicle may have one or more sensors such as those discussed elsewhere in this specification.

[0079] In some examples, sensor data may be received from a source external to the vehicle, such as wireless reception of data from an external network such as the Internet. Aerial images, such as satellite images, may be obtained over a communications link such as a wireless link, and used to determine principal directions within the environment represented by the received data.

[0080] In other examples, a vehicle may collect sensor data while operating in an environment, for example under human operation or while the environment is not being used by other vehicles. Principal directions may be determined using subsequent analysis, and used by an autonomous vehicle, which need not the same vehicle used to collect the sensor data.

Principal Directions

[0081] Principal driving directions (sometimes referred to herein as “principal directions”) represent vehicle directions within the environment that a human-operated vehicle would conventionally use. For example, in a highly structured environment such as a parking lot, a human-operated vehicle would conventionally move parallel to intended passageways (e.g. the aisles), and such structure may be defined by one or more of the following: parked vehicles, markings on the road such as painted lines, curbs, or areas of vegetation. The principal directions, and intended passageways, represent directions of vehicular motion intended by a designer of the structured environment, or those perceived as the intended directions by a typical human driver. A human driver might choose to disregard such intended directions by driving diagonally across an empty parking lot, but the human driver would generally be aware of the principal directions even as the driver chose to ignore them.

[0082] A highly-structured environment has intended limitations on driving directions imposed by structure, such as and may include environments such as parking lots, shopping malls, construction zones, and the like. Examples of the present invention allow an autonomous navigation system to detect drivable lanes and principal directions in such environments.

[0083] The determination of principal directions helps a robotic vehicle to comply with driving rules and conventions, allowing predictable operation and allowing the robotic vehicle to safely share the environment with human drivers, as discussed further below.

Autonomous Vehicle Operation

[0084] Examples of the present invention allow improved autonomous navigation in structured environments by vehicles, such as robotic vehicles. Environments may include simple environments such as streets and highways, complex environments, and off-road environments. For on-street driving, a map of the global road network can be used to determine principal directions. Determination of the principal directions allows a robotic vehicle to obey driving rules, such as driving on the appropriate side of the road, and not straddling the lane boundaries.

[0085] Example environments also include well-structured environments where a detailed map may not be available, but in which a vehicle should obey the rules of driving. Such environments may include, for example, parking lots, shopping malls, and construction zones. In such environments, human drivers are usually able to partition the space into drivable lanes and drive appropriately, even in the absence of typical road markings and signs. Examples of the present invention allow a robotic vehicle to determine such partitions and principal directions in such environments, allowing the vehicle to navigate the environment in a safer and more predictable manner.

[0086] A robot operating in such an environment can recognize features of the environment that allow it to drive in accordance with driving rules, for example using data from on-board sensors. The determination of principal directions allows a robotic vehicle to comply with driving rules and driving conventions, allowing predictable operation and allowing the robotic vehicle to safely share the environment with human drivers.

[0087] For some unstructured off-road environments, the usual rules of driving may not apply. In such cases there may be no detectable principal directions, for example due to the absence of any detectable linear features, so that a robotic vehicle may choose any drivable and safe path to its goal.

[0088] According to some examples of the present invention, autonomous vehicles may also operate indoors, or within other commercial environments, for example within warehouses.

[0089] Some examples of the present invention include improved methods of mapping an environment. Environment image data may be analyzed so as to detect principal directions.

[0090] Examples of the present invention allow improved autonomous vehicles that can operate predictably in unknown environments and follow the standard conventions of human driving. Another high-level driving behavior that is challenging to implement is the adherence to the established convention of passing oncoming traffic on the correct side. A straightforward method of partitioning the space into “left” and “right” regions can be developed by using a Voronoi diagram of the obstacle map and labeling points based on which side of the Voronoi edge they fall. Conventionally, sensor noise may produce fragmented obstacle maps that can lead to highly irregular Voronoi diagrams. This can be improved by considering the principal direction of the environment instead of the tangent of the Voronoi edge when classifying points (e.g., as shown in FIG. 6) because the former is a more globally consistent feature of the environment and is less sensitive to local noise.

[0091] Hence, examples of the present invention relates to apparatus and methods of detecting principal driving directions in unknown or unmapped environments such as parking lots. Such detection is useful in autonomous navigation to help assist vehicles to operate in a predictable fashion obeying the rules and conventions of driving. Local linear features can be detected in the environment using the vehicle's on-board sensors. The linear feature data can be passed to a Markov random field model whose solution provides a high-likelihood field of principal directions.

[0092] In other examples, the detected features need not be linear. For example, if drivable lanes are known to have curved forms, arcs or other curves may be detected within the environmental image. The evidence node passed to a given node of the MRF may be the average angular orientation of a curve section as it passes proximate to a given node, for example the average orientation of a curve section as it passes through an associated grid square.

[0093] In further examples, obstacle data can be combined with visual camera data and surface-reflectivity data from lidars for detecting and recognizing more advanced features within the environment.

[0094] The invention is not restricted to the illustrative examples described above. Examples described are exemplary, and are not intended to limit the scope of the invention. Changes therein, other combinations of elements, and other uses will occur to those skilled in the art. The scope of the invention is defined by the scope of the claims.