HYPERPLANE SEARCH-BASED VEHICLE TEST

Systems and methods for measuring autonomous vehicle (AV) capabilities in a simulation environment are provided. A method includes selecting, by a computer-implemented system, a first plurality of sampling points in an N-dimensional parameter space associated with a vehicle capability test, classifying, by the computer-implemented system, each sampling point of the first plurality of sampling points into a first class based on a vehicle passing a test scenario associated with the respective sampling point; or a second class based on the vehicle failing the test scenario associated with the respective sampling point; and determining, by the computer-implemented system based on the classifying, a capability of the vehicle. The classifying can include computing a first hyperplane in the N-dimensional parameter space to separate the first plurality of sampling points into the first class and the second class.

BACKGROUND

1. Technical Field

The present disclosure generally relates to autonomous vehicle and, more specifically, to hyperplane search-based vehicle testing.

Autonomous vehicles, also known as self-driving cars, driverless vehicles, and robotic vehicles, may be vehicles that use multiple sensors to sense the environment and move without human input. Automation technology in the autonomous vehicles may enable the vehicles to drive on roadways and to accurately and quickly perceive the vehicle's environment, including obstacles, signs, and traffic lights. Autonomous technology may utilize map data that can include geographical information and semantic objects (such as parking spots, lane boundaries, intersections, crosswalks, stop signs, traffic lights) for facilitating the vehicles in making driving decisions. The vehicles can be used to pick up passengers and drive the passengers to selected destinations. The vehicles can also be used to pick up packages and/or other goods and deliver the packages and/or goods to selected destinations.

DETAILED DESCRIPTION

Autonomous vehicles (AVs) can provide many benefits. For instance, AVs may have the potential to transform urban living by offering opportunity for efficient, accessible and affordable transportation. An AV may be equipped with various sensors to sense an environment surrounding the AV and collect information (e.g., sensor data) to assist the AV in making driving decisions. To that end, the collected information or sensor data may be processed and analyzed to determine a perception of the AV's surroundings, extract information related to navigation, and predict future motions of the AV and/or other traveling agents in the AV's vicinity. The predictions may be used to plan a path for the AV (e.g., from a starting position to a destination). As part of planning, the AV may access map information and localize itself based on location information (e.g., from location sensors) and the map information. Subsequently, instructions can be sent to a controller to control the AV (e.g., for steering, accelerating, decelerating, braking, etc.) according to the planned path.

The operations of perception, prediction, planning, and control at an AV may be implemented using a combination of hardware and software components. For instance, an AV stack or AV compute process performing the perception, prediction, planning, and control may be implemented as software code or firmware code. The AV stack or AV compute process may be executed on processor(s) (e.g., general processors, central processors (CPUs), graphical processors (GPUs), digital signal processors (DSPs), ASIC, etc.) and/or any other hardware processing components on the AV. Additionally, the AV stack or AV compute process may communicate with various hardware components (e.g., on-board sensors and control system of the AV) and/or with an AV infrastructure over a network.

Training and testing AVs in the physical world can be challenging. For instance, to provide good testing coverage, an AV may be trained and tested to respond to various driving scenarios (e.g., millions of physical road test scenarios) before it can be deployed in a real-life roadway system. As such, it may be costly and time-consuming to train and test AVs on physical roads. Furthermore, there may be test cases that are difficult to create or too dangerous to cover in the physical world. Accordingly, it may be desirable to train and validate AVs in a simulation environment.

A simulator may simulate (or mimic) real-world conditions (e.g., roads, lanes, buildings, obstacles, other traffic participants, trees, lighting conditions, weather conditions, etc.) so that an AV may be tested in a virtual environment that is close to a real physical world. Testing AVs in a simulator can be more efficient and allow for creation of specific traffic scenarios. To that end, the AV compute process implementing the perception, prediction, planning, and control algorithms can be developed, validated, and fine-tuned in a simulation environment. More specifically, the AV compute process may be executed in an AV simulator (simulating various traffic scenarios), and the AV simulator may compute metrics related to AV driving decisions, AV response time, etc. to determine the performance of an AV to be deployed with the AV compute process.

In some examples, it may be desirable to understand the capabilities of an AV so that a planned path is drivable (e.g., navigable, maneuverable) by the AV. As an example, a path may include tight turns (e.g., right turns). Accordingly, it may be useful for an AV planning stack to have information about the maximum curvature that the AV may be capable of maneuvering. As another example, a path may include a narrow gap, for example, between buildings and/or parked vehicles. Accordingly, it may be useful for an AV planning stack (e.g., a compute process) of the AV to have information about the minimum gap width that the AV may be capable of driving through.

Accordingly, the present disclosure provides efficient mechanisms for searching and defining vehicle (e.g., AV) capabilities in a way that the vehicle capabilities can be represented by quantifiable measures or metrics. As used herein, a quantifiable measure or metric for a particular vehicle capability may refer to a set of parameters that define the particular vehicle capability. As an example, the capability of a vehicle in making a tight turn can be defined by two parameters, where a first parameter may be a curvature of a path and a second parameter may be a distance between the vehicle's position to the curvature. As another example, the capability of a vehicle in driving through a narrow gap can be defined by three parameters, where a first parameter may be a width of the gap, a second parameter may be a lateral distance, and a third parameter may be a longitudinal distance between the vehicle's position to the gap.

To determine the best combination(s) of parameters representative of the particular vehicle capability, a finite parameter space can be defined with dimensions corresponding to the set of test parameters and a search may be performed in the finite parameter space. More specifically, an N-dimensional parameter space, where N can be any positive integer (e.g., 1, 2, 3, 4 or more), can be defined for testing the particular vehicle capability. Each dimension of the N-dimensional parameter space may correspond to a different one of the test parameters in the set. Each sampling point in the N-dimensional parameter space may define a test scenario (or test case) for the vehicle capability test. In general, a vehicle may pass in some of the test scenarios and fail in others. The best combination(s) of parameters representative of the particular vehicle capability may refer to the combination(s) of parameters at a pass/fail boundary in which the vehicle may pass all test scenarios associated with sampling points on one side of the boundary and fail all test cases associated with sampling points on the other side of the boundary. While the vehicle capability can be found by sampling the entire N-dimensional parameter space densely (e.g., by executing a vehicle compute process for each combination of test parameters in the N-dimensional space to determine a pass/fail result), which can be time-consuming and costly, the disclosed embodiments utilize a search technique that can sample the N-dimensional parameter space sparsely to find a pass/fail boundary in the N-dimensional space. To that end, the pass/fail boundary can be represented by a hyperplane in the N-dimensional parameter space, and the vehicle capability test may be determined by searching (e.g., iteratively) for a best-fit hyperplane that separates sampling points associated with passed test results from sampling points associated with failed test results in the N-dimensional parameter space.

A hyperplane is a decision boundary that classifies data points in a data space (e.g., a multi-dimensional space). The dimension of the hyperplane is one less than the dimension of the data space. For instance, if the data space has 2 dimensions, then the hyperplane in the data space is a line. If the data space has 3 dimensions, then the hyperplane becomes a two-dimensional plane. Data points falling on either side of the hyperplane can be attributed to different classes.

In an aspect of the present disclosure, a computer-implemented system may generate a first plurality of vehicle test scenarios, each corresponding to a different one of a first plurality of sampling points in an N-dimensional parameter space associated with a vehicle capability, where N is a positive integer (e.g., 1, 2, 3, 4, 5 or more). The computer-implemented system may execute a vehicle process (e.g., an AV compute process, an AV stack, and/or an AV planning stack) in each vehicle test scenario of the first plurality of vehicle test scenarios to generate a first test result for the respective vehicle test scenario. The computer-implemented system may compute a first hyperplane in the N-dimensional parameter space based on the first test results. For instance, the first hyperplane may separate (or classify) the first plurality of sampling points into a first group (or class) of sampling points and a second group (or class) of sampling points. The first group of sampling points may correspond to vehicle test scenarios in which the vehicle compute process fails. The second group of sampling points may correspond to test scenarios in which the vehicle compute process passes.

Subsequently, the computer-implemented system may generate a second plurality of vehicle test scenarios based on the first hyperplane, where each of the second plurality of test scenarios may correspond to a different one of a second plurality of sampling points in the N-dimensional parameter space. The computer-implemented system may repeat the execution of the vehicle compute process in each of the second plurality of vehicle test scenarios to generate a second test result for the respective vehicle test scenario and compute a second hyperplane in the N-dimensional parameter space based on the first test results and the second test results. That is, the second hyperplane is a newly derived hyperplane based on the first plurality of sampling points (selected from the previous iteration) and the second plurality of sampling points (selected from the current iteration). For instance, the first plurality of sampling points and the second plurality of sampling points may together form a set of sampling points in the N-dimensional parameter space and the second hyperplane may separate the set of sampling points into a first group (or class) corresponding to vehicle test scenarios in which the vehicle compute process fails and a second group (or class) corresponding to test scenarios in which the vehicle compute process passes.

By keeping or utilizing test results (e.g., the first test results) from an earlier or previous iteration to determine an updated hyperplane for a later or current iteration effectively reduces the weight of test results (e.g., the second test results) from the later or current iteration. This updating technique allows for convergence to a best-fit or optimal hyperplane (pass/fail boundary) with multiple iterations. For instance, the computer-implemented system may perform the vehicle test scenario generation and hyperplane computations iteratively (or repeatedly) until a test termination condition (or threshold) is satisfied. In some aspects, the test termination condition may be based on a difference between a hyperplane computed from a current iteration and a hyperplane computed from a previous iteration being sufficiently small (e.g., satisfying a threshold). After terminating the test, the computer-implemented system may determine a capability (e.g., a quantifiable metric) based on the most recent computed hyperplane.

In some aspects, the computer-implemented system may randomly and/or sparsely sample the N-dimensional parameter space by selecting the first plurality of sampling points in the N-dimensional parameter space, for example, for an initial iteration at the beginning of the vehicle capability test. Subsequently, the computer-implemented system may generate the first plurality of vehicle test scenarios based on the first plurality of sampling points. To reduce the number of test scenarios for testing, the computer-implemented system may determine a search direction for the next iteration based on the first hyperplane. To that end, the computer-implemented system may select the second plurality of sampling points for the next iteration from a subspace of the N-dimensional parameter space, where the subspace may be on one side of the first hyperplane (e.g., on the side in which the sampling points corresponding to vehicle test scenarios in which the vehicle compute process passes are located). In some aspects, the computer-implemented system may sample densely along the first hyperplane (e.g., by randomly selecting the second plurality of sampling points on the first hyperplane). Subsequently, the computer-implemented system may generate the second plurality of vehicle test scenarios based on the second plurality of sampling points.

The systems, schemes, and mechanisms described herein can advantageously define vehicle capabilities with quantifiable metrics and determine the vehicle capabilities via hyperplane searches. Further, utilizing a current hyperplane to determine a search direction for a next iteration can allow for an efficient search (e.g., with a reduced number of test scenarios to be tested), and thus can reduce time and cost (e.g., in terms of compute resources). The reduced time and cost for AV capability testing can be significant. For example, to deploy an AV compute process in an AV, the AV compute process may iterate through multiple development, integration, and release cycles in which test cases are to be re-tested at each stage of a cycle. While the disclosed embodiments describe hyperplane search mechanisms being applied for testing AV capabilities, similar hyperplane search mechanisms may be applied for any other suitable AV tests.

FIG.1illustrates a simulation environment100for autonomous driving in which hyperplane searches may be implemented for AV capability testing, according to some examples of the present disclosure. The simulation environment100may include a simulation platform110simulating a traffic scenario104. The simulation platform110may be any suitable computer-implemented system. In some examples, the simulation platform110may be similar to the simulation platform856ofFIG.8. In some examples, the simulation platform110may be similar to the processor-based system900ofFIG.9. In some examples, the simulation platform110may utilize cloud services for compute resources, storage resources, network resources, etc. In some examples, the simulation platform110may be part of a data center850as shown inFIG.8. In general, the simulation platform110may be used for AV code development, code testing, and/or code integration.

In an aspect, an AV compute process (or software stack)112may be executed on the simulation platform110. The AV compute process112may include a perception stack, a prediction stack, a planning stack, a control stack, etc. as will be discussed more fully below with reference toFIG.8. Further, an AV tester114(e.g., including testing software, tools, testing simulator, etc.) may be executed on the simulation platform110. The AV tester114may generate test cases122for various traffic scenarios (e.g., a scenario104) and test the AV compute process112using the test cases122. To that end, the AV tester114may execute the AV compute process112in the test traffic scenarios and measure the performance of the AV compute process112(or the AV102), for example, in terms of perception, prediction, planning, control, etc., or an overall driving performance. After the AV compute process112successfully passes the test cases122or traffic scenarios, the AV compute process112can be deployed in an AV102, which may be a semi-autonomous vehicle or semi-autonomous vehicle. In some examples, the AV102may be similar to the AV802ofFIG.8.

According to aspects of the present disclosure, the AV tester114may include an AV capability tester120. The AV capability tester120may utilize hyperplane searches as discussed herein to measure the capabilities of the AV102. For instance, the AV capability tester120may sample a finite N-dimensional parameter space representative of traffic scenarios, where N may be any positive integers (e.g., 1, 2, 3, 4, or more). Each dimension of the N-dimensional parameter space may correspond to a test parameter (e.g., related to the position of a vehicle, a lane boundary, a road curvature, etc.) associated with the vehicle capability test. Each sampling point in the N-dimensional parameter space may define a test scenario. The AV capability tester120may generate a plurality of vehicle test scenarios, each corresponding to a different one of a plurality of sampling points in the N-dimensional parameter space. The AV capability tester120may execute the AV compute process112in each test scenario of the plurality of vehicle test scenarios to generate a test result for each respective test scenario. The AV capability tester120may compute a hyperplane in the N-dimensional parameter space to classify or separate the plurality of sampling points into a first group (or class) and a second group (or class) and determine a capability of the AV102based on the hyperplane. For instance, the first group or class may correspond to vehicle test scenarios in which the AV compute process112fails. The second group may correspond to test scenarios in which the AV compute process112passes.

For simplicity of illustration and discussion,FIG.1illustrates a two-dimensional parameter space130(e.g., N=2), where one axis (or dimension) may represent a parameter A and another axis (or dimension) may represent a parameter B. The parameters A and B may be associated with a particular capability of the AV102. To generate the test cases122of AV capability testing, the AV capability tester120may sample the parameter space130by selecting a plurality sampling points132(shown as132a,132b,132c, and132d) in the parameter space130, and configure the parameter A and the parameter B with values corresponding to the sampling points132. As an example, the AV capability tester120may generate a first test case122according to the sampling point132aby configuring the parameter A with a value A1 and the parameter B with a value B1. In a similar way, the AV capability tester120may generate a second test case122according to the sampling point132bby configuring the parameter A with a value A2 and the parameter B with a value B2, and so on. WhileFIG.1illustrates four sampling points132, the AV capability tester120may select any suitable number of sampling points132(e.g., 3, 6, 7, 8 or more). In general, the selection can be sparse and/or random (especially for an initial iteration of the test).

After generating the test cases122, the AV capability tester120may execute the AV compute process112for each of the test cases122to generate a respective test result. The test result may generally be a pass or a failure. In the illustrated example ofFIG.1, the AV compute process112fails the test cases122corresponding to the sampling points132aand132b(shown by the square symbols) but passes the test cases corresponding to the sampling points132cand132d(shown by the circle symbols). To determine which direction to search in the parameter space130for a next iteration, the AV capability tester120may compute a hyperplane140in the parameter space130to separate the sampling points132based on associated pass/fail test results. As shown, the hyperplane140separates the sampling points132into a group of sampling points132corresponding to test cases122for which the AV compute process112passes and another group of sampling points132corresponding to test cases122for which the AV compute process112fails. In some aspects, the AV capability tester120may utilize a stochastic gradient descent (SGD) classifier or a support vector machine (SVM) to compute the hyperplane140.

As will be discussed more fully below with reference toFIGS.4and5A-5B, the AV capability tester120may repeat the sampling point selection (e.g., selecting sampling points along the hyperplane140or on one side of the hyperplane140to narrow the search), the test case generation, the AV compute process execution, and the hyperplane computation until a best-fit hyperplane representative of the capability of the AV102is found. As part of the hyperplane computation, the AV capability tester120may update a hyperplane based on test results from previous iteration(s) and a current iteration.

FIGS.2and3are discussed in relation toFIG.1to illustrate various exemplary AV capability tests using hyperplane searches.FIG.2illustrates an AV capability test scheme200that utilizes hyperplane searches, according to some examples of the present disclosure. The scheme200may be implemented by the AV capability tester120ofFIG.1, the AV tester857ofFIG.8, and/or the processor-based system900ofFIG.9. The scheme200may generate test scenarios or test cases (e.g., the test cases122) to determine a maximum curvature that the AV102may be capable of maneuvering. Stated differently, the scheme200may be used to determine how tight the AV102may make a turn (e.g., a right turn).

For instance, in a traffic scenario201, the AV102may be near an intersection, and a trajectory or path202including a certain curvature206may be planned for the AV102(e.g., by an AV compute process or planning stack executing on the AV102). Accordingly, it may be useful for a planning stack of the AV102to have information about the maximum curvature that the AV102can navigate. To test such a capability of the AV102, the AV capability tester120may determine a two-dimensional parameter space230, where one dimension (e.g., y-axis) may represent a curvature (e.g., the curvature206) of a path and another dimension (e.g., x-axis) may represent a distance (e.g., a distance204) from the AV102's current position to the curvature206. The AV capability tester120may generate test scenarios (e.g., the test cases122) by sampling the parameter space230. As shown, the AV capability tester120may select sampling points232and generate test cases based on the sampling points232. The AV capability tester120may execute the AV compute process112in each test scenario to determine whether the AV compute process112passes or fails in each test scenario. Subsequently, the AV capability tester120may compute a hyperplane240(e.g., a line) to classify the sampling points232into a first class of sampling points232corresponding to test scenarios in which the AV compute process112fails (shown by the square symbols) and a second class of sampling points232corresponding to test scenarios in which the AV compute process112passes (shown by the circle symbols).

As will be discussed more fully below with reference toFIGS.4and5A-5B, the AV capability tester120may repeat the sampling point selection (e.g., selecting sampling points on one side of the hyperplane240to narrow the search), the test case generation, the AV compute process execution, and the hyperplane computation until a computed hyperplane is representative of how tight the AV102is capable of maneuvering.

FIG.3illustrates an AV capability test scheme300that utilizes hyperplane searches, according to some examples of the present disclosure. The scheme300may be implemented by the AV capability tester120ofFIG.1, the AV tester857ofFIG.8, and/or the processor-based system900ofFIG.9. The scheme300may generate test scenarios or test cases (e.g., the test cases122) to determine a minimum gap width that the AV102may be capable of driving through.

For instance, in a traffic scenario301, the AV102may be near a gap302between two objects304and306(which may be buildings, parked vehicles, etc.) and a trajectory or path308planned for the AV102may include driving through the gap302. Accordingly, it may be useful for a planning stack of the AV102to have information about the minimum gap width that the AV102can drive through. To test such a capability of the AV102, the AV capability tester120may determine a three-dimensional parameter space330, where a first dimension (e.g., y-axis) may represent a gap width (e.g., the width310), a second dimension (e.g., x-axis) may represent a longitudinal distance (e.g., the distance312) from the AV102's current position to the gap302, and a third dimension (e.g., z-axis) may represent a lateral distance (e.g., the distance314) of the AV102's current position to the gap302. The AV capability tester120may generate test scenarios (e.g., the test cases122) by sampling the parameter space330. As shown, the AV capability tester120may select sampling points332and generate test scenarios based on the sampling points332. The AV capability tester120may execute the AV compute process112in each test scenario to determine whether the AV compute process112passes or fails in each test scenario. The AV capability tester120may compute a hyperplane340to classify the sampling points332into a first class of sampling points332corresponding to test scenarios in which the AV compute process112fails (shown by the square symbols) and a second class of sampling points332corresponding to test scenarios in which the AV compute process112passes (shown by the circle symbols). The hyperplane340may be any two-dimensional plane of any shape within the three-dimensional parameter space330.

As will be discussed more fully below with reference toFIGS.4and5A-5B, the AV capability tester120may repeat the sampling point selection (e.g., selecting sampling points on one side of the hyperplane340to narrow the search), the test case generation, the AV compute process execution, and the hyperplane computation until a computed hyperplane is representative of how narrow a gap the AV102is capable of maneuvering through.

FIG.4illustrates an AV capability test process400that utilizes hyperplane searches, according to some examples of the present disclosure. The process400can be implemented by a computer-implemented system such as the simulation platform110ofFIG.1, the simulation platform856ofFIG.8, and/or the processor-based system900ofFIG.9. In certain aspects, the process400can be implemented by the AV capability tester120ofFIG.1, the AV tester857ofFIG.8, and/or the AV capability testing service932ofFIG.9. The process400may be performed using any suitable hardware components and/or software components. The process400may utilize similar mechanisms discussed above with reference toFIGS.1-3. Operations are illustrated once each and in a particular order inFIG.4, but the operations may be performed in parallel, reordered, and/or repeated as desired.

At402, a first plurality of sampling points in an N-dimensional parameter space associated with a vehicle capability test may be selected (e.g., for an initial test iteration). N may be a positive integer (e.g., 1, 2, 3, 4, 5, 6 or more). In a first example, the N-dimensional parameter space may correspond to the parameter space130and the first plurality of sampling points may correspond to the sampling points132as shown inFIG.1. In a second example, the N-dimensional parameter space may correspond to the parameter space230and the first plurality of sampling points may correspond to the sampling points232as shown inFIG.2. In a third example, the N-dimensional parameter space may correspond to the parameter space330and the first plurality of sampling points may correspond to the sampling points332as shown inFIG.3. A further example is shown inFIG.5Aand discussed more fully below. In some aspects, the selection may be based on a random selection. The first plurality of sampling points may be randomly spaced or non-uniformly spaced and can be sparse. In some aspects, the number of first plurality of sampling points may be limited to be below a certain threshold, for example, to maintain a low number of test cases.

At404, for each sampling point of the first plurality of sampling points, a first test result is determined based on whether a vehicle (e.g., the AV102and/or the AV402, or more specifically, an AV compute process such as the AV compute process112that operates the vehicle) passes or fails in a test scenario associated with the respective sampling point. To that end, a test scenario may be generated for each sampling point, for example, by configuring test parameters with values corresponding to coordinate values of the respective sampling point, and the AV compute process may be executed in each respective scenario.

At406, a first hyperplane (e.g., the hyperplanes140,240, and/or340) in the N-dimensional parameter space may be computed based on the first test results associated with the first plurality of sampling points. For instance, each of the first plurality of sampling points may be labeled or associated with a pass or fail based on whether the vehicle passes or fails a test scenario configured based on the respective sampling point. The first hyperplane may be computed such that the first hyperplane may partition the N-dimensional parameter space into two subspaces, where all sampled points associated with passed results may be within one subspace and all other sampled points associated with failed results may be within the other subspace. That is, the first hyperplane may operate as a pass/fail boundary in the N-dimensional parameter space. In some aspects, the first hyperplane may be computed using an SGD classifier. In some aspects, the first hyperplane may be computed using an SVM.

At408, a second plurality of sampling points in the N-dimensional parameter space may be selected based on the first hyperplane (e.g., for a next test iteration). In some aspects, as part of the selecting, the second plurality of sampling points may be selected from a subspace of the N-dimensional parameter space that is on one side of the first hyperplane, for example, from the side where the subset of the first plurality of sampling points associated with the passed results are located. In some aspects, the N-dimensional parameter space may be sampled densely along the first hyperplane (e.g., on the first hyperplane) as shown inFIG.5Bas will be discussed more fully below. That is, each of the second plurality of sampling points may have a shorter distance to the first hyperplane than the first plurality of sampling points.

At410, for each sampling point of the second plurality of sampling points, a second test result is determined based on whether the vehicle passes or fails in a test scenario associated with the respective sampling point. For instance, a test scenario may be generated for each sampling point of the second plurality of sampling points and a corresponding second test result may be determined, for example, using mechanisms as discussed at404.

At412, a second hyperplane in the N-dimensional parameter space may be computed based on the first test results associated with the first plurality of sampling points and the second test results associated with the second plurality of sampling points, for example, using similar mechanisms as discussed at406. That is, the second hyperplane is a newly derived hyperplane based on the first plurality of sampling points (selected from the previous iteration) and the second plurality of sampling points (selected from the current iteration). For instance, the first plurality of sampling points and the second plurality of sampling points may together form a set of sampling points in the N-dimensional parameter space and the second hyperplane may separate the set of sampling points into a first group (or class) corresponding to vehicle test scenarios in which the vehicle compute process fails and a second group (or class) corresponding to test scenarios in which the vehicle compute process passes. Utilizing both the first test results from a previous iteration and the second test results from the current iteration to update the hyperplane (e.g., from the first hyperplane to the second hyperplane) may effectively reduce the weight of the second test results from the current iteration for the update. That is, the hyperplane update is based on a weighted combination of test results from a previous iteration and a current iteration.

At414, a determination of whether a hyperplane difference between the second hyperplane (from the current iteration) and the first hyperplane (from the previous iteration) is greater than a threshold may be made, for example, to determine whether the vehicle capability test has converged and can be terminated. In some aspects, a hyperplane may be represented by parameter(s), and the difference between the second hyperplane and the first hyperplane may be based on respective parameter(s) of the second hyperplane and the first hyperplane.

If the difference between the second hyperplane (from the current iteration) and the first hyperplane (from the previous iteration) is greater than the threshold, the process may return to408and repeat the operations at408,410,412, and414. If, however, the difference between the second hyperplane (from the current iteration) and the first hyperplane (from the previous iteration) is not greater than the threshold, the process400may proceed to416. At416, a capability of the vehicle may be determined based on the second hyperplane. Stated differently, the terminating condition for the vehicle capability test is a hyperplane close to (or corresponds to) a best-fit hyperplane being found, and thus hyperplanes computed for consecutive iterations may not vary significantly.

The vehicle capability computed at416may be a quantifiable metric as explained above. More specifically, the vehicle capability may be an associated set of parameters corresponding to coordinate values of a sampling point on the second hyperplane. Referring to the example of AV capability in making a tight turn discussed above with reference toFIG.2, the AV capability may be represented by a parameter pair including a path curvature and an associated distance from the AV location to the curvature. Referring to the example of AV capability in driving through a narrow gap discussed above with reference toFIG.3, the AV capability may be represented by a parameter triplet including a gap width and an associated lateral distance and an associated longitudinal distance from the AV location to the curvature.

FIGS.5A-5Bare discussed in relation toFIG.4to further illustrate hyperplane search-based the AV capability testing process400ofFIG.4.FIG.5Aillustrates a hyperplane search-based AV capability test500during a first iteration (e.g., an initial iteration), according to some examples of the present disclosure.FIG.5Billustrates the hyperplane search-based AV capability test500during a second iteration subsequent to the first iteration, according to some examples of the present disclosure. In an example, the AV capability test500may correspond to the vehicle capability test discussed inFIG.4. For simplicity of illustration and discussion,FIGS.5A and5Billustrate the AV capability test500using a two-dimensional parameter space530with a parameter A and a parameter B. However, in general, the AV capability test process400can include any suitable number of dimensions (e.g., 3, 4, 5, 6 or more).

InFIG.5B, the sampling points552may correspond to the second plurality of sampling points selected based on the first hyperplane computed at408. The sampling points552may be selected as part of an iteration subsequent to the initial iteration. The hyperplane540from the previous iteration is shown as a dotted line inFIG.5Bas a reference. As can be seen, the sampling points552are selected along the hyperplane540and/or from one side of the hyperplane540(e.g., from the side where the group534bof sampling points532associated with passes are located). Each of the sampling points552(for the current iteration) may have a shorter distance to the hyperplane540(from the previous iteration) than the sampling point532(from the previous iteration shown inFIG.5A). As used herein, a distance from a sampling point532to the first hyperplane540may refer to the shortest distance from the respective sampling point532along a line perpendicular (or tangential) to the first hyperplane540. The sampling points552shown by the square symbols may correspond to test scenarios in which the vehicle fails (e.g., the first test results with failures) at410. The sampling points552shown by the circle symbols may correspond to test scenarios in which the vehicle passes (e.g., the first test results with passes) at410. The sampling points532(from the previous iteration) and the sampling points552(newly selected for the current iteration) may together form a set of sampling points as shown inFIG.5Bfor determining an updated hyperplane for the current iteration. For instance, a hyperplane560(the updated hyperplane) can be computed to separate the sampling points532and552into a first group (e.g., upper right portion of the parameter space530) corresponding to test scenarios in which the vehicle fails and a second group (e.g., lower left portion of the parameter space530) corresponding to test scenarios in which the vehicle passes, where the hyperplane560may correspond to the second hyperplane computed at412.

ComparingFIGS.5A-5B, the hyperplane560inFIG.5Bis shifted towards the origin compared to the hyperplane540from the previous iteration shown inFIG.5A. The AV capability test500can iterate through one or more iterations until the hyperplane from one iteration is about the same as the hyperplane from a previous iteration. That is, the AV capability test500can be iterated until it converges to a solution indicative of the capability of the AV. In some aspects, a hyperplane (e.g., the hyperplanes140,240,340,540, and560) may be expressed in terms of a weight parameter (e.g., the w1 vector shown inFIG.5Aand the w2 vector shown inFIG.5B), and the AV capability test500may be terminated based on a difference between a weight parameter of a hyperplane from a current iteration and a weight parameter of a hyperplane from a previous iteration satisfies a threshold. In general, a hyperplane can be described by an equation (a hyperplane equation) including parameters with a w vector (e.g., w1 or w2) tangential to the hyperplane being one of the parameters.

FIG.6illustrates an AV capability test process600that utilizes hyperplane searches, according to some examples of the present disclosure. The process600can be implemented by a computer-implemented system such as the simulation platform110ofFIG.1, the simulation platform856ofFIG.8, and/or the processor-based system900ofFIG.9. In certain aspects, the process400can be implemented by the AV capability tester120ofFIG.1and/or the AV capability testing service932ofFIG.9. The process600may be performed using any suitable hardware components and/or software components. The process600may utilize similar mechanisms discussed above with reference toFIGS.1-4and5A-5B. Operations are illustrated once each and in a particular order inFIG.6, but the operations may be performed in parallel, reordered, and/or repeated as desired.

At602, a first plurality of vehicle test scenarios may be generated. Each of the first plurality of vehicle test scenarios may correspond to one of a first plurality of sampling points (e.g., the sampling points132,232,332,532) in an N-multi-dimensional parameter space (e.g., the parameter space130,230,330,530), where N can be any positive integers. The N-dimensional space may have dimensions associated with at least one of a vehicle position or a lane boundary.

At604, a vehicle compute process (e.g., the AV compute process112) may be executed in each vehicle test scenario of the first plurality of vehicle test scenarios to generate a first test result for each respective vehicle test scenario.

At606, a first hyperplane (e.g., the hyperplane140,240,340,540) within the multi-dimensional parameter space may be computed based on the first test results, for example, using an SGD classifier or an SVM. In some aspects, the first hyperplane may separate the first plurality of sampling points into a first group of sampling points corresponding to vehicle test scenarios in which the vehicle compute process failed and a second group of sampling points corresponding to vehicle test scenarios in which the vehicle compute process passed.

At608, a second plurality of vehicle test scenarios may be generated based on the first hyperplane. Each of the second plurality of vehicle test scenarios may correspond to one of a second plurality of sampling points (e.g., the sampling points552) in the N-dimensional parameter space. In some aspects, as part of generating the second plurality of vehicle test scenarios, the second plurality of sampling points in the multi-dimensional parameter space may be selected based on the first hyperplane, for example, as shown inFIG.5B. As an example, the second plurality of sampling points may be along (or close to) the first hyperplane computed at606, where each of the plurality of sampling points may have a shorter distance to the first hyperplane than each of the first plurality of sampling points. Further, in some instances, a greater number of sampling points may be selected for the second plurality of sampling points than for the first plurality of sampling points.

In some aspects, the process600may further include executing the vehicle compute process in each vehicle test scenario of the second plurality of vehicle test scenarios to generate a second test result for each respective vehicle test scenario. The process600may further include computing, based on the first test results and the second test results, a second hyperplane (e.g., the hyperplane560) in the multi-dimensional parameter space. The process600may further include determining, based on the second hyperplane, a vehicle capability associated with the vehicle compute process.

FIG.7illustrates an AV capability test process700that utilizes hyperplane searches, according to some examples of the present disclosure. The process700can be implemented by a computer-implemented system such as the simulation platform110ofFIG.1, the simulation platform856ofFIG.8, and/or the processor-based system900ofFIG.9. In certain aspects, the process700can be implemented by the AV capability tester120ofFIG.1and/or the AV capability testing service932ofFIG.9. The process700may be performed using any suitable hardware components and/or software components. The process700may utilize similar mechanisms discussed above with reference toFIGS.1-4,5A-5B, and6. Operations are illustrated once each and in a particular order inFIG.7, but the operations may be performed in parallel, reordered, and/or repeated as desired.

At702, a first plurality of sampling points (e.g., the sampling points132,232,332,532) in an N-dimensional parameter space (e.g., the parameter space130,230,330,530) associated with a vehicle capability test (e.g., the test500ofFIGS.5A-5B) may be selected. In some examples, N may be an integer greater than 1. In some aspects, the selecting the first plurality of sampling points may be based on a random selection in the N-dimensional parameter space. In some aspects, the selecting the first plurality of sampling points may be based on a threshold number of test scenarios, for example, to limit the number of test scenarios for the vehicle capability test. In some aspects, the N-dimensional parameter space may include dimensions associated with at least one of a vehicle position or a lane boundary.

At704, each sampling point of the first plurality of sampling points may be classified into a first class based on a vehicle passing a test scenario associated with the respective sampling point or a second class based on the vehicle failing the test scenario associated with the respective sampling point. In some aspects, the classifying each sampling point of the first plurality of sampling points into the first class or the second class may be performed using an SGD classifier or an SVM. In some aspects, the classifying each sampling point of the first plurality of sampling points may include computing a first hyperplane (e.g., the hyperplane140,240,340,540,560) in the N-dimensional parameter space. The first hyperplane may separate the first plurality of sampling points into the first class and the second class.

At706, a capability of the vehicle may be determined based on the classifying at704. In some aspects, the N-dimensional parameter space may be associated with at least one of a path curvature or a distance from the vehicle to the path curvature, the capability of the vehicle may be associated with a navigable path curvature, for example, as discussed above with reference toFIG.2. In other aspects, the N-dimensional parameter space may be associated with at least one of a width of a gap, a lateral distance from the vehicle to the gap, or a longitudinal distance from the vehicle to the gap, and the capability of the vehicle may be associated with a navigable gap size, for example, as discussed above with reference toFIG.3.

In some aspects, the process700may further include configuring one or more test parameters for a first test scenario based on a first sampling point of the first plurality of sampling points. In some aspects, the selecting the first plurality of sampling points at702may be based on a second hyperplane in the N-dimensional parameter space, where the second hyperplane is different from the first hyperplane. For example, the second hyperplane may be computed from a previous iteration, where the second hyperplane separates a second plurality of sampling points in the N-dimensional parameter space into the first class and the second class. As such, the first plurality of sampling points (for the current iteration) can include the second plurality of sampling points (from the previous iteration). In some aspects, the process700may further include terminating the vehicle capability test based on a comparison between the first hyperplane and the second hyperplane. In some aspects, the process700may further include terminating the vehicle capability test based on a difference between a first weight associated with the first hyperplane and a second weight associated with the second hyperplane satisfying a threshold. In some aspects, the determining the capability of the vehicle based on the first hyperplane at706may be responsive to a difference between the first hyperplane and the second hyperplane satisfying a threshold.

In some aspects, the AV capability testing mechanisms discussed above with reference toFIGS.1-4,5A-5B, and/or6-7can be applied during a development stage, an integration stage, or a release stage. For example, during a development stage, a developer may develop an enhancement to an AV capability in an AV planning stack and may utilize the AV capability testing mechanisms to measure the enhancement. During an integration stage, the AV planning stack may be merged or integrated with a certain code base and tested using the AV capability testing mechanisms to determine whether the merged or integrated code operates correctly (e.g., with the expected AV capability enhancement). During a release stage, a code release may be created from the validated code base and tested using the AV capability testing mechanisms to determine whether the merged or integrated code operates correctly (e.g., with the expected AV capability enhancement). In general, the disclosed AV capability testing mechanisms can be applied to any stage of an AV code development, integration, and release cycle. The disclosed AV capability testing mechanisms can provide quantifiable AV capability measures, and thus can be effective in determining whether an integration code or a release code performs as expected. Further, the quantifiable AV capability measures can facilitate an AV planning stack in determining a trajectory for an AV or adjusting a trajectory for an AV based on a target AV to be deployed with the AV planning stack. Further still, the hyperplane searches disclosed herein can reduce testing time, and thus can shorten the time for code, integration, and release cycles.

While examples of an AV's capability in making a tight turn or driving through a narrow gap are discussed above, the disclosed hyperplane search techniques can be applied to determine any suitable vehicle capabilities.

In this example, the AV management system800includes an AV802, a data center850, and a client computing device870. The AV802, the data center850, and the client computing device870may communicate with one another over one or more networks (not shown), such as a public network (e.g., the Internet, an Infrastructure as a Service (IaaS) network, a Platform as a Service (PaaS) network, a Software as a Service (SaaS) network, another Cloud Service Provider (CSP) network, etc.), a private network (e.g., a Local Area Network (LAN), a private cloud, a Virtual Private Network (VPN), etc.), and/or a hybrid network (e.g., a multi-cloud or hybrid cloud network, etc.).

AV802may navigate about roadways without a human driver based on sensor signals generated by multiple sensor systems804,806, and808. The sensor systems804-808may include different types of sensors and may be arranged about the AV802. For instance, the sensor systems804-808may comprise Inertial Measurement Units (IMUs), cameras (e.g., still image cameras, video cameras, etc.), light sensors (e.g., LIDAR systems, ambient light sensors, infrared sensors, etc.), RADAR systems, a Global Navigation Satellite System (GNSS) receiver, (e.g., Global Positioning System (GPS) receivers), audio sensors (e.g., microphones, Sound Navigation and Ranging (SONAR) systems, ultrasonic sensors, etc.), engine sensors, speedometers, tachometers, odometers, altimeters, tilt sensors, impact sensors, airbag sensors, seat occupancy sensors, open/closed door sensors, tire pressure sensors, rain sensors, and so forth. For example, the sensor system804may be a camera system, the sensor system806may be a LIDAR system, and the sensor system808may be a RADAR system. Other embodiments may include any other number and type of sensors.

AV802may also include several mechanical systems that may be used to maneuver or operate AV802. For instance, the mechanical systems may include vehicle propulsion system830, braking system832, steering system834, safety system836, and cabin system838, among other systems. Vehicle propulsion system830may include an electric motor, an internal combustion engine, or both. The braking system832may include an engine brake, a wheel braking system (e.g., a disc braking system that utilizes brake pads), hydraulics, actuators, and/or any other suitable componentry configured to assist in decelerating AV802. The steering system834may include suitable componentry configured to control the direction of movement of the AV802during navigation. Safety system836may include lights and signal indicators, a parking brake, airbags, and so forth. The cabin system838may include cabin temperature control systems, in-cabin entertainment systems, and so forth. In some embodiments, the AV802may not include human driver actuators (e.g., steering wheel, handbrake, foot brake pedal, foot accelerator pedal, turn signal lever, window wipers, etc.) for controlling the AV802. Instead, the cabin system838may include one or more client interfaces (e.g., Graphical User Interfaces (GUIs), Voice User Interfaces (VUIs), etc.) for controlling certain aspects of the mechanical systems830-838.

AV802may additionally include a local computing device810that is in communication with the sensor systems804-808, the mechanical systems830-838, the data center850, and the client computing device870, among other systems. The local computing device810may include one or more processors and memory, including instructions that may be executed by the one or more processors. The instructions may make up one or more software stacks or components responsible for controlling the AV802; communicating with the data center850, the client computing device870, and other systems; receiving inputs from riders, passengers, and other entities within the AV's environment; logging metrics collected by the sensor systems804-808; and so forth. In this example, the local computing device810includes a perception stack812, a mapping and localization stack814, a planning stack816, a control stack818, a communications stack820, an High Definition (HD) geospatial database822, and an AV operational database824, among other stacks and systems.

Perception stack812may enable the AV802to “see” (e.g., via cameras, LIDAR sensors, infrared sensors, etc.), “hear” (e.g., via microphones, ultrasonic sensors, RADAR, etc.), and “feel” (e.g., pressure sensors, force sensors, impact sensors, etc.) its environment using information from the sensor systems804-808, the mapping and localization stack814, the HD geospatial database822, other components of the AV, and other data sources (e.g., the data center850, the client computing device870, third-party data sources, etc.). The perception stack812may detect and classify objects and determine their current and predicted locations, speeds, directions, and the like. In addition, the perception stack812may determine the free space around the AV802(e.g., to maintain a safe distance from other objects, change lanes, park the AV, etc.). The perception stack812may also identify environmental uncertainties, such as where to look for moving objects, flag areas that may be obscured or blocked from view, and so forth.

Mapping and localization stack814may determine the AV's position and orientation (pose) using different methods from multiple systems (e.g., GPS, IMUs, cameras, LIDAR, RADAR, ultrasonic sensors, the HD geospatial database822, etc.). For example, in some embodiments, the AV802may compare sensor data captured in real-time by the sensor systems804-808to data in the HD geospatial database822to determine its precise (e.g., accurate to the order of a few centimeters or less) position and orientation. The AV802may focus its search based on sensor data from one or more first sensor systems (e.g., GPS) by matching sensor data from one or more second sensor systems (e.g., LIDAR). If the mapping and localization information from one system is unavailable, the AV802may use mapping and localization information from a redundant system and/or from remote data sources.

The planning stack816may determine how to maneuver or operate the AV802safely and efficiently in its environment. For example, the planning stack816may receive the location, speed, and direction of the AV802, geospatial data, data regarding objects sharing the road with the AV802(e.g., pedestrians, bicycles, vehicles, ambulances, buses, cable cars, trains, traffic lights, lanes, road markings, etc.) or certain events occurring during a trip (e.g., an Emergency Vehicle (EMV) blaring a siren, intersections, occluded areas, street closures for construction or street repairs, Double-Parked Vehicles (DPVs), etc.), traffic rules and other safety standards or practices for the road, user input, and other relevant data for directing the AV802from one point to another. The planning stack816may determine multiple sets of one or more mechanical operations that the AV802may perform (e.g., go straight at a specified speed or rate of acceleration, including maintaining the same speed or decelerating; turn on the left blinker, decelerate if the AV is above a threshold range for turning, and turn left; turn on the right blinker, accelerate if the AV is stopped or below the threshold range for turning, and turn right; decelerate until completely stopped and reverse; etc.), and select the best one to meet changing road conditions and events. If something unexpected happens, the planning stack816may select from multiple backup plans to carry out. For example, while preparing to change lanes to turn right at an intersection, another vehicle may aggressively cut into the destination lane, making the lane change unsafe. The planning stack816could have already determined an alternative plan for such an event, and upon its occurrence, help to direct the AV802to go around the block instead of blocking a current lane while waiting for an opening to change lanes.

The control stack818may manage the operation of the vehicle propulsion system830, the braking system832, the steering system834, the safety system836, and the cabin system838. The control stack818may receive sensor signals from the sensor systems804-808as well as communicate with other stacks or components of the local computing device810or a remote system (e.g., the data center850) to effectuate operation of the AV802. For example, the control stack818may implement the final path or actions from the multiple paths or actions provided by the planning stack816. Implementation may involve turning the routes and decisions from the planning stack816into commands for the actuators that control the AV's steering, throttle, brake, and drive unit.

The communication stack820may transmit and receive signals between the various stacks and other components of the AV802and between the AV802, the data center850, the client computing device870, and other remote systems. The communication stack820may enable the local computing device810to exchange information remotely over a network, such as through an antenna array or interface that may provide a metropolitan WIFI® network connection, a mobile or cellular network connection (e.g., Third Generation (3G), Fourth Generation (4G), Long-Term Evolution (LTE), 5th Generation (5G), etc.), and/or other wireless network connection (e.g., License Assisted Access (LAA), Citizens Broadband Radio Service (CBRS), MULTEFIRE, etc.). The communication stack820may also facilitate local exchange of information, such as through a wired connection (e.g., a user's mobile computing device docked in an in-car docking station or connected via Universal Serial Bus (USB), etc.) or a local wireless connection (e.g., Wireless Local Area Network (WLAN), Bluetooth®, infrared, etc.).

The AV operational database824may store raw AV data generated by the sensor systems804-808and other components of the AV802and/or data received by the AV802from remote systems (e.g., the data center850, the client computing device870, etc.). In some embodiments, the raw AV data may include HD LIDAR point cloud data, image or video data, RADAR data, GPS data, and other sensor data that the data center850may use for creating or updating AV geospatial data as discussed further below with respect toFIG.5and elsewhere in the present disclosure.

The data center850may be a private cloud (e.g., an enterprise network, a co-location provider network, etc.), a public cloud (e.g., an IaaS network, a PaaS network, a SaaS network, or other CSP network), a hybrid cloud, a multi-cloud, and so forth. The data center850may include one or more computing devices remote to the local computing device810for managing a fleet of AVs and AV-related services. For example, in addition to managing the AV802, the data center850may also support a ridesharing service, a delivery service, a remote/roadside assistance service, street services (e.g., street mapping, street patrol, street cleaning, street metering, parking reservation, etc.), and the like.

The data center850may send and receive various signals to and from the AV802and the client computing device870. These signals may include sensor data captured by the sensor systems804-808, roadside assistance requests, software updates, ridesharing pick-up and drop-off instructions, and so forth. In this example, the data center850includes one or more of a data management platform852, an Artificial Intelligence/Machine Learning (AI/ML) platform854, a simulation platform856, a remote assistance platform858, a ridesharing platform860, and a map management platform862, among other systems.

Data management platform852may be a “big data” system capable of receiving and transmitting data at high speeds (e.g., near real-time or real-time), processing a large variety of data, and storing large volumes of data (e.g., terabytes, petabytes, or more of data). The varieties of data may include data having different structures (e.g., structured, semi-structured, unstructured, etc.), data of different types (e.g., sensor data, mechanical system data, ridesharing service data, map data, audio data, video data, etc.), data associated with different types of data stores (e.g., relational databases, key-value stores, document databases, graph databases, column-family databases, data analytic stores, search engine databases, time series databases, object stores, file systems, etc.), data originating from different sources (e.g., AVs, enterprise systems, social networks, etc.), data having different rates of change (e.g., batch, streaming, etc.), or data having other heterogeneous characteristics. The various platforms and systems of the data center850may access data stored by the data management platform852to provide their respective services.

The AI/ML platform854may provide the infrastructure for training and evaluating machine learning algorithms for operating the AV802, the simulation platform856, the remote assistance platform858, the ridesharing platform860, the map management platform862, and other platforms and systems. Using the AI/ML platform854, data scientists may prepare data sets from the data management platform852; select, design, and train machine learning models; evaluate, refine, and deploy the models; maintain, monitor, and retrain the models; and so on.

The simulation platform856may enable testing and validation of the algorithms, machine learning models, neural networks, and other development efforts for the AV802, the remote assistance platform858, the ridesharing platform860, the map management platform862, and other platforms and systems. The simulation platform856may replicate a variety of driving environments and/or reproduce real-world scenarios from data captured by the AV802, including rendering geospatial information and road infrastructure (e.g., streets, lanes, crosswalks, traffic lights, stop signs, etc.) obtained from the map management platform862; modeling the behavior of other vehicles, bicycles, pedestrians, and other dynamic elements; simulating inclement weather conditions, different traffic scenarios; and so on. In some embodiments, the simulation platform856may include an AV tester857(e.g., similar the AV capability tester120) that searches and defines AV capabilities using a finite parameter space with hyperplane searches as discussed herein.

The remote assistance platform858may generate and transmit instructions regarding the operation of the AV802. For example, in response to an output of the AI/ML platform854or other system of the data center850, the remote assistance platform858may prepare instructions for one or more stacks or other components of the AV802.

The ridesharing platform860may interact with a customer of a ridesharing service via a ridesharing application872executing on the client computing device870. The client computing device870may be any type of computing system, including a server, desktop computer, laptop, tablet, smartphone, smart wearable device (e.g., smart watch; smart eyeglasses or other Head-Mounted Display (HMD); smart ear pods or other smart in-ear, on-ear, or over-ear device; etc.), gaming system, or other general purpose computing device for accessing the ridesharing application872. The client computing device870may be a customer's mobile computing device or a computing device integrated with the AV802(e.g., the local computing device810). The ridesharing platform860may receive requests to be picked up or dropped off from the ridesharing application872and dispatch the AV802for the trip.

In some embodiments, the map viewing services of map management platform862may be modularized and deployed as part of one or more of the platforms and systems of the data center850. For example, the AI/ML platform854may incorporate the map viewing services for visualizing the effectiveness of various object detection or object classification models, the simulation platform856may incorporate the map viewing services for recreating and visualizing certain driving scenarios, the remote assistance platform858may incorporate the map viewing services for replaying traffic incidents to facilitate and coordinate aid, the ridesharing platform860may incorporate the map viewing services into the client application872to enable passengers to view the AV802in transit en route to a pick-up or drop-off location, and so on.

FIG.9illustrates an example processor-based system with which some aspects of the subject technology may be implemented. For example, processor-based system900may be any computing device making up, or any component thereof in which the components of the system are in communication with each other using connection905. Connection905may be a physical connection via a bus, or a direct connection into processor910, such as in a chipset architecture. Connection905may also be a virtual connection, networked connection, or logical connection.

In some embodiments, computing system900is a distributed system in which the functions described in this disclosure may be distributed within a datacenter, multiple data centers, a peer network, etc. In some embodiments, one or more of the described system components represents many such components each performing some or all of the function for which the component is described. In some embodiments, the components may be physical or virtual devices.

Example system900includes at least one processing unit (Central Processing Unit (CPU) or processor)910and connection905that couples various system components including system memory915, such as Read-Only Memory (ROM)920and Random-Access Memory (RAM)925to processor910. Computing system900may include a cache of high-speed memory912connected directly with, in close proximity to, or integrated as part of processor910.

Processor910may include any general-purpose processor and a hardware service or software service, such as an AV capability testing service932stored in storage device930, configured to control processor910as well as a special-purpose processor where software instructions are incorporated into the actual processor design. The AV capability test service932may search and define AV capabilities using a finite parameter space with hyperplane searches as discussed herein.

Processor910may essentially be a completely self-contained computing system, containing multiple cores or processors, a bus, memory controller, cache, etc. A multi-core processor may be symmetric or asymmetric.

To enable user interaction, computing system900includes an input device945, which may represent any number of input mechanisms, such as a microphone for speech, a touch-sensitive screen for gesture or graphical input, keyboard, mouse, motion input, speech, etc. Computing system900may also include output device935, which may be one or more of a number of output mechanisms known to those of skill in the art. In some instances, multimodal systems may enable a user to provide multiple types of input/output to communicate with computing system900. Computing system900may include communications interface940, which may generally govern and manage the user input and system output. The communication interface may perform or facilitate receipt and/or transmission wired or wireless communications via wired and/or wireless transceivers, including those making use of an audio jack/plug, a microphone jack/plug, a Universal Serial Bus (USB) port/plug, an Apple® Lightning® port/plug, an Ethernet port/plug, a fiber optic port/plug, a proprietary wired port/plug, a BLUETOOTH® wireless signal transfer, a BLUETOOTH® low energy (BLE) wireless signal transfer, an IBEACON® wireless signal transfer, a Radio-Frequency Identification (RFID) wireless signal transfer, Near-Field Communications (NFC) wireless signal transfer, Dedicated Short Range Communication (DSRC) wireless signal transfer, 802.11 Wi-Fi® wireless signal transfer, Wireless Local Area Network (WLAN) signal transfer, Visible Light Communication (VLC) signal transfer, Worldwide Interoperability for Microwave Access (WiMAX), Infrared (IR) communication wireless signal transfer, Public Switched Telephone Network (PSTN) signal transfer, Integrated Services Digital Network (ISDN) signal transfer, 3G/4G/5G/LTE cellular data network wireless signal transfer, ad-hoc network signal transfer, radio wave signal transfer, microwave signal transfer, infrared signal transfer, visible light signal transfer signal transfer, ultraviolet light signal transfer, wireless signal transfer along the electromagnetic spectrum, or some combination thereof.

Storage device930may include software services, servers, services, etc., that when the code that defines such software is executed by the processor910, it causes the system900to perform a function. In some embodiments, a hardware service that performs a particular function may include the software component stored in a computer-readable medium in connection with the necessary hardware components, such as processor910, connection905, output device935, etc., to carry out the function.

Selected Examples

Example 1 includes a computer-implemented system, including one or more non-transitory computer-readable media storing instructions, when executed by one or more processing units, cause the one or more processing units to perform operations including generating a first plurality of vehicle test scenarios, each corresponding to one of a first plurality of sampling points in an N-dimensional parameter space associated with a vehicle capability, where N is a positive integer; executing a vehicle compute process in each vehicle test scenario of the first plurality of vehicle test scenarios to generate a first test result for each respective vehicle test scenario; computing, based on the first test results, a first hyperplane in the N-dimensional parameter space; and generating, based on the first hyperplane, a second plurality of vehicle test scenarios, each corresponding to one of a second plurality of sampling points in the N-dimensional parameter space.

In Example 2, the computer-implemented system of Example 1 can optionally include where the first plurality of sampling points are non-uniformly spaced in the N-dimensional parameter space.

In Example 3, the computer-implemented system of any one of Examples 1-2 can optionally include where the first hyperplane separates the first plurality of sampling points into a first group of sampling points corresponding to test vehicle scenarios in which the vehicle compute process fails; and a second group of sampling points corresponding to test vehicle scenarios in which the vehicle compute process passes.

In Example 4, the computer-implemented system of any one of Examples 1-3 can optionally include where the generating the second plurality of vehicle test scenarios includes selecting, based on the first hyperplane, the second plurality of sampling points in the N-dimensional parameter space.

In Example 5, the computer-implemented system of any one of Examples 1˜4 can optionally include where the selecting the second plurality of sampling points includes selecting the second plurality of sampling points in a subspace of the N-dimensional parameter space, the subspace being on one side of the first hyperplane.

In Example 6, the computer-implemented system of any one of Examples 1-5 can optionally include where each of the second plurality of sampling points has a shorter distance to the first hyperplane than each of the first plurality of sampling points.

In Example 7, the computer-implemented system of any one of Examples 1-6 can optionally include where the generating the first plurality of vehicle test scenarios includes configuring one or more test parameters for a first vehicle test scenario of the first plurality of vehicle test scenarios based on a first sampling point of the first plurality of sampling points in the N-dimensional parameter space.

In Example 8, the computer-implemented system of any one of Examples 1-7 can optionally include where the computing the first hyperplane is further based on a support vector machine (SVM).

In Example 9, the computer-implemented system of any one of Examples 1-8 can optionally include executing the vehicle compute process in each vehicle test scenario of the second plurality of vehicle test scenarios to generate a second test result for each respective vehicle test scenario; computing, based on the first test results and the second test results, a second hyperplane in the N-dimensional parameter space; and determining, based on the second hyperplane, a capability of the vehicle.

In Example 10, the computer-implemented system of any one of Examples 1-9 can optionally include where a value of N for the N-dimensional parameter space is at least 2.

Example 11 includes a method including selecting, by a computer-implemented system, a first plurality of sampling points in an N-dimensional parameter space associated with a vehicle capability test; classifying, by the computer-implemented system, each sampling point of the first plurality of sampling points into a first class based on a vehicle passing a test scenario associated with the respective sampling point; or a second class based on the vehicle failing the test scenario associated with the respective sampling point; and determining, by the computer-implemented system based on the classifying, a capability of the vehicle.

In Example 12, the method of Example 11 can optionally include where the selecting the first plurality of sampling points is based on a random selection in the N-dimensional parameter space.

In Example 13, the method of any one of Examples 11-12 can optionally include where the selecting the first plurality of sampling points is based on a threshold number of test scenarios.

In Example 14, the method of any one of Examples 11-13 can optionally include configuring, by the computer-implemented system, one or more test parameters for a first test scenario based on a first sampling point of the first plurality of sampling points.

In Example 15, the method of any one of Examples 11-14 can optionally include where the classifying each sampling point of the first plurality of sampling points into the first class or the second class is based on a stochastic gradient descent (SGD) classifier.

In Example 16, the method of any one of Examples 11-15 can optionally include where the classifying each sampling point of the first plurality of sampling points includes computing a first hyperplane in the N-dimensional parameter space, where the first hyperplane separates the first plurality of sampling points into the first class and the second class.

In Example 17, the method of any one of Examples 11-16 can optionally include where the computing the first hyperplane in the N-dimensional parameter space is based on a support vector machine (SVM).

In Example 18, the method of any one of Examples 11-17 can optionally include where the selecting the first plurality of sampling points is based on a second hyperplane in the N-dimensional parameter space, the second hyperplane being different from the first hyperplane.

In Example 19, the method of any one of Examples 11-18 can optionally include where the second hyperplane separates a second plurality of sampling points in the N-dimensional parameter space into the first class and the second class.

In Example 20, the method of any one of Examples 11-19 can optionally include terminating, by the computer-implemented system, the vehicle capability test based on a comparison between the first hyperplane and the second hyperplane.

In Example 21, the method of any one of Examples 11-20 can optionally include terminating, by the computer-implemented system, the vehicle capability test based on a difference between a first weight associated with the first hyperplane and a second weight associated with the second hyperplane satisfying a threshold.

In Example 22, the method of any one of Examples 11-21 can optionally include where the determining the capability of the vehicle based on the first hyperplane is responsive to a difference between the first hyperplane and the second hyperplane satisfying a threshold.

In Example 23, the method of any one of Examples 11-22 can optionally include where the N-dimensional parameter space includes dimensions associated with at least one of a vehicle position or a lane boundary.

In Example 24, the method of any one of Examples 11-23 can optionally include where the N-dimensional parameter space is associated with at least one of a path curvature or a distance from the vehicle to the path curvature; and the capability of the vehicle is associated with a navigable path curvature.

In Example 25, the method of any one of Examples 11-24 can optionally include where the N-dimensional parameter space is associated with at least one of a width of a gap, a lateral distance from the vehicle to the gap, or a longitudinal distance from the vehicle to the gap; and the capability of the vehicle is associated with a navigable gap size.

Example 26 includes a method including generating, by a computer-implemented system, a first plurality of vehicle test scenarios, each corresponding to one of a first plurality of sampling points in a multi-dimensional parameter space, the multi-dimensional parameter space having dimensions associated with at least one of a vehicle position or a lane boundary; executing, by the computer-implemented system, a vehicle compute process in each vehicle test scenario of the first plurality of vehicle test scenarios to generate a first test result for each respective vehicle test scenario; computing, by the computer-implemented system based on the first test results, a first hyperplane within the multi-dimensional parameter space; and generating, by the computer-implemented system based on the first hyperplane, a second plurality of vehicle test scenarios, each corresponding to one of a second plurality of sampling points in the multi-dimensional parameter space.

In Example 27, the method of Example 26, where the first hyperplane separates the first plurality of sampling points into a first group of sampling points corresponding to vehicle test scenarios in which the vehicle compute process fails; and a second group of sampling points corresponding to vehicle test scenarios in which the vehicle compute process passes.

In Example 28, the method of any one of Examples 26-27 can optionally include where the generating the second plurality of vehicle test scenarios includes selecting, based on the first hyperplane, the second plurality of sampling points in the multi-dimensional parameter space.

In Example 29, the method of any one of Examples 26-28 can optionally include executing the vehicle compute process in each vehicle test scenario of the second plurality of vehicle test scenarios to generate a second test result for each respective vehicle test scenario; computing, based on the first test results and the second test results, a second hyperplane in the multi-dimensional parameter space; and determining, based on the second hyperplane, a vehicle capability.

Example 30 includes an apparatus comprising means for performing the method of any of the examples 11-25.

Example 31 includes an apparatus comprising means for performing the method of any of the examples 26-29.