System and Method for Controlling an Operation of a System Subject to an Uncertainty

The present disclosure discloses a system and a method for controlling an operation of a system subject to an uncertainty of an operation variable of the system. The method comprises collecting a number of samples of the uncertainty of the operation variable, constructing, based on the collected samples, an empirical quantile function associated with the uncertainty of the operation variable, determining confidence bounds on the empirical quantile function to bound an approximation error between the empirical quantile function and a true quantile function, determining an uncertainty set based on the empirical quantile function bounded by the confidence bounds, reformulating, based on the uncertainty set, a chance constraint into a deterministic constraint, solving an optimal control problem subject to the deterministic constraint to produce one or more control commands to one or more actuators of the system, and controlling the operation of the system based on the control commands.

TECHNICAL FIELD

The present disclosure relates generally to control systems, and more particularly to a system and a method for controlling an operation of a system subject to an uncertainty of an operation variable of the system.

BACKGROUND

Motion planning for an autonomous device (e.g., autonomous vehicle) uses optimization to deal with a task of minimizing a performance metric subject to constraints arising from dynamics, actuator limitations, and environmental limitations. The autonomous device faces uncertainty from physics of the autonomous device and environment, sensor limitations, and simplifications to the utilized mathematical models for the sake of tractability. Optimization under the uncertainty is handled using a chance-constrained optimization method. In the chance-constrained optimization method, the uncertainty in the optimization is accounted by that the constraints be satisfied with a certain probability, i.e., by formulating chance constraints that allow for a specified, yet non-zero, probability of constraint violation. However, the chance constraints are computationally intractable and require an approximate formulation.

To mitigate such a problem, the chance-constrained optimization method is reformulated as a deterministic optimization method having deterministic constraints guaranteeing the satisfaction of the chance constraints. To achieve such a reformulation, some approaches assume structure on the uncertainty or a constraint set f≤0. For example, the uncertainty is assumed to be Gaussian and a constraint set is a hyperplane, or the uncertainty has known mean and covariance and the constraint set is affine in the uncertainty. Such reformulations are often conservative in practice.

Further, data-driven approaches for the reformulation use a notion of scenarios and pose the chance constraint as a collection of a finite number of constraints evaluated at data points available for the uncertainty. However, the data-driven approaches require a convex f, restricting a class of functions of considered. Alternatively, the data-driven approaches utilize a mixed-integer formulation that can cause severe numerical challenges in implementation, or solve a collection of separate scenario problems that require significant computational resources.

Therefore, there is a need for a system and method for solving a chance constrained optimization problem to optimize the motion trajectory for the autonomous device subject to the uncertainty, where the uncertainty is unknown.

SUMMARY

It is an objective of some embodiments to solve a chance constrained optimization problem using data and without relying on any structural assumptions on the uncertainty. In particular, it is an objective of some embodiments to solve a constrained optimization problem to optimize a motion trajectory under constraints for a system subject to uncertainty, where the uncertainty is unknown and is estimated using data collected during present and possibly past operation of the device.

Examples of the system include autonomous ground vehicles, such as cars or robots in factory automation, an aircraft on airport surfaces, and unmanned aerial vehicles such as drones for infrastructure monitoring or inspections. Examples of the constraints include steering the system to always stay within operation bounds, steering the system to eventually reach a desired region, and keeping a safe distance from obstacles in an environment. The uncertainty in these applications arise from uncertainty due to unmodelled phenomena in the environment and mathematical models used during control, e.g., friction effects on the autonomous ground vehicles and wind effects on flight of the unmanned aerial vehicles. Additionally, the uncertainty can also arise from limitations of sensors in sensing the environment.

According to an embodiment, a chance constraint may be given asw{f(z, w)≤a} ≥ δ. Here, f encodes the constraint that a decision variable z must lie outside a set f(z, w)≤0. However, w is an unknown uncertainty whose value is not known, therefore a value of the decision variable z is chosen such that a likelihood of satisfaction of the constraint f(z, w)≤0 is above a user-specified risk threshold 8 (say 0.999). Existing literature enforces the chance constraintw{f(z, w)≤a} ≥ 8 by utilizing distribution or moments (mean and covariance) of w to approximate a likelihood of a chosen value of the decision variable z satisfies the constraint f(z, w)≤0. Some embodiments are based on the realization that the chance constraint can be enforced using samples of w and without requiring prior knowledge of the distribution or the moments of w. Some embodiments are based on the realization that the chance constraint can be decomposed into requiring that the uncertainty lie in a particular uncertainty set independent of the decision variable, and then the decision variable is optimized while maintaining constraint satisfaction for all values of the uncertainty in the uncertainty set. The uncertainty set can be determined using empirical quantile functions for the user-specified risk threshold δ, and computation of the decision variable while maintaining constraint satisfaction for all values of the uncertainty can be achieved via a robust optimization. Hence, the embodiments of the present disclosure are based on the realization that a combination of the empirical quantile functions and the robust optimization can compute optimal motion trajectories for the system subject to the uncertainty, where the uncertainty is unknown and can be estimated using the data collected during the present and/or possibly past operation of the system. Such an approach is described below.

For the purpose of the explanation, a vehicle is considered to be the system subject to uncertainty. The vehicle may be an autonomous vehicle or a semi-autonomous vehicle. At first, a number of samples of an uncertainty of an operation variable of the vehicle are collected. For instance, in collision avoidance example, the operation variable of the vehicle may correspond to a bounding box position around an obstacle and a number of samples of uncertainty in the bounding box position are collected.

Further, based on the collected samples, an empirical quantile function associated with the uncertainty of the operation variable is constructed. The quantile function is an inverse of a cumulative distribution function. The cumulative distribution function of a real-valued random variable w, denoted by @w(w), is a probability that w will take a value less than or equal to w. The empirical quantile function approximates a true quantile function of the uncertainty w, since the true quantile function is not available to a user. However, the quantile functions approximated using the samples are noisy. To mitigate such a problem, some embodiments use a property of the quantile functions that enable finite samples guarantee on a quality of approximation.

To that end, confidence bounds on the empirical quantile function are determined to bound an approximation error between the empirical quantile function and the true quantile function. In an embodiment, Dvoretzky-Kiefer-Wolfowitz-Massart inequality is used to bound the approximation error between the empirical quantile function and the true quantile function using only a finite number of samples. Further, based on the empirical quantile function bounded by the confidence bounds and the user-specified risk threshold δ, an uncertainty set ε is computed. The uncertainty set E includes a subset of values attainable by the uncertainty w.

Further, using the uncertainty set ε, the chance constraint is reformulated into a deterministic constraint max∈εf(z, w)≤0. Some embodiments are based on the recognition that any value of the decision variable that satisfies deterministic constraint max∈εf(z, w)≤0 satisfies the chance constraintw{f(z, w)≤a}≥δ. In the deterministic constraint max∈εf(z, w)≤0, the maximization operation encodes a requirement that all uncertainty values within the uncertainty set ε must satisfy the constraint f(z, w)≤0. Additionally, the deterministic constraint max∈εf(z, w)≤0 does not impose any structure or assumptions on the uncertainty w or constraint function f.

Additionally, in some embodiments, the deterministic constraint max∈εf(z, w)≤0 is equivalently expressed as g(z)=max∈εf(z, w)≤0, which can be easily implemented in standard off-the-shelf optimization solvers and provides guarantees of satisfaction of the chance constraint. Additionally, g(z) is known to be convex when f is convex in z for every value of w∈ε and ε is convex. Convexity of g(z) provides numerical and theoretical benefits when enforcing (1) in an optimal control problem.

Further, an optimal control problem subject to the deterministic constraint is solved to produce one or more control commands to one or more actuators of the vehicle, such as a steering wheel and/or brakes of the vehicle. Furthermore, the vehicle is controlled based on the control commands to the one or more actuators.

Accordingly, one embodiment discloses a controller for controlling an operation of a system subject to an uncertainty of an operation variable of the system. The controller comprises at least one processor; and a non-transitory memory having instructions stored thereon that, when executed by the at least one processor, cause the feedback controller to: collect a number of samples of the uncertainty of the operation variable; construct, based on the collected samples, an empirical quantile function associated with the uncertainty of the operation variable; determine confidence bounds on the empirical quantile function to bound an approximation error between the empirical quantile function and a true quantile function; determine an uncertainty set based on the empirical quantile function bounded by the confidence bounds and a user-specified risk threshold; reformulate, based on the uncertainty set, a chance constraint into a deterministic constraint; solve an optimal control problem subject to the deterministic constraint to produce one or more control commands to one or more actuators of the system; and control the operation of the system based on the control commands to the one or more actuators of the system.

Accordingly, another embodiment discloses a method for controlling an operation of a system subject to an uncertainty of an operation variable of the system. The method comprises collecting a number of samples of the uncertainty of the operation variable; constructing, based on the collected samples, an empirical quantile function associated with the uncertainty of the operation variable; determining confidence bounds on the empirical quantile function to bound an approximation error between the empirical quantile function and a true quantile function; determining an uncertainty set based on the empirical quantile function bounded by the confidence bounds and a user-specified risk threshold; reformulating, based on the uncertainty set, a chance constraint into a deterministic constraint; solving an optimal control problem subject to the deterministic constraint to produce one or more control commands to one or more actuators of the system; and controlling the operation of the system based on the control commands to the one or more actuators of the system.

Accordingly, yet another embodiment discloses a non-transitory computer-readable storage medium embodied thereon a program executable by a processor for performing a method for controlling an operation of a system subject to an uncertainty of an operation variable of the system. The method comprises collecting a number of samples of the uncertainty of the operation variable; constructing, based on the collected samples, an empirical quantile function associated with the uncertainty of the operation variable; determining confidence bounds on the empirical quantile function to bound an approximation error between the empirical quantile function and a true quantile function; determining an uncertainty set based on the empirical quantile function bounded by the confidence bounds and a user-specified risk threshold; reformulating, based on the uncertainty set, a chance constraint into a deterministic constraint; solving an optimal control problem subject to the deterministic constraint to produce one or more control commands to one or more actuators of the system; and controlling the operation of the system based on the control commands to the one or more actuators of the system.

The presently disclosed embodiments will be further explained with reference to the attached drawings. The drawings shown are not necessarily to scale, with emphasis instead generally being placed upon illustrating the principles of the presently disclosed embodiments.

DETAILED DESCRIPTION

As used in this specification and claims, the terms “for example,” “for instance,” and “such as,” and the verbs “comprising,” “having,” “including,” and their other verb forms, when used in conjunction with a listing of one or more components or other items, are each to be construed as open ended, meaning that that the listing is not to be considered as excluding other, additional components or items. The term “based on” means at least partially based on. Further, it is to be understood that the phraseology and terminology employed herein are for the purpose of the description and should not be regarded as limiting. Any heading utilized within this description is for convenience only and has no legal or limiting effect.

FIG.1Ashows a block diagram100of a method for controlling a system, according to some embodiments of the present disclosure. Examples of the system include autonomous ground vehicles, such as cars or robots in factory automation, an aircraft on airport surfaces, and unmanned aerial vehicles such as drones for infrastructure monitoring or inspections. For the purpose of the explanation, a vehicle is considered to be the system that has to be controlled. The vehicle may be an autonomous vehicle or a semi-autonomous vehicle. The vehicle may be subject to uncertainty. The uncertainty may arise due to unmodelled phenomena in an environment in which the vehicle is operated and mathematical models used during control, e.g., friction effects on the vehicles. Additionally, the uncertainty can also arise from limitations of sensors in sensing the environment. The uncertainty arising in an autonomous driving scenario of the vehicle is explained below inFIG.1B.

FIG.1Billustrates a typical autonomous driving scenario115, according to some embodiments of the present disclosure. A vehicle117to be controlled is moving on a road119. The vehicle117is communicatively coupled to a controller. In some embodiments, the controller is embedded into the vehicle117. In addition to the vehicle117, multiple uncontrolled cars, such as, a car121aand a car121b(which are collectively referred to hereinafter as the multiple uncontrolled cars121aand121b), are moving on the road119. The multiple uncontrolled cars121aand121bact as moving obstacles for the vehicle117. Further, a foreign object, e.g., a large stone121cacts as a static obstacle for the vehicle117. Hereinafter, the multiple uncontrolled cars121aand121b, and the large stone121care collectively referred to as the obstacles121a,121b, and121c.

The vehicle117may include sensors to sense surrounding environment. Examples of the sensors include distance range finders, radars, lidars, and cameras. Additionally, the vehicle117may include sensors, such as, global positioning system (GPS), accelerometers, inertial measurement units, gyroscopes, shaft rotational sensors, torque sensors, deflection sensors, pressure sensor, and flow sensors, to sense its current motion quantities and internal status.

The controller collects data from the sensors of the vehicle117and determines bounding boxes, such as a bounding box123a, a bounding box123b, and a bounding box123c(which are collectively referred to hereinafter as the bounding boxes123a,123b, and123c), around the obstacles121a,121b, and121c, respectively, based on the collected data. Further, a motion trajectory125afor the vehicle117may be determined based on the bounding boxes123a,123b, and123c. However, due to sensing limitations of the sensors and processing limitations, the bounding boxes123a,123b, and123cmay not always be correct. For example, the bounding box123apartially lies outside the vehicle121a. Since the bounding boxes123a,123b, and123cmay be incorrect, the motion trajectory125ais susceptible to collision with any of the obstacles121a,121b, and121c. To that end, it is desirable to determine a motion trajectory125bthat provides sufficient margins from the obstacles121a,121b, and121c, accounting for uncertainty of the bounding boxes123a,123b, and123c.

Further, in some embodiments, the operation of the vehicle117is subject to constraints, for example, drive the vehicle117within speed limits. Due to unpredictability of conditions of the road119, it is not practical to drive the vehicle117at the speed limit. The speed limits may be violated due to uncertainty in friction of tires of the vehicle117.

According to some embodiments, the constraints under uncertainty can be cast as a chance constraint, i.e., a constraint which must hold with likelihood greater than a user-specified risk threshold. For example, the chance constraint may be given as

Here, function f encodes the constraint that a decision variable z must lie outside a set f(z, w)≤0. However, w is an unknown uncertainty whose value is not known, therefore a value of the decision variable z is chosen such that a likelihood of satisfaction of the constraint f(z, w)≤0 is above a user-specified risk threshold δ (say 0.999). In other words, the chance constraint constraints a probability of a nonlinear function (e.g., function f) of the decision variable be non-positive with a user-specified risk threshold δ. The nonlinear function is one of a non-convex and a polynomial.

As an example, consider a constraint that the vehicle117should not collide with the vehicle121ais written in the form of (1). Here, an uncertainty is associated with a two-dimensional position of the bounding box123a. Specifically, the bounding box123aaround the vehicle121ais uncertain. For the collision avoidance constraint of the form (1), z is a two-dimensional position of the vehicle117in (x, y)-coordinate system, w is a two-dimensional position of the bounding box123ain (x, y)-coordinate system, and

is a constraint which is positive if and only if position of the vehicle117does not lie in the bounding box123a. Here, Z1is the position of the vehicle117in x-coordinate, Z2is the position of the vehicle117in y-coordinate, a1is a length of the bounding box along the x-coordinate, and a2is a length of the bounding box along the y-coordinate.

However, incorporating the constraints of the form (1) in an optimal control problem is challenging as the chance constraints are computationally intractable and require an approximate formulation. Existing literature enforces the chance constraint Pw{f(z, w)≤a} ≥ δ by utilizing distribution or moments (mean and covariance) of w to approximate a likelihood of a chosen value of the decision variable z satisfies the constraint f(z, w)≤0. Some embodiments are based on the realization that the chance constraint can be enforced using samples of w and without requiring prior knowledge of the distribution or the moments of w. Some embodiments are based on the realization that the chance constraint can be decomposed into requiring that the uncertainty lie in a particular uncertainty set independent of the decision variable, and then the decision variable is optimized while maintaining constraint satisfaction for all values of the uncertainty in the uncertainty set. The uncertainty set can be determined using empirical quantile functions bounded by confidence bounds and the user-specified risk threshold δ, and the computation of the decision variable while maintaining constraint satisfaction for all values of the uncertainty in the uncertainty set can be achieved via a robust optimization.

Hence, the embodiments of the present disclosure are based on the realization that a combination of the empirical quantile functions and the robust optimization can compute optimal motion trajectories for the vehicle117subject to the uncertainty, where the uncertainty is unknown and can be estimated using the data collected during the present and/or possibly past operation of the vehicle117. Such an approach is described below with reference toFIG.1A.

Referring toFIG.1A, at block101, a number of samples of an uncertainty of an operation variable of the vehicle117is collected. For instance, in collision avoidance example, a number of samples of uncertainty in the bounding box position is collected. The samples may be determined offline (i.e., before real-time operation) or during real-time control of the vehicle117.

The quantile function Qwis the inverse of a cumulative distribution function. The cumulative distribution function of a real-valued random variable w, denoted by Φw(v), is a probability that w takes a value less than or equal to v.

At block103, based on the collected samples, an empirical quantile function associated with the uncertainty of the operation variable is constructed. Given a set of M data samples={wsample(1), wsample(2), . . . wsample(3)}, the empirical quantile function associated with the uncertainty w can be given as

where {circumflex over (Φ)}wM(w) is an empirical cumulative distribution of the uncertainty w,

and{wsample(j)≤w}=1 when wsample(j)≤w, and zero otherwise.

The empirical quantile function (2) approximates a true quantile function Qwof the uncertainty w, since Qwis not available to the user.

FIG.1Cillustrates true probability density functions (such as, a true probability density function127and a true probability density function129), true cumulative distributions (such as, a true cumulative distribution131and a true cumulative distributions133), true quantile distributions (such as, a true cumulative distributions135and a true cumulative distributions137), along with their empirical counterparts constructed using a finite set of samples for two distributions, namely, a symmetric triangular distribution and a Gaussian random variable. The symmetric triangular distribution has a support of [−1, 1] as can be observed from the true probability density function127and the true cumulative distribution131, while the Gaussian random variable has a support of an entire real line as can be observed from the true probability density function129and the true cumulative distribution133.

A dotted line131aand a dotted line133arepresent empirical cumulative distributions, and a dotted line135aand a dotted line137arepresent empirical quantile functions constructed using (2) and (3) with the collected samples. It can be observed fromFIG.1Cthat a domain of the true probability density function, the true cumulative distribution, and the empirical cumulative distribution match the support of the uncertainty. Ranges of the true cumulative distribution and the empirical cumulative distribution functions match and are equal to [0, 1]. On the other hand, a domain of the true quantile function and the empirical quantile function (e.g., empirical quantile function represented by the dotted line137a) match and are equal to [0,1]. The ranges of the true quantile function and the empirical quantile function match the support of the uncertainty.

However, the quantile functions approximated using the samples are noisy. To mitigate such a problem, some embodiments use a property of the quantile functions that enable finite samples guarantee on a quality of approximation.

To that end, referring toFIG.1A, at block105, confidence bounds on the empirical quantile function to bound an approximation error between the empirical quantile function and the true quantile function, are determined. In an embodiment, Dvoretzky-Kiefer-Wolfowitz-Massart inequality is used to bound the approximation error between the empirical quantile function and the true quantile function using only a finite number of samples. Specifically, the empirical quantile function associated with the uncertainty w, when defined using a set of M samples={wsample(1), wsample(2), . . . wsample(3)} sample has the following approximation guarantee:

Equation (4) implies that for all possible values of the uncertainty w, the maximum deviation between the true quantile function Qw(p) and the empirical quantile function {circumflex over (Q)}wM(p) is bounded from above by e with a high probability as M increases, where M is the number of samples used to construct the empirical quantile function {circumflex over (Q)}wM. Right hand side (RHS) of (4) shrinks to zero as M increases implying that a probability of an event |Qw(p)−{circumflex over (Q)}wM(p)>∈ vanishes as M increases.

Given a small probability of failure β, it is observed that RHS of (4) is smaller than β when

Consequently, the confidence bounds on the unknown quantile function Qware determined using the empirical quantile function {circumflex over (Q)}wM, as

where (5) holds with probability 1−β for any choice of sample count M>0. Equation (5) shows that high-probability confidence bounds can be constructed around the true quantile function Qwusing the empirical quantile function {circumflex over (Q)}wM.

FIG.1Dillustrates a confidence bound135band a confidence bound135con the empirical quantile function135a, and a confidence bound137band a confidence bound137con the empirical quantile function137afor M=50 and M=1000 samples, respectively, according to some embodiments of the present disclosure. It is evident fromFIG.1Dthat the confidence bounds tighten when the number of samples M is high.

Referring back toFIG.1A, at block107, an uncertainty set & is determined based on the empirical quantile function bounded by the confidence bounds and the user-specified risk threshold δ, such that probability{w∈ε}≥δ. The uncertainty set ε includes a subset of values attainable by the uncertainty w. When the uncertainty set ε covers the entire set of values attainable by the uncertainty w,{w∈ε}=1.

At block109, using the uncertainty set ε, the chance constraint (1) is reformulated into a deterministic constraint

Some embodiments are based on the recognition that any value of the decision variable that satisfies (6) satisfies the chance constraint (1). In (6), the maximization operation encodes a requirement that all uncertainty values within the uncertainty set ε must satisfy the constraint f(z, w)≤0. Additionally, (6) does not impose any structure or assumptions on the uncertainty w or constraint function f.

However, chance constrained optimization problems where the chance constraints are replaced with deterministic constraints of the form (6) lead to a bilevel optimization problem, and are typically hard to solve. The bilevel optimization problems are optimization problems where the constraints themselves involve solving one or more optimization problems.

Some embodiments are based on the observation that for some special cases of the constraint function f and the uncertainty set ε, (6) can be equivalently expressed as

Unlike with (6), optimization problems with deterministic constraints of the form (7) can be easily implemented in standard off-the-shelf solvers and provides guarantees of satisfaction of the chance constraint (1). Additionally, g in (7) is known to be convex when f is convex in z for every value of w∈ε and ε is convex. Convexity of g in (7) provides numerical and theoretical benefits when enforcing (1) in an optimal control problem.

At block111, an optimal control problem subject to the deterministic constraint (6) or (7) is solved to produce one or more control commands to one or more actuators of the vehicle117, such as a steering wheel and/or brakes of the vehicle117. At block113, the operation of the vehicle117is controlled based on the control commands to the one or more actuators.

The steps (101-113) described in the block diagram100for controlling the operation of the vehicle117are executed by a controller.FIG.1Eshows a block diagram of a controller139for controlling the operation of the vehicle117, according to some embodiments of the present disclosure. The controller139includes a processor141and a memory143. The processor141may be a single core processor, a multi-core processor, a computing cluster, or any number of other configurations. The memory143may include random access memory (RAM), read only memory (ROM), flash memory, or any other suitable memory systems. Additionally, in some embodiments, the memory143may be implemented using a hard drive, an optical drive, a thumb drive, an array of drives, or any combinations thereof.

FIG.2illustrates a relationship between sets of values for the decision variables z that satisfy the chance constraint (1) and the deterministic constraint (6), according to some embodiments of the present disclosure. Here, a set201denotes a set of values for the decision variable z that satisfies chance constraint (1). Since the uncertainty is unknown, the set201is unknown. However, using the data-driven approach described inFIG.1C, a tighter set203that is a strict subset of the set201can be determined. Formally, every value of the decision variable that belongs to the tighter set203also belongs to the set201, i.e., every value of the decision variable that satisfies (6) also satisfies (1).

According to an embodiment, the chance constraint (1), when linear in w, can be reformulated into the deterministic constraint (6) using half-spaces. Consider an example of driving the vehicle117to stay within a speed limit. Here, the chance constraint (1) where f has a specific form,

Here, the decision variable z, may be a collection of thrust output of engine of the vehicle117, steering angle, and the like, V(z) describes the estimated speed of the vehicle117as a known nonlinear transformation of the decision variable z, and the uncertainty w is a difference between an estimated speed of the vehicle117and a true speed of the vehicle117. Here, w is a complex object whose uncertainty distribution is difficult to obtain in practice.

Some embodiments are based on the realization that data on w can be collected separately. For example, by driving the vehicle117on a test track equipped with a speed estimator like Doppler radar, one can obtain the true speed of the vehicle117and estimate w for different road conditions, steering conditions, and the like.

It may be observed that the chance constraint (1), where f is affine in the uncertainty (similarly to (7)), can be considered as a special case of the constraint set/function f,

including N different chance constraints of the form (1) with structure assumed in (9). Here,is a set of known, deterministic constraints on the decision variable z.

Given M samples of the decision variables, it can be shown using (4) that

hold with confidence 1−β with

Consequently, an inner- and outer-approximation to the constraint set in (8) can be computed using the collected samples. In practice, β is set to be very small (for example, 10−6). Here,coincides with the set201inFIG.2, while the Left Hand Side (LHS) of (10a) coincides with the set203inFIG.2.

Thus, the constraint (1) with the f of the form (8) can be enforced using the M samples of the uncertainty w as follows,

Here, the tightening {circumflex over (Q)}wM(Δ+) is computed using the collected samples and the user-specified risk threshold δ.

FIG.3illustrates an exemplar reformulation of the chance constraint using halfspaces, according to some embodiments of the present disclosure. Axis301aand axis301bdenote permissible lateral and longitudinal speeds allowed for the vehicle117, respectively. The speed limit constraint limits the longitudinal speed at303without any restriction on the lateral speed. The chance constraint reformulation using M samples and (10a) tightens the speed limit constraint further to a region305, where a region307is removed from a set of possible longitudinal speeds to enforce (1).

In some embodiments, the uncertainty set ε is defined using an ellipsoid or a union of ellipsoids. In either of these cases, a second-order cone programming or semi-definite programming may be used to enforce the constraint (6) when f is a (possibly non-convex) quadratic function without resorting to the bilevel optimization.

In an embodiment, the uncertainty set is determined based on the empirical quantile function bounded by the confidence bounds, the user-specified risk threshold, and a user-specified template set. In some embodiments, the uncertainty set is an affine transformation of the user-specified template set in a space of uncertainty. A shape of the user-specified template set is one of a halfspace, a polytope, a hypersphere, a hyperellipsoid, a zonotope, a convex shape, and a non-convex shape. For instance, the determination of the uncertainty set ε can be achieved via optimization or binary search of a scaling of the user-specified template set until the desired probability threshold is met. Specifically, the uncertainty set ε is defined as ε=(t), where(t)={w:h(w)≤t} is the user-specified template set for some real-valued function h, and t solves the following optimization problem,

For different choices of function h, different uncertainty sets can be constructed. Examples of the function h include continuous functions such as polynomials, and transcendental functions. To obtain a convex uncertainty set, the function h can be restricted to quasiconvex functions, which are functions whose sublevel sets are convex. The optimization problem (12) has a closed-form expression t*=Qh(w)(δ). Specifically, for t*<1, (12) scales down the set(1), while for t*>1, (12) scales up the set(1), and choice of t* is made to ensure that{w∈(t*)}>δ while making t* as small as possible. In such a manner, the user-specified template set(t) is scaled based on the empirical quantile function, the user-specified template set, and the user-specified risk threshold, to determine the uncertainty set ε.

Since the true quantile function is unknown, (10c) is used and t*={circumflex over (Q)}h(w)(Δ+) is defined to obtain the scaling using the samples and the empirical quantile function. In an embodiment, Δ+is chosen to be conservative in the choice of the uncertainty set.

According to an embodiment, a linear chance constraint can be transformed into the deterministic constraint, by the processor141, by using the halfspace as the uncertainty set. The halfspace is based on a pre-determined normal vector and a parameter determining a shift in the halfspace. For instance, equations (8), (9), (10), and (11) can be cast, for a generic linear chance constraintw{p(z)+cTw≤0}>δ for any function p and vector c in the context of (12), for example, as f(z, w)=p(z)+cTw. For such a chance constraint, the function h is defined as h(w)=cTw,t and the template set(t)={w:cTw≤t} is the halfspace with the pre-determined normal vector c and parameter t determining the shift in the halfspace. Consequently, by solving (12), the uncertainty set ε=(t*)={v∈:cTv≤{circumflex over (Q)}cTwM(Δ+)}, and g(z)=p(z)+{circumflex over (Q)}cTwM(Δ+)are obtained.

In an alternate embodiment, the uncertainty set is an ellipsoidal uncertainty set, i.e., the uncertainty set of an ellipsoid shape. In such an embodiment, a quadratic h(w)=(w−c)TS−1(w−c)=wTS−1w−2cTS−1w+cTS−1c is defined for a p-dimensional uncertainty w with a user-defined vector c∈pand a positive semi-definite matrix S∈p×p, and the template set(t)={w:(w−c)TS−1(w−c)≤t} is a family of ellipsoids. The optimization problem (12) has a closed form expression t*={circumflex over (Q)}h(w)(Δ+). Specifically, (12) scales an ellipsoid/(1) centered at c until probability threshold requirement{w∈(t)}≥δ is met.

FIG.4Aillustrates a family of ellipsoids(t) such as, an ellipsoid401, an ellipsoid403, and an ellipsoid405(which are collectively referred to hereinafter as the ellipsoids401,403, and405), characterized by a specific value of c (point407) and S for different values of t for p=2,according to some embodiments of the present disclosure. The ellipsoid401corresponds to ellipsoid(1). By design, the ellipsoids401,403, and405are nested, and ellipsoids corresponding to smaller values of t are contained in ellipsoids corresponding to larger value of t. For example, the ellipsoid403corresponds to(t1) and the ellipsoid405corresponds to(t2) with t1<t2and the ellipsoid403is contained in the ellipsoid405.

FIG.4Billustrates an ellipsoid411, where the uncertainty set ε includes data samples413and excludes data samples415, according to some embodiments of the present disclosure. The shape of the ellipsoid411forces the uncertainty set ε to contain a region417that does not include any data samples.

FIG.4Cillustrates construction of a union of a pre-determined number of ellipsoids εi419,421, and423that together achieve the probability mass of δ, according to some embodiments of the present disclosure. The union of ellipsoids419,421, and423may be computed via machine learning techniques ,(2) like clustering where a set of samples={wsample(1), wsample(2), . . . wsample(3)} is partitioned into a pre-determined number of groupsisuch that Uii=and setsiare pairwise disjoint. Subsequently, separate empirical quantile functions are computed using the samples from each one of the groups and solve (12) to compute the ellipsoid εi. The use of the union of ellipsoids may permit a more tighter formulation containment of the data samples as compared to a single ellipsoid, e.g., the ellipsoid411. Further, it may be observed that

Consequently, (6) can be expressed as a collection of i constraints of the form maxw∈εif(z, w)≤0.

Additionally, according to some embodiments, quadratic chance constraints can be reformulated using the ellipsoidal uncertainty set obtained by scaling, based on the empirical quantile function, the user-specified template set. The quadratic chance constraints are chance constraints where f is quadratic in the decision variable z and the uncertainty w. Referring back toFIG.1B, the quadratic chance constraints arise when designing motion trajectory125bfor the vehicle117where the obstacles121a,121b, and121cfaced by the vehicle117are desired to be bounded using ellipsoids instead of the bounding boxes123a,123b, and123c.

Additionally or alternatively, for the case of quadratic chance constraints, it may be observed that max∈εf(z, w) can be evaluated for an ellipsoidal ε using S-lemma. Specifically, the S-lemma enables to cast the deterministic constraint max∈εf(z, w)≤0 as a constraint in a semi-definite cone, i.e., require symmetric matrices constructed using functions solely of z, f, and h have non-negative eigenvalues. Such a reformulation enables use of off-the-shelf solvers when solving chance constrained optimization problems with the quadratic chance constraints, without resorting to solving the bilevel optimization problem. In such a manner, the quadratic chance constraints are reformulated into the deterministic constraints based on the S-lemma.

Additionally or alternatively, in some embodiments, different types of template sets including hyperspheres, polytopes, zonotopes, and general convex and non-convex sets, may also be considered by varying the choice of the function h in the definition of(t), with more general forms of the constraint function f.

To that end, according to an embodiment, a generic non-convex chance-constrained optimization problems of the form

can be cast as a deterministic, bilevel optimization problem,

which is then reformulated into the deterministic optimization problem,

Using the empirical quantile functions, some embodiments of the presented disclosure provide a principled approach to convert realizations of the uncertainty w and the constraint function fiand probability threshold δiinto a deterministic constraint gi(z)≤0.The key advantage of such a reformulation is that (14c) can be solved using off-the-shelf nonlinear optimization solvers. Additionally, similarly to (9) and (10), we can use (6) to tighten the chance constraint in (14a) to ensure that every feasible solution of (14c) is also feasible for (14a).

FIG.5Ashows a schematic of a vehicle501including the controller139, according to some embodiments of the present disclosure. As used herein, the vehicle501can be any type of wheeled vehicle, such as a passenger car, bus, or rover. Also, the vehicle501can be an autonomous or semi-autonomous vehicle. For example, some embodiments control the motion of the vehicle501. Examples of the motion include lateral motion of the vehicle501controlled by a steering system503of the vehicle501. In one embodiment, the steering system503is controlled by the controller139. Additionally or alternatively, the steering system503can be controlled by a driver of the vehicle501.

The vehicle501may include an engine506, which can be controlled by the controller139or by other components of the vehicle501. The vehicle501may also include one or more sensors504to sense the surrounding environment. Examples of the sensors504include distance range finders, radars, lidars, and cameras.

The vehicle501can also include one or more sensors505to sense its current motion quantities and internal status. Examples of the sensors505include global positioning system (GPS), accelerometers, inertial measurement units, gyroscopes, shaft rotational sensors, torque sensors, deflection sensors, pressure sensor, and flow sensors. The sensors provide information to the controller139. The vehicle can be equipped with a transceiver507enabling communication capabilities of the controller139through wired or wireless communication channels.

FIG.5Bshows a schematic of interaction between the controller139and controllers520of the vehicle501, according to some embodiments. For example, in some embodiments, the controllers520of the vehicle501are steering controller525and brake/throttle controllers530that control rotation and acceleration of the vehicle501. In such a case, the controller139outputs control commands to the controllers525and530to control a state of the vehicle501such as acceleration, orientation, and the like, for controlling motion of the vehicle501. The controllers520can also include high-level controllers, e.g., a lane-keeping assist controller535that further process the control commands of the controller139. In both cases, the controllers520maps use the control commands of the controller139to control at least one actuator of the vehicle501, such as the steering wheel and/or the brakes of the vehicle501, in order to control the motion of the vehicle501.

FIG.5Cshows a schematic of an autonomous or semi-autonomous vehicle550controlled by the controller139, for which control commands are computed by using principles of some embodiments. The controller139controls the controlled vehicle550to keep the controlled vehicle550within particular bounds of road552, and aims to avoid other uncontrolled vehicles, i.e., obstacles551for the controlled vehicle550. For such controlling, the controller139determines the control commands by solving the optimal control problem subject to the deterministic constraint (6). In some embodiments, the control commands include commands specifying values of one or combination of a steering angle of wheels of the controlled vehicle550, a rotational velocity of the wheels, and an acceleration of the controlled vehicle550. The control commands may, for example, cause the controlled vehicle550to navigate along a trajectory553, without colliding the uncontrolled vehicles551(obstacles).

FIG.6is a schematic illustrating a computing device600for implementing the methods and the controller of the present disclosure. The computing device600includes a power source601, a processor603, a memory605, a storage device607, all connected to a bus609. Further, a high-speed interface611, a low-speed interface613, high-speed expansion ports616and low speed connection ports617, can be connected to the bus609. In addition, a low-speed expansion port619is in connection with the bus609. Further, an input interface621can be connected via the bus609to an external receiver623and an output interface625. A receiver627can be connected to an external transmitter629and a transmitter631via the bus609. Also connected to the bus609can be an external memory633, external sensors635, machine(s)637, and an environment639. Further, one or more external input/output devices641can be connected to the bus609. A network interface controller (NIC)643can be adapted to connect through the bus609to a network645, wherein data or other data, among other things, can be rendered on a third-party display device, third party imaging device, and/or third-party printing device outside of the computer device600.

The memory605can store instructions that are executable by the computer device600and any data that can be utilized by the methods and systems of the present disclosure. The memory605can include random access memory (RAM), read only memory (ROM), flash memory, or any other suitable memory systems. The memory605can be a volatile memory unit or units, and/or a non-volatile memory unit or units. The memory605may also be another form of computer-readable medium, such as a magnetic or optical disk.

The storage device607can be adapted to store supplementary data and/or software modules used by the computer device600. The storage device607can include a hard drive, an optical drive, a thumb-drive, an array of drives, or any combinations thereof. Further, the storage device607can contain a computer-readable medium, such as a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid-state memory device, or an array of devices, including devices in a storage area network or other configurations. Instructions can be stored in an information carrier. The instructions, when executed by one or more processing devices (for example, the processor603), perform one or more methods, such as those described above.

The computing device600can be linked through the bus609, optionally, to a display interface or user Interface (HMI)647adapted to connect the computing device600to a display device649and a keyboard651, wherein the display device649can include a computer monitor, camera, television, projector, or mobile device, among others. In some implementations, the computer device600may include a printer interface to connect to a printing device, wherein the printing device can include a liquid inkjet printer, solid ink printer, large-scale commercial printer, thermal printer, UV printer, or dye-sublimation printer, among others.

The high-speed interface611manages bandwidth-intensive operations for the computing device600, while the low-speed interface613manages lower bandwidth-intensive operations. Such allocation of functions is an example only. In some implementations, the high-speed interface611can be coupled to the memory605, the user interface (HMI)647, and to the keyboard651and the display649(e.g., through a graphics processor or accelerator), and to the high-speed expansion ports616, which may accept various expansion cards via the bus609. In an implementation, the low-speed interface613is coupled to the storage device607and the low-speed expansion ports617, via the bus609. The low-speed expansion ports617, which may include various communication ports (e.g., USB, Bluetooth, Ethernet, wireless Ethernet) may be coupled to the one or more input/output devices641. The computing device600may be connected to a server653and a rack server655. The computing device600may be implemented in several different forms. For example, the computing device600may be implemented as part of the rack server655.

Further, embodiments of the present disclosure and the functional operations described in this specification can be implemented in digital electronic circuitry, in tangibly-embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Further some embodiments of the present disclosure can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions encoded on a tangible non transitory program carrier for execution by, or to control the operation of, data processing apparatus.

Further still, program instructions can be encoded on an artificially generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, which is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus. The computer storage medium can be a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, or a combination of one or more of them.

A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network. Computers suitable for the execution of a computer program include, by way of example, can be based on general or special purpose microprocessors or both, or any other kind of central processing unit. Generally, a central processing unit will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and data.

Although the present disclosure has been described with reference to certain preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the present disclosure. Therefore, it is the aspect of the append claims to cover all such variations and modifications as come within the true spirit and scope of the present disclosure.