Online Learning for Obstacle Avoidance
Authors: David Snyder
Wenhan Xia
Daniel Suo
Anirudha Majumdar
Elad Hazan
Venue: Submitted to ICLR 2023 (2023)
Keywords: obstacle avoidance
online optimization
regret minimization

Abstract: We approach the fundamental problem of obstacle avoidance for robotic systems via the lens of online learning. In contrast to prior work that either assumes worst-case realization of uncertainty in the environment or a given stochastic model of uncertainty, we propose a method that is efficient to implement and provably grants instance-optimality to perturbations of trajectories generated from an open-loop planner in the sense of minimizing worst-case regret. The resulting policy thus adapts online to realizations of uncertainty and provably compares well with the best obstacle avoidance policy in hindsight from a rich class of policies. The method is validated in simulation on a dynamical system environment and compared to baseline open-loop planning and robust Hamilton-Jacobi reachability techniques.

Under review as a conference paper at ICLR 2023
ONLINE LEARNING FOR OBSTACLE AVOIDANCE
Anonymous authors Paper under double-blind review
ABSTRACT
We approach the fundamental problem of obstacle avoidance for robotic systems via the lens of online learning. In contrast to prior work that either assumes worst- case realization of uncertainty the environment or a given stochastic model of uncertainty, we propose method that is efficient to implement and provably grants instance-optimality to perturbations of trajectories generated from an open-loop planner in the sense of minimizing worst-case regret. The resulting policy thus adapts online to realizations of uncertainty and provably compares well with the best obstacle avoidance policy in hindsight from rich class of policies. The method is validated in simulation on a dynamical system environment and compared to baseline open-loop planning and robust Hamilton-Jacobi reachability techniques.
INTRODUCTION
The problem of obstacle avoidance in motion planning is fundamental and challenging task the core of robotics and robot safety. Successfully solving the problem requires dealing with environments that are inherently uncertain and noisy: robot must take into account uncertainty in its dynamics, e.g., due to external disturbances or unmodeled effects, and the dynamics of other agents in the environment, e.g., humans other robots. Approaches for tackling the obstacle avoidance problem in robotics typically fall under two categories: (i) methods that attempt to construct stochastic models of uncertainty in the dynamics of the robot and other agents and use the resulting probabilistic models for planning, and (ii) methods that construct plans that take into account worst-case behavior. In Sec. 2 we give more detailed overview of both classes of approaches.
In this paper, we are motivated by Vapnik's principle: "when solving given problem, try to avoid solving an even harder problem as an intermediate step". Constructing accurate models of external disturbances and the dynamics of humans or other agents is perhaps more complicated than the task of obstacle avoidance motion planning. The uncertainty in these dynamics rarely conform to the assumptions made by the two classes of approaches highlighted above: external disturbances and human motion are typically neither fully stochastic nor fully adversarial. This motivates the need for online learning methods for adaptive non-stochastic control to avoid obstacles as they perceived by the robot's sensors.
Statement of Contributions. In this work, we pose the problem of obstacle avoidance in regret minimization framework and build on techniques from non-stochastic control. Our primary contribu- tion is a gradient- gradient-based online learning algorithm for the task of obstacle avoidance, coupled with provable regret bounds that show our obstacle avoidance policy to be comparable to the best policy in hindsight from a given class of closed-loop policies. This type of theoretical performance guarantee is nonstandard, and allows us to flcxibly adapt to the behavior of the uncertainty in any instance of the obstacle avoidance problem without making a priori assumptions about whether the uncertainty is stochastic or adversarial. In addition, the resulting method is computationally efficient. The method applied experiments with complex (and dynamic) obstacle environments, and demonstrates improved performance in respective instances where open-loop planners and overly-robust methods can struggle.
2 RELATED WORK
Our results apply techniques from online learning to the problem of obstacle avoidance in order to provide efficiently computable safety guarantees. Both online learning and safe motion planning

---

Under review as a conference paper at ICLR 2023
have generated significant interest and theoretical development in the past few years; we our work within these contexts below.
Online Learning for Control. Many canonical control-theoretic results have recently been cast as problems in online learning [Hannan 1958; Cesa-Bianchi & Lugosi 2006), providing interesting
generalizations to established control results like the -inaar-quadratic regulator (Cohen al.] 2018
Agarwal et al. 2019a c) and Hao robust control (Ghai et al., 202I). Optimal results in sample
complexity (Dean et al. 2020) and control synthesis for unknown linear systems (Hazan al. 2020
illustrate further generalization. of standard controllers.
Control formulations are often efficiently solvable due to the convexity of the objective; however, "higher-level" decision- decision-making tasks like motion planning and obstacle avoidance have non-convex objective functions (e.g., maximizing the distance of an ego vehicle to its nearest obstacle). Fortu- nately, some non-convex problem formulations actually admit "hidden convexity," " meaning that they can be reformulated (via nonlinear transformations, relaxations, or conversions to an efficient dual formulation see Xia (2200) for a survey) into equivalent optimization problems that are convex. This allows for efficient solutions (e.g.. Ben- Tal & Teboulle (996);; Konno & Kuno (1995); Voss et al. (2016) to problems that nominally would be hard to solve (e.g.. Matsui (1996). ). Our work gives such a reformulation for an obstacle avoidance task, which differs from but builds upon the existing online learning and control literature.
Motion Planning. Effective motion planning is a central challenge within robotics that has both generated consistent interest for many years and has spurred many recent developments. Inspired by the classical search algorithms of Dijkstra (1959); Hart et al. (1968), many sampling- -baned,
probabilistic techniques (Kavraki et al., 1996 La Valle & Kuffner 2001 Karaman & Frazzoli 2 Kobilarov 2012) have come to the fore due to several key characteristics: (1) provable probabilistic
completeness, (2) extension to continuous state, action, and configuration spaces, and (3) direct integration with differential constraints on robot kinematics and dynamics. The case of obstacle avoidance in multi-agent settings has also been considered in the literature, although many existing practical algorithms (van den Berg et al. 2011 Zhou et al. 2017) are difficult to analyze theoretically. Most importantly, however, none of the above methods directly model and account for the effects of disturbances, sensor noise, or other uncertainty within the system.
Safe and Robust Motion Planning. Construction of robust planning algorithms forms the natural development from the above limitation. Existing robust planning techniques generally fall into one of two categories: (i) methods that make assumptions on the distribution of uncertainty, or (ii) methods that assume worst-case disturbances. One of the earliest methods utilizes chance constraints to bound the probability of collision under stochastic uncertainty (Charnes & Cooper 1959); this framework is extended to various sources of stochastic uncertainty in dynamical systems in Blackmore et al. (006);; :
Du Toit & Burdick (01T). To model stochastic noise in robot's sensory observations, extensions of planning algorithms to partially observable Markov decision processes (POMDPs) and to planning in the robot belief space have been developed (Kaelbligg et al. 1998 Prentice & Roy 2009 Platt et al.,
2012). However, these methods do not account for a notion of worst-case behavior yet must often still rely on moderately strong distributional assumptions (e.g. Gaussian noise) in practice.
To account for worst-case disturbances, Hamilton-Jacoti (HJ) reachability (Mitchell & Tomlin 2003
Bansal et al. 2017) and robust trajectory library methods (Singh al. 2017 Majumdar & Tedrake
2017) have been developed to provide non-stochastic (adversarial) certificates of safety for path planning problems. Given only an assumption of bounded disturbances, these techniques construct corresponding representations (or outer approximations) to the safe and unsafe regions of the state space conditional on the robot dynamics, obstacle placement, and disturbance size. HJ methods, which generally suffer from the curse of dimensionality (Darbon & Osher 2016) (although with the potential for speed-ups certain settings (Herbert et al. 2017)), use the formalism of the differential game [Isaacs] 1965) to provide a "global" notion of safe and unsafe sets MMitchell al. 2005). By comparison, robust trajectory librarics, which are usually computed using convex programs (Parrilo 2003) provide safety guarantees in the form of robust "tubes" or "funnels" (Burridge et al. 1999 Majumdar & Tedrake 2017) that encompass only the nominal trajectory (or hypothesized trajectories) within the space.
The key distinction of our work from these methods arises from the desire for "instance- optiiallttptmmaitt" namely, the development of an algorithm through the use of online learning and regret minimization
2

---

Under review as a conference paper at ICLR 2023
that yields a controller that adapts to the nature of the disturbances observed. In particular, this allows the method to recover effective performance in both stochastic and non-stochastic regimes; we do not sacrifice good transient behavior in "bennin" environments in order to provide guarantees about robust performance more adversarial cases, and vice versa.
3 PROBLEM FORMULATION
Consider a discrete-time dynamical system with state x and control input ú. planning oracle (Xo)) takes in an initial state and generates nominal state trajectory with associated control inputs (x) - We intend to design an adversary-robust obstacle avoidance controller that will act to update the trajectory to avoid local obstacles. Intuitively, this will serve as faster "safety inner loop" for the slower trajectory planning stage Or, keeping the agent safe from external features unseen planning time. The key modeling assumption necessary proceed is to assume that the dynamics of perturbations about the nominal trajectory are well-modeled by linear discrete- time dynamic Defining x, X, x and u, ü, u.. express this modeling assumption as
X Ax; + Bu, + DWr.
where w; is a bounded, unknown, possibly-adversarial disturbance. For many practical cases, the linear dynamics assumption is reasonable; one concrete example is a control-affine system with feedback lincarization in the planning controller. Our task is to construct a "residual" controller generating u, so to correct the system in order to avoid obstacles. Intuitively, Or is the optimistic, goal-oriented planner (in practice, the planner could be an off-the-shed algorithm, see for example the OMPL library (Sucan al. 2012)), while controller acts as a robust safety mechanism that becomes active only when needed, and in a provably effective manner.
3.1 SAFETY CONTROLLER OBJECTIVE
The proxy objective for the controller trying to avoid obstacles is maximize the distance to the nearest obstacle, subject to regularization of state deviations and control usage. We assume a sensor mechanism that reports all obstacle positions within a given radius of the agent. The optimization problem, for a trajectory of length T, safety horizon of length T. S T, and obstacle positions p/ denoting the jth sensed obstacle at time t, is
Cobs(A) = Σ min min ||x - p2l ||x 12 FE[L]
| 11
max AEA
Here, A is the set of online algorithms that choose actions for the controller take, and x/ denotes the state trajectory reached given actions u,a ~ A E A. The last two terms represent quadratic state and action costs penalizing large deviations from the nominal trajectory and large actions; these costs are very common objectives in the control literature, but serve in this instance instead to regularize the solution the obstacle avoidance task. Further, in order be tractably analyzed, the collision avoidance objective is relaxed to a quadratic penalty term; nonetheless, even this relaxation nonconvex due the selection over time and obstacle indices of the minimal-distanee obstacle in the first term of Cobs. As the optimal policy may be hard to find in practice, we instead relax the problem into one of online learning and regret minimization (Agarwal all, 2019a). This allows us to define the safety metric with respect to the best achievable performance in hindsight with respect to comparator class (which we describe in the following section). For sufficiently powerful and convex comparator class, we can achieve guarantees on the safety of the resulting controller.
3.2 REGRET FRAMEWORK FOR OBSTACLE AVOIDANCE
Leveraging the expressiveness of linear dynamic controllers (LDCs) Ghai et al., 2021 Agarwal
et al. 2019a), use the tisturbance-action controller parameterization construct low-regret
'The results here presented for linear time-invariant (LTI) systems. We believe that the results extend linear varying (LTTV) systems under reasonable but slightly more technical assumptions; however, this formal analysis is left as future work.
Here, we omit the fully general LQQR costs (time-varying Qe and R₂) for simplicity of presentation; however, the results we show will also hold for this more general setting.
3

---

Under review as a conference paper at ICLR 2023
framework. The action is the sum of stabilized nominal action and residual obstacle-avoiding term, as shown in Eqn.
H M fl
U
Kx2
+
We-s-
It will be useful to define the intermediate quantities ü, system dynamics are equivalently expressed as
Kx, and A = A BK. Then the
X Ax, + Bü,- + Dw
(4)
The comparator class IT will be the class of LDCss parameterized by M; this class has provably expressive approximation characteristics (Agarwal et al. 2019a). The regret is defined using quantities from Eqn. as
Cabsa (A)
Regr(A)
sup W
max Cobs MEll
Eqn. 5 implles that the adaptive sequence Mr selected by low-regret online algorithm A will compete on average with the best fixed policy M in hindsight. Note that this is an instance-optimal, finite time guarantee. Specifically, the optimum M1 may vary with the choice of disturbances, the selection of time horizon T, or the particular obstacle array and planner. The guarantee ensures that the sequence of M, chosen by algorithm competes with M for all choices of these parameters.
3.3 TRUST REGION OPTIMIZATION
trust region optimization problem (Sorensen 1980) is nominally non-convex optimization
problem that admits hidden convexity. Formulating a problem as a trust region instance (see Def. allows for convex relaxation that can be solved efficiently (Ben-Tal & Teboulle 1996 Hazan &
Koren 2016).
Definition 1 (Trust Region Instance). A trust region instance is defined by a tuple (P, (P.p. P.p.D) D) with P Rdxd p E Rd, and D >> 0 as the mathematical optimization problem
max DD
2 PP2
(6)
Throughout the remainder of this paper. we will use "trust region instance" to refer interchangeably to instances of Def. [ and the implicit, equivalent convex relaxation.
4 METHODOLOGY AND ALGORITHM
We begin with a brief outline of the regret minimization method, from which we outline the resulting algorithm and describe its key properties.
4.1 REGRET MINIMIZATION METHODOLOGY
Many existing results in online learning and control formulate guarantees by posing the specific problem as a (possibly complex) online convex optimization (Hazan) 2021) instance, which can be
solved in efficient manner (Boyd & Vandenberghe 2004). This method alone will not suffice
for our setting because of the non-convexity of the objective. However, optimal regret bounds for
online non-convex optimization have been shown via "Follow the Perturbed Leader" (FPL) method
for problems with an optimization oracle of known performance (Agarwal et al., 2019b Suggala
Netrapalli 2020). This was extended the setting with memory Ghai al. (2021). The key
challenge here is to reduce our con-convex setting to one in which a good oracle is feasible, and then
follow through with the analysis to combine the results of Suggala & Netrapalli (020)) Ghai et (202T) with the guarantees for online convex optimization.
4.2 NON-CONVEX MEMORY FPL FOR OBSTACLE AVOIDANCE
Adapting the general online non-convex FPL framework, we formulate the obstacle avoidance safety controller online FPL algorithm, shown in Alg. The procedure is relatively direct. The agent
4

---

Under review as a conference paper at ICLR 2023
plays Mr. which induces ú, via Eqn. The state dynamics propagated to reveal w, and observe
X4+1. and then sensor reading is taken to observe the new local obstacle positions. The reward
(Eqn. 7 is revealed by the environment, and the agent incurs the loss of action M, Finally, the agent
updates Mc+1 using the new information by solving the optimization problem in Eqn. X Eqn. B the
component of the algorithm, where the inner product (M Po) serves as the regularizing perturbation. Importantly, the history length H determines how large M is (see Eqn. D}. We will show that H can be reduced logarithmic dependence T,, the random play at the outset in Alg. does not form a significant portion of the game.
Algorithm 1 Non-convex Memory FPL for Obstacle Avoidance
Input: (partially observed) {p/ ) planning horizon L, history length H
Input: Full horizon T, algorithm parameters {n, e, A}, initial state X0
Input: Open-loop plan: uj for L...,
Initialize: Closed-loop correction M fixed perturbation Po ~ Exp(n) xHd
Initialize: Play randomly for = (0.... H - 1}, observe rewards, states, noises, and obstacles for t=H...T-1 do Play Mt 1 and observe state X noise w,, and sensed obstacles (D1+1)ee/B)44
Observe the reward function
= min JE(A]
| P|-11 |xx+1ll8 - |/u:122
Solve for Mi/ as the solution to
[1:1 [M
1+1
arg max
Σ L(M) 1(M Po)
(8)
end for return My+1
To feasibly engage the obstacle avoidance algorithm, it necessary to solve for optimal solutions the objective in Eqn. g We show that the optimum can be found as the solution to an iterative "hidden convex" " -concave game (Hazan 2006 in which the players respectively solve hidden-convex trust region objective and utilize a low-regret algorithm (exponentiated gradient from Kivinen & Warmuth (1997) for linear objective on the simplex. We show in Alg. a method iteratively solve for
M in Eqn. 8 of Alg.
Algorithm 2 (General) Hidden- Formulation for Objective in Eqn.
Input: Set vectors {a,); matrix B, vectors b, b Input: Iterations N, learning 7), approx. error 6, perturbation Po. diameter DM Initialize: Vector co =
for n=O...N do (1) Solve for Mn
M, = arg max MM
Σ cnliilla BMb llbo + BMBI3 - |[Mb| + A(M Po)
(2) Update Cn-1
Cne ve -Vv. + +.bb)l1)++MBB133)
Ca+1
II An
(10)
end for return Mn
5

---

Under review as a conference paper at ICLR 2023
5 ANALYSIS AND REGRET BOUND
We now present our main theoretical contributions: we demonstrate that Alg. A efficiently solves the optimization in Eqn. g and that (as a consequence) Alg. aattais low (sublinear) regret. We defer details of all proofs to App. A and only present the main ideas here.
CONVEX OBSTACLE AVOIDANCE: ALG. EFFICIENTLY SOLVES BQN.
We first analyze the behavior of Alg. and demonstrate that My solves the optimization problem To establish this we need a few assumptions and key lemma.
g
Assumption 2 (Bounded Disturbances). The disturbances are norm norm-bounded by a constant Cw-
Assumption 3 (Stabilizabillity and Conditioning). The matrix Ā HHH-1, with |A] 11-7
Further, assume that || S and that [|Å]], [[B]], || S 3.
Remark 4 (Bounded Behavior). The state (xx) and imput (ūx) are norm- norm-bounded by constants Cz. Cu.
Proof. From Assumption 2 and Eqn. 3 we have that | S HDDMCum Therefore, by Assumption we have that |[ + Dw.ll 23 Ca Assume wlog that ||xol| S 2 D5HDMMC D Then true that for every 2 0, x 12 S 23HDM
Then Oz. Cy can be chosen appropriately.
Assumption (No Extraneous Inputs). The dynamics matrix B E RRd= xdu has rank (3) = d.
Lemma 6 (Trust Region Instance). Eqn. U
is a trust region instance (Defn. 7 that can be solved
efficiently.
Proof of this lemma is deferred Appendix A.4
Theorem (Solving Eqn. The optimization in Eqn.
8 solved efficiently using Alg.
Proof. The proof requires two steps: constructing instance of Eqn. 9 that solves Eqn. 8
and
demonstrating that Alg. converges to this instance and its optimal solution by using Lemma For space considerations, the full construction is deferred to App. A.2
5.2 TOWARDS A REGRET BOUND: FPL WITH MEMORY
In order to demonstrate the low regret of Alg. D we utilize regret bound that extends results for non-convex FPL to the equivalent setting with memory (Anava al., 2015: Arora et al. 2012). This important for the control theoretic setting we consider here, where there is inherent memory of previous control inputs expressed in the state of the agent. This extension of non-convex FPL to settings with memory was developed in Ghai et al. (202I); we state their result here.
Theorem 8 (FPL with Memory Ghai et al. (021)). Let M E Rdd be a convex decision set with || D. Assume that for all E [T], the loss functions (,M,, My.....) :) are L-Lipschitz with respect to the En-nrrm in each argument. Then, for any there exists an algorithm (see App. A.3 that achieves expected regret
T Σ
T
(.MM H41,..,, Md] < H2 + dD
max MEM
M)
Σ
+eHT.
1=H
5.3 TOWARDS REGRET BOUND: STATE APPROXIMATION STABILITY AND HISTORY
In order to apply the results from Sec. 5.2 for establishing low regret of Alg. need to limit the effect of the state history on the regret. This is accomplished via the stability of the closed-loop
dynamics. Since we use the coturbance-actionn parameterization (Aarwal et al. 20 9a Hazan et al.
Asssmptton holds without loss of generality; if rank B)) rg <, du. simply choose subset of B with rg independent columns and fix any other inputs to he uniformly

---

Under review as a conference paper at ICLR 2023
2020) for the controller in Eqn.
can be shown that the state can be expressed as function of limited history the actions:
3
2H
2H Σ We-Weyj X
H
V W
(11)
where Vi,y is the disturbance- state transfer function (matrix) between disturbance wi-j and state x (see Eqn. 12 The boundedness of H ensures that the effect of any "bad" action does not linger too long within the system. By the (1 - of Á (Assumption 3). for the state to be approximated by Eqn. (IT) within an error fraction of the history H grows only logarithmically with l/e. Further, note that Vr, is linear in M, for all {1, 7;::
H
v (M Mi-1) = DDI < H
Σ
A'
D - i (I, M
(12)
1=1
Remark (Bounded Cost Error), For H = 1 lo- (5n²C,(1 (1+ 3DM the error in cost is less than Cz/T. See App. A.5.2 for the proof.
5.4 REGRET BOUND
We conclude the analysis by stating the main theorem of the paper, which establishes the low regret of the obstacle avoidance algorithm.
Theorem 10 (Regret Bound for Alg. achieves
Alg.
utilizing Alg. as an optimization subroutine,
RegT (A) I O(poly(C)VT)
(13)
where C measure of the complexity of the optimization instance (Ghai al. 2021 Agarwal et al.
2019a Chen & Hazan 2021
Proof. Using the boundedness the disturbances, states, and actions (Assumption 2 and Remark 4. choose appropriate H such that the error of approximation of the state X is small per Eqn. App. A.5.2 gives H (log T') such that the error in associated costs less than Cz/'T' (see
Remark
Now, we analyze the regret as follows:
T-1
Regr = max MET
Σ
4- (x (p!),
Σ
(x (p(),
1=
-=
C2 (x)
C Mi)
max Mell
Σ
(4, M,... M)
Σ
(M.
T
(=H-1
t=H-1
T-1
max MElT 1=1-1
Σ
4+1
( Mc)
+ +(logT
S @(poly(C)VT)
We provide justification for each step. The first line is the regret definition. Next, we utilize the truncated state history representation
rewards to upper bound the regret by an error term (from Remark in addition to the approximate costs as a function of X
Now, because the approximate states are linear the Vr,j and the rewards are quadratic, it can be shown that the rewards for the approximate states quadratic in the actions. Therefore, even using the truncated history length H. the optimization still of a form amenable to Lemma 0 and Theorem As such, every step of Alg. [ becomes efficiently computable.
Finally, efficient computability allows us to use an effective oracle within the Non-convex FPL framework of "Suggala & Netrapalli (2020). Therefore, after rearranging to the third line and upper bounding the I/l terms, we arrive at the final line by citing the FPL with Memory result in Ghai al. (202T).
7

---

Under review as a conference paper at ICLR 2023
EXPERIMENTS
We demonstrate the effectiveness of our method under different online scenarios and various modes of environmental perturbation. For the experimental setting, we consider 2D racing problem with the goal of avoiding obstacles in an online fashion (Fig. D We use this example to demonstrate cases which our algorithm outperforms established baselines.
random
centerline
pedestrian
slalom
100
(mm)
40-
000000000000
20
-40
-20
20
40
-40
-20
0
20
40
-40
-00
-40
-20
20
40
X (m)
X (m)
(m)
X (m)
Figure 1: Visualization of experimental environments. (a) Random static obstacles. (b) Vertically stacked obstacles. (c) Moving pedestrian. (d) Slalom course.
6.1 EXPERIMENT OVERVIEW, BASELINE PLANNERS, AND SETUP
In the experimental environment, the racer (car) starts the origin and observes obstacles in its sensor range (blue shaded semi-circle). The obstacles are generated at random positions for every testing environment and can have different sizes and velocities; this adds partial observability to the environment. We implemented our algorithm and the simulation environments in JAX; all experiments are carried out on single CPU minutes. On average, 5.6 seconds are required for the computation of control signal every time new observation is made.
The experiments consist of two components. First, our planner is evaluated across four different scenarios (see Fig. D: (I) random static obstacles, (2) centerline static obstacles, (3) "pedestrian" obstacles that have unknown, non-zero velocities, and (4) a challenging "slalom course" with walls of obstacles and gates. For each environment, both stochastic and non-stochastic disturbances and the safety evaluated via measuring the minimal distance to obstacles. The second component of the experiments focuses the second configuration ("centerline") described above, and explores how our algorithm performs against several baselines. We utilize a HJ reachability planner (ASL. 202T), as well modified kinodynamic RRT* implementation (Zhou 2020) generate more "optimistic" plans. We hypothesize two key behaviors: our algorithm (1) performs (nearly) as effectively with respect standard LQR costs in states and inputs RRT* when disturbances "benign," and (2)
tested
performs (nearly) as well as HJ methods when disturbances are adversarial.
6.2 EXPERIMENTAL RESULTS
The first component of the experiments is summarized in Fig. 2 where minimal distance to obstacles over time is plotted for each environment and disturbance type. The distances for all cases remain greater than zero, indicating that our algorithm remains safe and avoids collisions. We note that challenging slalom instances those with narrow openings and large requisite deviations our algorithm suffers empirically due to the inherently long cost memory within the slalom environment design. This corresponds the planner being forced to overcome very poor nominal planned trajectory, and in combination with the gated passageways, requires very precise sequences of inputs. This notion of "memory" provides an interesting and interpretable metric of the difficulty of an obstacle avoidance instance, and is discussed further in App.
For the second component of the experiments, we report the results for each planning algorithm on the centerline example in Table For each planner, three separate disturbance setups were utilized, and each planner-diste glanner-disturbance disturbance configuration was run on the equivalent of 50 centerline obstacles. Several key aspects of Table deserve note. First, expected, RRT fails handle unmodeled disturbances
8

---

Under review as a conference paper at ICLR 2023
Randam Obstacles
Centerline
Moving Pedestrian
Haacon
Dicalind
Figure 2: Performance across varied environments and disturbances. The minimal distance remains positive, demonstrating the safety of our planner.
effectively, with high failure rate (see App. adversariality is reduced, they fail to take advantage of existing structure in the disturbances; this is readily apparent in the fact that for sinusoidal noise (which incentivizes the racer to pass the obstacles on the right), the HJ planner passes on the left and right in equal proportion. In contrast, our planning module is able to adapt to the structure of the disturbances to take the "casier route" with lower cost. Additionally, we note that, while our planner does not recover the performance of RRT' under random disturbances, if the fraction of failures is controlled for (i.e., if we average only over the best 40% of online runs), the performance of our algorithm 0.42 = 0.03, versus 0.50 + 0.03 for the equivalent for the HJ planner.
Second, while HJ planning methods improve as
Sample trajectories for each case are included in App.
Table Planner performance for each disturbance type. Costs are given in terms of linear-quadratic (LQ) costs (top) and fraction of failures (bottom). Best-performing cases for each column are bold. LQ costs are only computed for successful passes; as such, RRT* intentionally blank for two entries.
Planner
Random
Sinusoid
Adversarial
RRT
0.27 + 0.05
0.60
1.00
1.00
HJ Plan
0.55 0.05
0.59 + 0.14
1.01 + 0.03
0.00
0.00
0.00
Online
0.51 + 0.09
0.49 + 0.13
1.57 + 0.65
(ours)
0.06
0.04
0.26
7 CONCLUSION AND LIMITATIONS
We develop a regret minimization framework for the problem of obstacle avoidance. In contrast to prior approaches that either assume worst-case realization of uncertainty or given stochastic model, we utilize techniques from online learning in order to adaptively react to disturbances and obstacles. To this end, we prove regret bounds that demonstrate that our obstacle avoidance policy is comparable to the best policy in hindsight from given class of closed-loop policies. Simulation experiments demonstrate that our approach compares favorably with baselines terms computational efficiency and performance on settings with varying disturbances and obstacle behaviors. Additionally, our framework provides a possible means of understanding the instance-specific "difficulty" of obstacle avoidance problems through parameterizations of the cost memory (H) and other parameters. As such, future guarantees may be possible for classes of dynamics and classes of obstacles.
In future work, we intend to explore the above directions in addition richer comparator classes. Further, it would be of practical interest to tackle settings with more complex dynamics and obstacle geometries than considered here. Finally, approach on real hardware platforms (e.g., drones).
interested in practical demonstrations of our

---

Under review as a conference paper at ICLR 2023
REFERENCES
Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online Control with Adversarial Disturbances. In Proceedings of the 36th International Conference on Machine Learning, pp. 111-119. PMLR, May 2019a. URL htt.pss:/ppocceed.ggg/.. mlr press/
v 9c html
ISSN: 2640-3498.
Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Conference on Learning Theory, pp. 18-29. PMLR, 2019b.
Naman Agarwal, Flad Hazan, and Karan Singh. Logarithmic Regret for Online Con- trol. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019c. URL (tt.5f11fa2af99176e1110a AASTA html
nips wc/paperr//19//aaeeeeeeeeoe Abstract
Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: price of past mistakes. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume 1, NIPS' pp. 784-792, Cambridge, MA, USA, December 2015,
MIT Press.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Coference on International Conference Machine Learning, ICML'12 12, pp. 1747-1754, Madison, WI, USA, June 2012. Omnipress. ISBN 978-1-4503-1285-1
Stanford ASL. Hj-reachabilityy in jax. teachability 2021.
Somil Bansal, Mo Chen, Sylvia Herbert, and Claire J. Tomlin, Hamilton-Jacobi reachability: A brief overview and recent advances. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 2242-2253, Melbourne, Australia, December 2017. IEEE Press. doi: NM.1009/CDC.2011.8266977
URL https://doi..... org 1tt9//.0..11///PP/ 2017.01700 8263977
Aharon Ben- Tal and Mare Teboulle. Hidden convexity in some nonconvex quadratically constrained
quadratic programming. Mathematical Programmingg 72(1): January 1996. ISSN 1436- 4646. doi: 10.1007/BF005922331 URL httpp:::p:p....rroooooe o00 1ttp:///11..1000//0200.0
Lars Blackmore, Hui Li, and Brian Williams. A probabilistic approach to optimal robust path planning with obstacles. In Proceedings of the American Control Conference, 2006.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. doi: 10.1017/CR0970051
R. R. Burridge, A. Rizzi, and D. E. Koditschek. Sequential Composition of Dynamically Dexterous Robot Behaviors. The International Journal of Robotics Research, 18(6):534 555, June 1999. ISSN -6778-3344, doi: 10.117/027336499906688 URL htt.thttt////ett 0ttttss///oil.oo/111111111 027 02783649922066333
Publisher: SAGE Publications Ltd STM.
Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. doi: 10.1017/CB0978051 155189999801114922.. 1546921.
A. Charnes and W. W. Cooper. Chance-Constrainer Programming. Management Science,6(1):73--5 6(1):73-79 October 1959. ISSN 0025-1909. doi: 10. 13.. URL htttps://doi.orq//
1287 ww77/nssc.o
Xinyi Chen and Elad Hazan. Black-Box Control for Linear Dynamical Systems. In Proceedings of Thirty Fourth Conference on Learning Theory, pp. 1114-1143, PMLR, July 2021. URL ISSN: 2640-3498.
http://cceeeeiiioo.rrreeeeeee//a wwt...ppp.ee.e////eeeeeeoeee http/////chee1cccc .tml
mlr. www.r.press/vve
Alon Cohen, Avinatan Hasidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online Linear Quadratic Control. In Proceedings of the 35th International Conference on Machine Learning, pp. 1029-1038, PMLR, July 2018. URL
mlr. press/
v80/ 8b. h
ISSN: 2640-3498.
10

---

Under review as a conference paper at ICLR 2023
Jerome Darbon and Stanley Osher. Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacon equations arising in control theory and elsewhere. Research in the Mathematiccal Sciences, 3(1):19, September 2016. ISSN 2197-9847. doi: 10. 10.1186:440687-01--00066
URL
htttps: //ss:///o/ http://o...r/...... 186/ w4048408880
0068-7
Sarah Dean, Horia Mania. Nikolai Matni, Benjamin Recht, and Stephen Tu. On the Sample Com- plexity of the Linear Quadratic Regulator. Foundations of Computational Mathematicc, 20 (4):633-679, August 2020. ISSN 1615-3375.
URL https::/rreoovee.. wwweeollee..aatechheee. edu/ Number: 4 Publisher: Springer.
caltech.
CaltechAUTHORS 201 90806 11088006113710000 130716007
E. W. Dijkstra. note on two problems in connexion with graphs. Numerische Mathematik, (1):269-271, December 1959. ISSN 0945-3245.
doi: 10.1007/BF011386390 URL https
Noel E. Du Toit and Joel W. Burdick. Probabilistic Collision Checking With Chance Constraints. IEEE Transactions on Robotics, 27(4)8809-115, August 2011. 1. ISSN 1941-0468. doi: 10.1109/
TRO.2011.2116190 Conference Name: IEEE Transactions on Roboties.
Udaya Ghai, David Snyder, Anirudha Majumdar, and Elad Hazan. Generating Adversarial Dis- turbances for Controller Verification. Proceedings of the 3rd Conference on Learning for Dynamics and Control, pp. 120-1100. PMLR, May 2021. URL https:://rroceeetee
mlr wttpps//14///aaa2222LLL html
ISSN: 2640-3498.
James Hannan. Approximation to Bayes Risk in Repeated Play. In Approximattin to Bayes Risk in Repeated Play, pp. 97-140. Princeton University Press, 1958. ISBN 978-1-4008-8215-1 doi: 10.1515/978140082251--000 URL http::::s/wwwww.eggureeee
com/document/dol.
http//hhmmmlaageennn ?lang=en.
Peter E. Hart, Nils Nilsson, and Bertram Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. JEEE Transactions on Systems Science and Cybernetics, 4(2):100- 107, July 1968. ISSN 2168-2887. doi: 10. 109/TSSC.1968.300113.... Conference Name: IEEE Transactions on Systems Science and Cybernetics.
Elad Hazan. Approximate Convex Optimization by Online Game Playing. arXiv:cs/0610119, October October 2006.
061 0011119 arXiv: cs/0610119.
Elad Hazan. Introduction to Online Convex Optimization. December 2021. URL http::/arrx
prg/aba/ www.abbs...... 05207
arXiv: 1909.05207.
Elad Hazan and Tomer Koren. A linear-time algorithm for trust region problems. Mathematical Programming, 158(1):363-33) 2016.
Elad Hazan, Sham Kakade, and Karan Singh. The Nonstochastic Control Problem. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, pp. 408 421. PMLR, January 2020. 3498.
http:///oocedddeecoo ngs mm www.prrssslll. http//////haaaaaaa/ html ISSN: 2640-
Sylvia L. Herbert, Mo Chen, SooJean Han, Somil Bansal, Jaime F. Fisac, and Claire J. Tomlin. FaSTrack: modular framework for fast and guaranteed safe motion planning. 20/7 IEEE 56th Annual Conference Decision and Control (CDC), pp. 1517-1522, Melbourn,, Australia, December 2017. IEEE Press, doi: ALL110//CDCC22017882666666 URL
1109/ 1109/CDC.20 201 8263867
R. Isaacs. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. Dover books on mathematics. Wiley, 1965. ISBN 978-0-471-42860-2 URL https: /bookss///ooo....
www.oooks.ooooe.......ooooo googleoogeeeeooooooo le. com books wttpkk/eeidd.aa11aaaaaaaaa.aaaaa
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in
partially observable stochastic domains. Artificial Intelligence, 101(1-2):99-11 134, May 1998. ISSN 00043702. doi: 000110066/0004444702298091000000 ottr:///..............///////nn.

---

Under review as a conference paper at ICLR 2023
Sertac Karaman and Emilio Frazzoli. Sampling based algorithms for optimal motion planning. The International Journal of Robotics Research, 30(7):866 894, June 2011. ISSN 0278 3649. doi: 10.1177/02783649 14406661. URL Publisher: SAGE Publications Ltd STM.
Sampling-based
L.E. Kavraki, P. Svestka, J.-C. Latombe, and M.H. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Transactions on Robotics and Automation, 5264):56,5580, August 1996. ISSN 2374-958X. doi: 10.1109770.508439. Conference Name:
IEEE Transactions on Robotics and Automation.
Jyrki Kivinen and Manfred K. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132(1):1-63, 1997. ISSN 0890-5401. doi: https:
//doi. //bb..org/1..1006/mco...o/ 1996. 2612. URL http://wwwwwc.n.....ccccccc.cc.. rect. com/ /onmsciinne///
artic Sct.cceep.11/3339500010383
Marin Kobilarov. Cross-entropy motion planning. The International Journal of Robotics Research, 31(7):855-871 June 2012. ISSN 0278-3649. doi: 00.1177002783649144446 URL https Publisher: SAGE Publications Ltd STM.
Hiroshi Konno and Takahito Kuno. Multiplicative Programming Problems. In Reiner Horst and Panos M. Pardalos (eds.). Handbook of Global Optimizatioon Nonconvex Optimization and Its Ap-
plications, pp. 465.400..550 Springer US, Boston, MA, 1995. ISBN 07781---115-22---2222 doi: 10.1007/
978-1-4615-2025-22 URL htwph: /tt:://doo..oo org /10. 10. 1w07/97001188 4615
LaValle and J Kuffner. Randomized Kinodynamic Planning. 1/RR, 20:378 2001. URL
https:///ournn:
Anirudha Majumdar and Russ Tedrake. Funnel libraries for real-time robust feedback motion
planning. The International Journal of Robotics Research, 36(8)947--88, 2017. doi: 10.1177/
0278364917712421. /ttpa///////......///0/1/1111111
Matsui. NP-hardness of linear multiplicatiie programming and related problems. Journal of Global Optimization, 9(2: September 1996. ISSN 1573-2916. doi: 10.1007/BF00121655. URL
lan M. Mitchell and Claire J. Tomlin. Overapproximating Reachable Sets by Hamilton-Jacobe Projec-
tions. Journal of Scientific Computing, 19(1):323-344 346, December 2003. ISSN 1573-7691. doi: 10.1023/A:100253422773
URL /ttp:::///oi..r///0... 1023/A....223130 Ttt.///A..22233222211
L.M. Mitchell, A.M. Bayen, and C.J. Tomlin. A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games. IEEE Transactions on Automatic Control, 50(7): 947-957, July 2005. ISSN 1558-2523, doi: (1009//AAC.200588144399 Conference Name: IEEE
Transactions on Automatic Control.
Pablo A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming, 96(2):293-324 May 2003. ISSN 1436-4646. doi: 10. 10.10077/101077000-033355 URL 0ttp:::://0i10001111100/////1//0
0387-3
Robert Platt, Leslie Kaelbling, Tomas Lozano-Perez, and Russ Tedrake. Non-Gaussian belief space planning: Correctness and complexity. In 2012 IEEE International Conference Robotics and Automation, pp. 4711-4717, May 2012. doi: 10. 10.1109/CRA.200122222222
ISSN: 1050-4729.
Samuel Prentice and Nicholas Roy. The Belief Roadmap: Efficient Planning in Belief Space by Factoring the Covariance. The International Journal of Robotics Research, 28(1 1-12))11448 1465, November 2009. ISSN 0278-3649, doi: 10.1177/02783649099444888 1177 /ttp://....111171777822866999990
URL https! Publisher: SAGE Publications Ltd STM.
Sumeet Singh, Anirudha Majumdar, Jacques Slotine, and Marco Pavone. Robust online motion planning via contraction theory and convex optimization. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 5883-5890, May 2017. doi: 10.1109/ICRA.2017.
7989693.
12

---

Under review as a conference paper at ICLR 2023
D. C. Sorensen. Newton's Method with Model Trust-Region Modification, September 1980. ber: ANL-80-106 Publisher: Argonne National Laboratory.
Num-
Ioan A. Şucan, Mark Moll, and Lydia Kavraki. The Open Motion Planning Library. IEEE Robotics & Automation Magazine, (9)4)22--2, December 2012. doi: 10.1109/MAA
https://oms ompl. kavraki lab. ab.org.
Arun Sai Suggala and Praneeth Netrapalli. Online Non-Convex Learning: Following the Perturbed
Leader is Optimal. In Proceedings of the 31 International Conference on Algorithmic Learning Theory, pp. 845-861. PMLR, January 2020. URL fttt:s::/procee.ngs..... p.pess ISSN: 2640-3498.
v117 htl.//sggalalaa.aiag html
Jur van den Berg, Stephen Guy, Ming Lin, and Dinesh Manocha. Reciprocal n-Body Collision Avoidance. In Springer Tracts in Advanced Robotics, volume 70, pp. 3-19. April 2011. ISBN (06-3-642-19456-- doi: 10. in Advanced Robotics.
Journal Abbreviation: Springer Tracts
James Voss, Mikhail Belkin, and Luis Rademacher. The hidden convexity of spectral clustering, In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 1A pp. 2108-2114, Phoenix, Arizona, February 2016. AAAI Press.
Yong Xia. A Survey of Hidden Convex Optimization Journal of the Operations Research Society of China, 8:1-28, January 2020. doi: 10. 00110077440305--19400226655
Dingjiang Zhou, Zijian Wang, Saptarshi Bandyopadhyay, and Mac Schwager. Fast, On-line Collision Avoidance for Dynamic Vehicles Using Buffered Voronoi Cells. IEEE Robotics and Automa- tion Letters, 1(2):1047-1054, April 2017. ISSN 2377-3766. doi: 10. 10.10091LAA.201..2552222
Conference Name: IEEE Robotics and Automation Letters
Huiming Zhou, Path planning.
com zhm real www./ 2020.
13


Reviews:
[{"review_id": "wjk7eoTKRIV", "reviewer": "Reviewer_GFpG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies an online control setting where the online controller is encouraged to stay away from the obstacles. The authors consider a linear time-invariant system with time-invariant quadratic costs and the class of disturbance-action controllers. Despite the control costs that penalizes the state and control inputs in classic online control settings, the online controller also receives a reward based on its distance to the nearest obstacle. To compete against the clairvoyant optimal disturbance-action controller, the authors proposed a Follow-the-Perturbed-Leader type algorithm with an iterative subroutine that solves a sequence of trust region objectives. The main result is that the proposed algorithm achieves a sublinear regret bound against the clairvoyant optimal disturbance-action controller. The authors also used numerical simulations to demonstrate the effectiveness of the proposed algorithm.", "summary_of_the_review": "In summary, I think the setting and the algorithm in this paper will be interesting for the online control community. But my concern is that some parts of the problem setting (time-invariant LQR costs/dynamics and disturbance-action controller class) are relatively simple and many previous works on online control have already considered more general costs/dynamics/controllers, so the main results are not significant enough. Therefore, I would like to vote for a borderline accept.", "strength_and_weaknesses": "Strength:\n\nOnline control has received much attention recently and a limitation of previous works is that the sublinear regret guarantees usually relies on the convexity of the cost functions. It is good see the sublinear regret bound still holds for the obstacle avoidance problem, where the cost function is nonconvex (though it has a special form).\n\nWhile the FPL type of online control algorithm has been used in, e.g., Ghai et al. (2021), a novelty in Algorithm 1 is the iterative subroutine to compute (8). Unlike the settings in previous works, since the authors consider the minimum distance to any one of the obstacles, the optimization problem (8) is not a trust region problem, thus one cannot solve it directly.\n\nWeakness:\n\nMy first concern is about the controller class (or parameterization): It is unclear to me that the disturbance-action controller class is expressive enough for the task of obstacle avoidance. In my opinion, an alternative controller class like Model Predictive Control (MPC) provides more flexibility to avoid a set of moving obstacles, whose positions are not included in the historical disturbances that a disturbance-action controller can react on. Thus, my questions are: Is it possible to extend the analysis in this work to other controller classes like MPC? What is the main technical difficulty of doing the extension?\n\nI also have a concern about the necessity of introducing this specific setting of obstacle avoidance. Specifically, the setting in Agarwal et al. (2019) can already handle general convex stage cost functions. In contrast, if we incorporate the reward for avoiding obstacles into the original stage costs, the new stage costs still have a specific “quadratic” form though it is nonconvex. Therefore, my questions are: If we directly apply the online control algorithm in Agarwal et al. (2019) to nonconvex stage costs, do we expect a counterexample to show the regret will be much worse? If we solve the nonconvexity problem by some convex relaxation approach to the nonconvex stage costs, will the performance loss be significant?\n\nLastly, I have a slight concern about the way that the problem setting penalizes a direct “collision” with the obstacle. In many applications, I believe it is more natural to consider the obstacles as hard constraints and model them as a compact set rather than singletons. I think that might bring much technical difficulty to the proof, but I recommend the authors to add more discussion about the specific challenges, because I believe online control with hard constraints on states and inputs is an important open question.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "wTHRgv2KZc", "reviewer": "Reviewer_txHg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a novel method for obstacle avoidance by using online learning theory and provide regret bounds on this. The proposed method is claimed to be efficient, provides instance-optimalty to perturbations and compares favorably to baseline open-loop planning as well as a robust planning approach.\n", "summary_of_the_review": "This paper builds on recent work in online learning theory for control of linear systems, further extending it to the application of obstacle avoidance. The result seems rather narrow and technical as the assumptions of unconstrained linear systems do not seem like a great fit for obstacle avoidance. Even though the paper does compare against baseline planners from control/robotics, they do not appear to be strong ones (at least in the case of moving obstacles), and the experiments in particular are not convincing from an obstacle avoidance perspective. \n\nThat said, the paper is mostly well-written. Unfortunately, the main contribution, the provable regret bounds, is a six page proof unfortunately only found in an appendix. There is clearly a lot of work put into this, but it is difficult to evaluate its significance since it rests on assumptions that usually do not hold in the targeted application. From an obstacle avoidance perspective, it is unclear when this would actually be of use. I am willing to change my mind if somebody willing to champion the theoretical contributions on the online learning side. ", "strength_and_weaknesses": "Strengths:\n- Obstacle avoidance is an important area of robotics, and the proposed approach appears to be novel, based on some recent advances in online learning theory for linear systems\n- The paper is mostly well-written\n- The paper makes a good effort of citing related works on obstacle avoidance from control and robotics \n\nWeaknesses\n- Strong assumptions: From an obstacle avoidance perspective, the significance of the proposed approach is hampered by the assumption that the world is adequately modeled by unconstrained linear dynamics. Most robots have non-linear dynamics (e.g. cars), and especially control saturation constraints (e.g. they cannot generate infinite accelerations on demand). While the proposed approach provides provable bounds, it is not obvious how applicable these would be in practice.\n- Weak experiments/baselines: I like that the authors make an effort to compare against baselines from the control/robotics literature. However, worst-case approaches are pessimistic against highly dynamic obstacles like people, and open loop ones that ignore motion and uncertainty are of course very optimistic. Further, the performance of RRT* depends heavily on the number of samples, which is not shown to be sufficient for these experiments. A bigger issue is that the experiment environments appear very simple, and important details are unclear. i) The results across all environment types appear to be averaged together, but these are vastly different problems. To understand what is going on it would be helpful to report them separately. ii) On the experiment whit static obstacles, I do not understand why the RRT baseline would ever crash. iii) On the experiments with moving obstacles, is the random velocity assigned to them fixed at the start of the episode or does it change? iv) Are the obstacle velocities ever estimated and used as inputs of the baseline avoidance algorithms? Work on avoidance of moving obstacles in robotics typically includes estimated motion predictions, and focuses on finding real-time solutions (c.f. [1] and citing papers).  \n- The abstract claims this is an efficient approach, but in what way? It still collides 4-26% of the time, and it takes 5.6 seconds per time step to compute, which for obstacle avoidance systems seems potentially problematic. I suspect this again refers to the regret bound(?), but they do not really do a good job of showing how this is effective in the experiments. From an obstacle avoidance perspective, it is very unclear what benefit the proposed approach would provide.\n- The main contribution of the paper is the provable regret bound, but the proof is deferred to a six page section of the appendix. I understand extra space is sometimes needed for proofs, but this is the main result of the paper. \n\n[1] Wilkie, David, Jur Van Den Berg, and Dinesh Manocha. \"Generalized velocity obstacles.\" 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2009.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TtZstMwcedW", "reviewer": "Reviewer_vUNR", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the author formulated obstacle avoidance as a regret-minimization minimization problem and proposed a gradient-based online learning algorithm to solve it. The author theoretically shows the instance-optimality to perturbations. Compared with previous work, this paper does not rely on the a priori assumptions about whether the uncertainty is stochastic or adversarial and thus allows for more flexible behavior and adaptations. Finally, the authors demonstrate the experimental comparison with an open-loop planner, RRT*, and a worst-case planner, Hamilton-Jacobi (HJ) planner.", "summary_of_the_review": "First, the reviewer has not have much experience reviewing papers in the field of control theory. Thus some of the comments are subjected to small mistakes. Please correct me during the rebuttal phase if any of my statement (e.g., weakness) is not well-grounded. Thus, the final score of this paper will also be largely modified based on the comments and discussion from other reviewers after the rebuttal phase. ", "strength_and_weaknesses": "Strength:\n1. The author does not make any assumption on the distribution of uncertainty and proposes a more generic pipeline using regret optimization.\n2. The regret objective is well-formulated and an iterative algorithm based on Hidden-Convex is developed to solve it.\n3. Regret bound of the problem is given with theoretical proof. \n\nWeakness:\n1.It seems that the method part is very similar to the related work cited in the paper: Generating Adversarial Disturbances for Controller Verification. Could the author provide more clarification on this? \n2.Experimental comparison to RRT* seems not good: Even though the RRT* baseline is an oracle without partial observability, the visible region is still very large, which covers more than half of the obstacles. In this case, the naive RRT* (as mentioned in supp C1) can still outperform the proposed method by a large margin on the first task.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MdXiQ6LW-xC", "reviewer": "Reviewer_Mcwo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a method where a control policy, to simultaniously follow a nominal trajectory and to keep obstacles at a distance, is learned online as to adapt to the disturbance characteristic that is present for the given problem instance.\nAlgorithms for doing so are introduced and regret bounds are proven.\nThe approach is evaluated on four toy-environments with varying difficulties and chracteristic of the disturbance. The proposed method is shown to be competitive with a kinodynamic RRT* and a Hamilton-Jacobi reachability planner.", "summary_of_the_review": "The paper propose an interesting way to deal with obstacle avoidance for nominal trajectory tracking when much is unkown about the disturbances. Relevant proofs are provided and the approach is evaluated with competing methods while showing benefits in some regards over these. ", "strength_and_weaknesses": "Strength:\n* The approach is possible to analyze formally and certain guarantees as well as performance measures (i.e. regret bounds) are proven.\n* The approach is straight forward to integrate into motion planning achitectures and interface with a planner that produce a nominal trajectory. Even if the nominal trajectory is not collision free at plan time, then the proposed method will perform collision avoidance.\n\n\nWeaknesses:\n* The approach seem to be too slow for (soft) real-time performance with current hardware and potentially vary a lot in computation time? (5.6 seconds on average). Since collision avoidance is safety-critical in most applications, then an upper bound on time is usually enforced (after which it does not matter any more anyways). How does the approach deal with an upper bound on time (even if it is mostly finished before the bound is reached)? How will the approach perform if the horizon is reduced to reach 1hz (or stay below the upper bound with high probability)?\n* The problem formulation in (2) where the distance to obstacles is supposed to be minimized (with relative importance with nominal tracker error and control signal penalties) seem a bit simplistic and hard to tune. If it is desired that the probability of collision is less than say 10^-5 each second, then the only way is to achieve this is to reduce the penalties on the other terms which would then hold globally. However, the collision probability is time (and state)-dependent: It is less likely the further away, and it is less likely if the disturbance is less adverserial etc.. How would such safety constraints or considerations fit into your approach and/or extensions thereof?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "G4VROCpUpt", "reviewer": "Reviewer_YMGQ", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses the problem of safety assurance in terms of collision avoidance for a robotic system under uncertainty learned online. The key contribution of this work lies in the introduced online learning algorithm for safe control in the context of regret minimization, followed by the formal proof of the bounded regret and safety guarantee. Compared to other existing online learning for safe control frameworks, the proposed method relies on the setting of regret minimization to achieve instance-optimality, which allows for less conservative behaviors given the observed stochastic/non-stochastic disturbances in hindsight. Experimental results on a racing car simulation example are provided to demonstrate the effectiveness of the proposed algorithm.", "summary_of_the_review": "While the studied problem of online learning for safe control is interesting, the paper mainly follows the standard approach of non-convex memory FPL with incremental contribution in applying it to the collision avoidance scenario. On the other hand, the challenge of enforcing safety during learning, as studied in many existing work on safe learning, is not addressed in the paper. The results are also seem substandard given the lack of sufficient number of testing trials. Authors are encouraged to address the comments in the future version of the paper.", "strength_and_weaknesses": "Strength:\n\n+ The paper is generally well written with clear motivation and good overview about the high level idea of the algorithm.\n+ A good coverage of the related work in multiple relevant fields.\n+ The idea of contextualizing standard online non-convex FPL framework in robotic planning is interesting.\n \nWeakness:\n\n- The technical contribution seems rather incremental as the adapted non-convex memory FPL is a standard approach in many existing work.\n- For the target application of obstacle avoidance, there is no formal discussion or proofs in terms of the safety assurance.\n- As inherited from the existing non-convex memory FPL framework, most of the proofs are from existing work including the performance on the bounded regret, and it’s unclear what are the novel proofs beyond the existing work.\n- There is no comparison between the proposed method and other existing learning-based approaches.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject