Online Learning for Obstacle Avoidance
Authors: David Snyder
Meghan Booker
Nathaniel Simon
Wenhan Xia
Daniel Suo
Elad Hazan
Anirudha Majumdar
Venue: CoRL 2023 Poster (2023)
Keywords: Regret
Online
Learning
Convex
Optimization
Obstacle

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 realizations of uncertainty in the environment or a stationary stochastic model of uncertainty, we propose a method that is efficient to implement and provably grants instance-optimality with respect to perturbations of trajectories generated from an open-loop planner (in the sense of minimizing worst-case regret). The resulting policy 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. Further, it is implemented on a hardware example where a quadruped robot traverses a dense obstacle field and encounters input disturbances due to time delays, model uncertainty, and dynamics nonlinearities.

Online Learning for Obstacle Avoidance
David Snyder
Meghan Booker'
Nathaniel Simon'
Wenhan Xia 2.3
Daniel Suo 2.3
Elad Hazan 2.3 Anirudha Majumdar' 1,3
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 realizations of uncertainty the environment or stationary stochastic model of uncertainty, we propose a method that is efficient to implement and provably grants instance-optimality with respect to perturbations of trajectories generated from an open-loop planner (in the sense of minimizing worst-case regret). The resulting policy 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 dynamical system environment and compared to baseline open-loop planning and robust Hamilton- Jacobi reachability techniques. Further, implemented on hardware example where quadruped robot traverses dense obstacle field and encounters input disturbances due time delays, model uncertainty, and dynamics nonlinearities.
Keywords: Regret Minimization, Obstacle Avoidance, Online Learning
Introduction
The problem of obstacle avoidance in motion planning is fundamental and challenging task at the core of robotics and robot safety. Successfully solving the problem requires dealing with environments that are inherently uncertain and noisy: a robot must take into account uncertainty external disturbances and unmodeled effects, for example- - its own dynamics and those of other agents in the environment. Approaches for tackling the obstacle avoidance problem in robotics typically fall under two categories: (i) methods that attempt construct stochastic models of uncertainty in the agents' dynamics and use the resulting probabilistic models for planning policy learning, and (ii) methods that construct plans that take into account worst-case behavior. In Sec. we give a 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 a harder problem as an intermediate step." " Constructing accurate models of disturbances and agent dynamics is perhaps more complicated than the task of obstacle avoidance in motion planning, practical uncertainties rarely conform assumptions made by the two classes of approaches highlighted above. As an example, consider a quadruped robot navigating through an (a priori unknown) obstacle field subject to unmodeled dynamics and external disturbances in the input channel (Fig. 1). Constructing accurate probabilistic models of disturbance and obstacle variations challenging, and may cause the robot to violate safety out-of-distribution settings. contrast, worst-case assumptions may lead to extremely conservative behavior. This motivates the need for online learning methods that adapt the particular context encountered by the robot.
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 trust-region-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
"orrespooniig Author: dasnyder@ praiee@rrrinnntnnttii "Intelligent Robot Motion (IRoM) Lab, Princeton University. Department of Computer Science, Princcton University. GGoolle DeepMind.
7th Conference Robot Learning (CoRL. 2023), Atlanta, USA.

---

A* plan
OLC
Figure I: A quadruped robot tasked with traversing course with densely placed obstacles goal. During traversal, robot is subject sensor noise, time delays, input-channel disturbances, nonlinearities in closed-loop dynamics, which can render optimistic nominal plans (orange) unsafe. Our online learning control (OLC) algorithm (dashed pink) corrects for this to give a wider margin of erro when moving through the course.
hindsight from a given class of closed-loop policies. This type of theoretical performance guarantee flexibly adapt the behavior of the uncertainty in any instance of
nonstandard, and allows the obstacle avoidance problem without making priori assumptions about whether the uncertainty is stochastic adversarial. Further, the resulting method is computationally efficient. The method is applied to dense obstacle environments with complex unmodeled dynamics, and demonstrates improved performance where open-loop planners and overly-robust methods can respectively struggle. We additionally show the efficacy of our method with hardware demonstrations where a quadruped robot has navigate dense obstacle fields subject time delays and input-channel disturbances.
2 Related Work
Effective motion planning is central challenge within robotics of continuing and significant inter- est [1, 2, 3]. While planning is well-developed in deterministic settings, robustness remains major challenge in the presence of unmodeled uncertainty. Existing techniques typically fall into one of two categories: (i) methods that make assumptions on the distribution of uncertainty, or (ii) methods that assume worst-case disturbances. Below, we set our work within this context and discuss techniques from online learning: we will leverage the latter to develop our framework for obstacle avoidance.
Planning under uncertainty. A popular approach to account for uncertainty in motion planning to assume knowledge of the uncertainty distribution. One early method in this vein utilizes chance constraints to bound the probability of collision under stochastic uncertainty [4] and has been subsequently extended encompass many sources of stochastic uncertainty in robotics [5] [8]. Further development has utilized partially observable Markov decision processes (POMDPs) to account for state uncertainty [9] [12]. These approaches are able to provide strong guarantees on safety, albeit under generally restrictive assumptions on the uncertainty distribution (c.g.. i.i.d. Gaussian uncertainty); our approach does not assume knowledge of the distribution of uncertainty, yet provides regret bounds even in the presence of non- non-Gaussian and non-stationary noise.
Recently, learning-based planning techniques relying on domain randomization have demonstrated significant empirical success [13] [19] by specifying distribution of uncertainty over various simulation parameters to train robust policies. Combining this domain randomization with online identification of uncertain parameters has been proposed [20, 21]; however, despite these methods' empirical successes, they still rely on real-world environments being well-represented by the dis- tribution of uncertainty used in (relatively extensive) training. By contrast, our approach focuses on settings where it may be challenging to specify the uncertainty, and we do not require expensive training of policies in simulation provide theoretical guarantees in the form of bounded regret.

---

Reachabillty-basee robust planning. Hamilton- (HJ) Reachability- based [22, 23] and tra- jectory library-based (24, 25] robust planning techniques assume worst-case realization of uncertainty. As such, they provide adversarial certificates of safety for path planning problems via the construction of representations (or outer approximations) of the safe and unsafe regions of the state space condi- tional on the robot dynamics, obstacle placement, and disturbance size. This formalism is similar to related results in adaptive control [26, 27], which prove stability in the face of disturbances for specific planning controllers, even in the presence of certain non-convex obstacles. HJ methods, which generally suffer from the curse of dimensionality [28] (despite the existence of speed-ups in certain settings [29]), use the formalism of the differential game [30] to provide "global" notion of safe and unsafe sets [31]. In comparison, robust trajectory libraries, which are usually computed using convex programs [32], provide safety guarantees in the form of robust "tubes" or "funnels" [33, 25] that encompass only the nominal trajectory (or hypothesized trajectories) within the space.
Our work differs from these methods via guaranteeing "instance-opiimallyy"" namely, the regret mini- mization framework allows us to adapt to the specific nature of observed disturbances. Our method is effective in both stochastic and adversarial regimes, we do not sacrifice too much performance in "benign" environments to provide guaranteed robust performance in more adversarial cases.
Online learning for control. Our work makes significant use of online learning [34] to make guarantees on regret, which is the difference between the algorithm's performance and that of the best policy in hindsight (once disturbances are realized) from a given class of closed-loop policies. Several canonical control-theoretee results have recently been cast as problems in online learning [35, 36), providing interesting generalizations established control results like the linear-quadratic regulator [37, 38, 39] and Ho robust control [40]. Results in optimal sample complexity [41] and synthesis for unknown linear systems [42] illustrate further generalizations of standard control theory.
Standard control formulations are efficiently solvable due to a convex objective. However, "higher- level" decision-making tasks like obstacle avoidance often have non-convex objective functions (e.g., maximizing the distance to the nearest obstacle). Fortunately, some non-convex objectives admit "hidden convexity" - that they can be reformulated (via transformations, relaxations, or conversions to dual formulation see [43] for survey) into equivalent optimization problems that convex. This allows for efficient solutions (e.g., [44, 45, 46)) to problems that nominally would be hard to solve (e.g.. [47]). Our work gives such formulation for the task of obstacle avoidance.
3 Problem Formulation and Preliminaries
Consider a discrete-time dynamical system with state X and control input u A planning oracle (Xo) takes in an initial state and generates a nominal state trajectory with associated control inputs T= {x] ) Here, x E Rd= and u E Rdd, We design a robust obstacle avoidance controller that will update the trajectory online to avoid local obstacles. Intuitively, this is a faster "safety inner loop" for the slower trajectory planning stage O7, keeping the agent safe from external features. For analytical tractability, we assume that the dynamics of perturbations of the nominal trajectory are discrete-time linear. Defining x, X2 x and u, π, n., this assumption becomes
X++1 = Aox; Bu, + W.
(1)
where w, E dR is a bounded, unknown, possibly-adversarid disturbance For many practical systems the linear dynamics assumption is reasonable; one example is a control-affine system with feedback linearization. Additionally, w, can encompass small, unmodeled nonlinearities. Our task to construct this "residual" controller generating u, avoid obstacles. As such, O is the optimistic. goal-oriented planner (in practice, an off-the-shelf algorithm, e.g., [48]) and our controller is the safety mechanism that becomes active only when needed and in a provably effective manner.
'The results here are presented for linear time- innerinvariant (LTI) systems. Additionally, we present the case di.. = da. which affords the disturbances the most 'power": these results immediately extend to the inclusion of non-identity disturbance-te state matrix and du de in Eqn. 1.
3

---

3.1 Safety Controller Objective
A controller trying to avoid obstacles needs to maximize the distance to the nearest obstacle, subject to regularization of state deviations and control usage. Assume sensor mechanism that reports all "relevant" obstacle positions (e.g.. within a given radius of the agent). The optimization problem, for trajectory of length T, safety horizon of length L T, and obstacle positions PỘ denoting the jth sensed obstacle at time t, is
max (Ad, AEA
where:
Cots(A) = Σ min min ||x p/1l ||x,
|u, 1
rE(L]
Here, A is the set of online algorithms that choose actions for the controller, and x denotes the realized state trajectory conditioned actions n ~ A A. The last two terms represent quadratic state and action costs; these costs² very common objectives in the control literature, but serve primarily here to regularize the solution to the obstacle avoidance task. Note that, though the collision avoidance objective is relaxed, it remains a nonconvex quadratic penalty term rendered additionally complex due to the discrete selection over time and obstacle indices the minimal-distame obstacle in the first term of Cobs- From here, we model the optimal policy search in the online control paradigm [38]. This allows us to define the regret-based safety metric with respect the best achievable performance in hindsight. For a sufficiently powerful policy comparator class, achieve meaningful guarantees on the safety of the resulting controller.
3.2 Regret Framework for Obstacle Avoidance
Leveraging the class of linear dynamic controllers (LDCs) as comparators [40, 38), we use disturbance-action controller design, which combines state feedback with residual obstacle-avoidance:
H M
u = Kx + b. +
Σ E=1
w,-s-
Here, [i] indexes the history length and f denotes the time index of the decision. We rearrange the expression by moving the state feedback out of u, defining ü, Kx, and Á = Ao + BK. Then the system dynamics (Eqn. 1) are equivalently
x
Ax, + Bü;- + W.-
(4)
The comparator class II will be the class of LDCs parameterized by M; this class has provably expressive approximation characteristics [38]. The regret is defined using quantities from Eqn. 2:
(eg = sup
max Cots(M MEI
(5)
A sublinear bound on Eqn. 5 implies that the adaptive sequence M, selected by low-regret algorithm A will perform nearly as well as the best fixed policy M in hindsight, for all realizations of uncertainty within the system. Thus, sublinear regret bounds establish finite-time (near) optimality; the policy performs nearly as well as an optimal policy that has a priori knowledge of the realized disturbances.
3.3 Trust Region Optimization
To provide guarantees regret, the method presented in Sec. 4.2 will construct sequential trust region optimization instances. A trust region optimization problem [49] is nominally non-convex optimization problem that admits "hidden convexity". One can reformulate a trust region instance (see Def. 1) via a convex relaxation in order to solve efficiently [44, 50].
Here, we omit the fully general LQR costs (time varying Qe and Rt) for simplicity of presentation; however, the results show will also hold for this general setting.

---

Definition 1 (Trust Region Instance). A trust region instance is defined by tuple (P. D) with P g Rdxd, E Rd, and D > as the optimization problem
max 5
Pz P
(6)
Throughout the remainder of this paper, we will use "trust region instance" to refer interchangeably to instances of Def. I and the implicit, equivalent convex relaxation.
Methodology, Algorithm, and Regret Bound
4.1 Intuitive Decomposition of the OLC Algorithm Control Signal
The intuition of our control scheme is allow for online, optimization-bane feedback to correct for two key sources of failure in obstacle avoidance: (1) non-robust (risky) nominal plans, and (2) external disturbances. The former can be thought of as errors in planning that is, they arise when the nominal path is followed exactly. Paths that move very close to obstacles or that pass through them (e.g., due to sensor noise) would be examples of this problem. The presence of the bias term in the OLC framework accounts for control input to correct these errors. The latter challenge concerns deviation from nominal trajectories caused by errors modeling, time discretization, and physical disturbances. The linear feedback term in the OLC framework accounts for these errors.
4.2 Theoretical Method and Contributions
We utilize the "Follow the Perturbed Leader" (FPL) method [35] in tandem with optimization oracle [51, 52] from the online convex optimization [53] literature. In this area, [40] develops method to generate adversarial disturbances for linear systems online, and extends the FPL algorithm to the setting with memory. Further, [54] gives regret bounds for many game scenarios in which the players have varying cost landscapes. Several contributions of this paper lie in reductions: we show general-sum two-player
that optimizing Eqn. is equivalent to finding the equilibrium solution trust-region problem, and that both players have
game for which every control-player instance low-regret algorithms solve for the optimal policies. This allows to use the results in [54]. Additionally, show that extension to the multi-step setting in Eqn. remains trust region instance in 'lifted' game, allowing us to use the FPL results [52, 51, 40]).
4.3 Algorithm Exposition and Regret Bound
We formulate the obstacle avoidance controller as online non-convex FPL algorithm in Alg. 1. At time I, the agent generates a control input ú, via Eqn. by playing MM {M). The state dynamics are then propagated to reveal the new state X,+1, and the realized w, is reconstructed in hindsight from the state. The robot simultaneously uses its sensors to observe local obstacle positions.
The key conceptual step is then the following: given past reconstructed disturbances and obstacle locations, one can construct a instantaneous reward function (Eqn. 8) time + 1. This is function of a counterfactual set gains (M), where M and ü correspond to the state and control input that would have resulted from applying M given the realized disturbances, obstacle locations, and the initial state Xo. The key algorithmic step is solve for the optimum M,(1IH]] {M) in Eqn. which is the Follow-the-Perturee
component of the algorithm (M Po is the perturbation). The resulting sublinear regret bound is given in Thm. 2.
Theorem 2 (Regret Bound for Online Obstacle Avoidance). Consider an instance of Alg. 1, with Alg. 2 (see Supp. B) acting as subroutine optimizing Eqn. 9, Then the regret attained by Memory FPL will be
Ö(poly(C) (T)
(7)
where L. is measure of the instance complexity.
5

---

Algorithm Online Learning Control (OLC) for Obstacle Avoidance
Input: Observed obstacle positions {P 1K history length H = ()o
Input: Full horizon T, algorithm parameters {n, c, C),, initial state Xu-
Input: Open-loop plan: U. for T.
Initialize: Closed-loop correction M, [1: fixed perturbation Po ~ Exp(r))dxxHd
Initialize: Play randomly for {0. ..... H 1), observe rewards, states, noises, and obstacles. for t = H. until
do
Play M, 1 and observe state X and obstacles {pi+ 1 Reconstruct disturbance w, using observed X++1-
Construct the reward function in M:
le (M) = min ||x P4t1118 -11xf ||ū."112
(8)
jEj8]
Receive realized reward (++ (MM!-.H) Solve for 'perturbed leading policy" MH1 the solution to:
++1
arg max S
( + Po)
(9)
end for
5 Experiments
We demonstrate the effectiveness of our method in simulated and physical environments. The simulated environment in Sec. 5.1 considers 2D racing problem. The hardware experiments in Sec. 5.2 are conducted on Gol quadruped robot [55] avoiding obstacles the presence of unmodeled nonlinear dynamics, sensor noise, and time delays, shown in Fig. 1. In both settings, we demonstrate the benefits of our approach compared to baselines that use, resp., RRT*/A* (with replanning) for 'optimistic' path generation, and HJ reachability for robust planning. We illustrate how our method acts as an adaptive intermediary, providing a computationally tractable algorithm that nonetheless maintains improved safety properties relative to purely optimistic planners.
5.1 Simulation Experiments
Centerline Experiment overview. In the simulated environment, racing vehicle (using double integrator dynamics) observes all obstacles within a fixed sensor range (Fig. 2). The nominal dynamics are perturbed by disturbances with varying levels of structure (described further below). A "centerline" environment shown in Fig. is utilized to demonstrate key safety and adaptivity criteria. The nominal trajectory fixed be a straight path through obstacles, requiring the obstacle avoidance behavior to emerge via the online adaptation of Alg. For speed, the implementation the environment and algorithm set up JAX [56], using Deluca [57] framework for the control-theoretic simulation environment. Each simulation takes 1-2 minutes to
single CPU with H 10. T 1000.
Comparison with baselines. We utilize a HJ reachability planner [58] generate robust trajecto- ries, as well as kinodynamic RRT* implementation [59] to generate "optimistic" plans (replanned at Hz, with a path-following controller applied at 5 Hz). We demonstrate two key behaviors: (1)
better performance than HJ methods with respect to LQR costs when disturbances are "benign;" (2) better performance than RRT* when disturbances are adversarial, For each algorithm both stochastic ['Rand'] and non-stochastic (sinusoidal ['Sin'] and adversarial ['Adv') disturbance profiles are tested, and metrics for both the safety (number of collisions) and performance (L.QR state and input costs) are collected for runs spanning 50 centerline obstacles. Results are presented for each algorithm and disturbance profile in Table 1. For space considerations, figures illustrating trajectories of simulated runs referenced below are deferred to Supp. D.

---

Centerline Environment
Dist.
Rand
Sin
Adv
Initial Path
Plan
Seen
RRT
0.27 + 0.05
Unseen
0.60
1.00
1.00
OLC
0.51 + 0.09
0.49 + 0.13
1.57 + 0.65
(ours)
0.06
0.04
0.26
HJ Plan
0.55 = 0.05
0.59 + 0.14
1.01 + 0.03
0.00
0.00
0.00
Table I: Planner performance for each disturbance type. Costs are given in terms of linear-quadranl (LQ) costs (top) and fraction of failures (bottom). Best-perforning cases for each column are bold. LQ costs only computed for successful passes; such, RRT" is intentionally blank for two entries.
Figure 2: Centerline environment. The nominal path passes vertically through obstacles; the sensor range is denoted by the blue shaded region.
Several aspects of Table reflect the expected behavior of cach algorithm. RRT follows efficient paths, but fails to handle disturbances effectively, with high collision rate. Second, HJ paths are robust, but performance improvements are limited as 'adveraarialtty' is reduced, and the method does not adapt to disturbance structures. In particular, the sinusoid case incentivizes the racer to pass the obstacles on a specific side; the HJ planner passes on each side in equal proportion In contrast, OLC adapts to the structure of the sinusoidal disturbances to take the "easier route" with lower cost.
As shown in Table 1, OLC significantly reduces collisions across all disturbance profiles relative to RRT" planning, while also reducing control usage and state costs relative to HJ planners. This intermediate solution also provides computational speed-up to HJ, allowing it to be run more efficiently online and allow for feedback on sensory information (as opposed to the privileged map information that HJ requires in Sec. 5.2). Finally, OLC was tested on several other environments, including with dynamic obstacles for further details, see Supp. D.
5.2 Hardware Experiments
Experiment overview. For our hardware experiments, we use the Unitree Gol quadruped robot, shown in Fig. 1. The robot is equipped with LIDAR and an inertial measurement unit (IMU) which enable obstacle detection and localization using LIO-SAM [60]. The robot's task to traverse a dense course of cylindrical obstacles, while encountering time delays and residual, nonlinear dynamics. The plant is modeled as a Dubins' car; the equations of motion are included in Supp. C. The high-level inputs are then translated to joint-level torque commands by the robot's low-level controller. We note that the noisy estimates on hardware of both the state and the relative obstacle positions will further demonstrate the OLC algorithm's 's robustness to noise in the inputs to Alg. 1, including in the reconstructed disturbances and in the estimated state.
Controller architecture. All sensing and computation is performed onboard the robot. We use a Euclidean clustering algorithm for obstacle detection [61] based on the LIDAR measurements. This detection algorithm runs onboard the robot and provides updated obstacle locations to the controller in real time (not all obstacles initially sensed due occlusions and larger distances). At each replanning step, the robot generates a nominal set of waypoints from the estimated state and detected obstacles using an A algorithm [62] over a discretization of the traversable space, which is converted to a continuous path by a down- sammled smoothing spline. We then wrap the additional OLC feedback controller (H = 5, T = 40) of the form presented in Eqn. 3 using Alg. 1. The use of A' in lieu of RRT was undertaken to ensure smoother resulting paths for the quadruped. We justify the change by noting that due discretization A should only be equally or more robust than RRT (using equivalent margin), thereby reducing the apparent benefits of the OLC module.
Baselines.
We compare OLC with the baselines used for the simulated experiments (Sec. 5.1), substituting * for RRT* to improve speed and stability of the nominal planner. Concretely, the first baseline uses A# in receding horizon re- plaannnnnng scheme with the nominal dynamics model
7

---

and obstacle padding of 0.25m to account for the Gol's ss size. The robot executes the control inputs provided by the planner, replanning at Hz and taking actions at 4 Hz. The second baseline is a robust controller that is generated using Hamilton-Jacobi (HJ) reachability. This baseline is provided an a priori map of the obstacles, and uses provided model of the disturbances, taking into account velocity-dependent effects. This second baseline acts as a safety 'oracle.' with optimal trajectories synthesized offline from the true map. As before, demonstrate that our algorithm improves the safety of pure A (with margin) while providing shorter and more intuitive paths than HJ methods.
Metric
Path Length (m)
Max Deviation (m)
Collisions
Planner
A*
10.61 + 0.40
0.62 +: 0.33
12
Online (OLC)
10.59 + 0.41
0.63 + 0.28
7
HJ Plan
11.13 + 0.45
1.16 + 0.57
[simulated]
Table 2: Planner performance along several metrics for the hardware examples. We observe that our method ('Online') performs very similarly to A" in terms of path efficiency while reducing collisions by over 40%. Note that HJ methods choose significantly longer paths account for worst-case uncertainty; HJ was not on hardware and the optimal paths were calculated offline using the true obstacle positions.
We run physical experiments using A and OLC for 21 runs each, consisting of three trials over seven obstacle layouts (see the supplemental video and Supp. C for additional details). In each instance, the robot is required to traverse 10m forwards. For each layout, the optimal HJ path is analyzed offline; for all runs, a 'crash' is defined as any contact made with an obstacle. As shown in Table 2, HJ methods choose an overly-conservativ, route that is generally safe but inefficient. Conversely, A even with obstacle padding of 0.25m - does not sufficiently account for the disturbances, yielding significant rate of crashes. However, in contrast to HJ, A and OLC take significantly shorter paths (note that the shortest possible path is at minimum 10m in length). However, algorithm reduces the number of collisions by nearly half versus the naive obstacle-padee padeed A approach, a result significant at p 0.1 using Boschloo exact test (see Supp. C). Importantly, while OLC was run onboard the robot in real time, the HJ methods required several seconds for each computation of the backward reachable set, and could not be run online.
Results.
6 Conclusion and Limitations
We develop regret minimization framework for the problem of online 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, prove regret bounds that demonstrate that our obstacle avoidance policy is comparable the best policy in hindsight from given class of closed-loop policies. Simulation and hardware experiments demonstrate that our approach compares favorably with baselines in terms of computational efficiency and performance with varying disturbances and obstacle behaviors.
Some limitations that we hope to address in future work include the limited classes of applicable dynamics (though our hardware experiments apply the method to time-varying linear dynamies) and obstacle geometries. Additionally, the cost function does not have multi-time-step lookahead (i.c., MPC-like). Additional lookahead would yield better foresight in the planning stage and likely improve performance. Finally, because the algorithm relies on solutions to optimization problems that run real-time, ensuring stability of the optimization procedure and automating selection of hyperparameters (those used are satisficing but likely suboptimal) would be useful extensions that may further improve the runtime performance.
8

---

Acknowledgments
This work was partially funded by the NSF Career Award No. 2044149, Additionally, this material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGF-2039656. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the authors(s) and do not necessarily reflect the views of the National Science Foundation.
References
[T] S. M. LaValee. Planning Algorithms. Cambridge University Press, 2006.
[2] D. Gammell and M. P. Strub. Asymptotically optimal sampling-based motion planning methods. Annual Review of Control, Robotics, and Autonomous Systems, 4:295-318, 2021. 2021.
[3] Z. Kingston, M. Moll, and L. E. Kavraki. Sampling- methods for motion planning with constraints. Annual review of control, robotics, and autonomous systems, 1:159-185, 2018.
[4] A. Charnes and W. W. Cooper. Chance-Constrained Programming. Management Science, 6(1): 73-79, Oct. 1959. ISSN 0025-1909. doi: 1tt.:.0..//mmms..... URL https://doi. org/10. 1287 /tmsc/nscc..m///m/mmmmmm./////.m 6. 1.73.
[5] L. Blackmore, H. Li, and B. Williams. A probabilistic approach to optimal robust path planning with obstacles. In in Proceedings of the American Control Conference, 2006.
[6] N. E. Du Toit and W. Burdick. Probabilistic Collision Checking With Chance Constraints. IEEE Transactions on Robotics, 27(4):809-815, Aug. 2011. 1. ISSN 1941-0468. doi:10.1109/ TRO.201 1. 16190. Conference Name: IEBE Transactions Roboties.
[7] L. Janson, E. Schmerling, and M. Pavone. Monte Carlo motion planning for robot trajectory optimization under uncertainty. In Robotics Research: Volume 2, pages 343-361. Springer, 2017.
[8] S. Jha, V. Raman, D. Sadigh, and S. A. Seshia. Safe autonomy under perception uncertainty using chance-constrained temporal logic. Journal of Automated Reasoning, 60:43-62, 2018.
[9] L. P. Kaelbling, M. L. Littman, and A. Cassandra. Planning and acting partially observable stochastic domains. Artificial Intelligence, 101(1-2):99-134 May 1998. ISSN 00043702. doi: 10. 10.00166500043377000080003333333 URL https:://inkkin:::: wttighhubbeseeieeee.e. elsevier com/retrieve/ pi1/$5000337029000233..
[10] Prentice and N. Roy. The Belief Roadmap: Efficient Planning in Belief Space by Factoring the Covariance. The International Journal of Robotics Research, 18(111122:1448-111 Nov. 2009. ISSN 0278-3649 0278364909341659 Publisher: SAGE Publications Ltd STM.
URL https: :/do:::////////// org/10....111.1100 1177/
[11] R. Platt, L. Kaelbling, Lozano-Peres and Tedrake. Non-Gaussian belief space plan-
ning: Correctness and complexity. In 2012 IEEE International Conference Robotics and Automation, pages 471 1-4717, May 2012. doi: 1000000100//CAA2.222.2220000
ISSN: 1050-4729.
[12] H. Kurniawati. Partially observable markov decision processes and robotics. Annual Review of Control, Robotics, and Autonomous Systems, 5:253-277, 2022.
[13] F. Muratore, F. Ramos, G. Turk, W. Yu, M. Gienger, and J. Peters. Robot learning from randomized simulations: A review. arXiv preprint arXiv:21 2021.
[14] Tobin, R. Fong, A. Ray, Schneider, W. Zaremba, and Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RS/ international conference intelligent robots and systems (IROS), pages 23-30. IEEE, 2017.

---

[15] I. Akkaya, M. Andrychowicz, M. Chociej, M. Litwin, B. McGrew, A. Petron, A. Paino, M. Plappert, G. Powell, R. Ribas, et al. Solving rubik's cube with a robot hand. arXiv preprint 13Xiv:19/0007113, 2019.
[16] K.-C. Hsu, A. Z. Ren, D. P. Nguyen, A. Majumdar, and J. F. Fisac. con-to-lab-to-real Safe reinforcement learning with shielding and generalization guarantees. Artificial Intelligence, 314: 103811, 2023.
[17] F. Sadeghi and S. Levine. Cad2rl: Real single-image flight without single real image, arXiv preprint arXiv: 161 1.04201, 2016.
[18] X. B. Peng, M. Andrychowicz, W. Zaremba, and P. Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE international conference on robotics and automation (ICRA), pages 3803-3810. IEEE, 2018.
[19] G. B. Margolis and P. Agrawal. Walk these ways: Tuning robot control for generalization with multiplicity of behavior. arXiv preprint arXiv:2212.03258, 2022.
[20] A. Kumar, Z. Fu, D. Pathak, and J. Malik. Rma: Rapid motor adaptation for legged robots. arXiv preprint arXiv:2107.04034, 2021.
[21] T. Miki, J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter. Learning robust perceptive locomotion for quadrupedal robots in the wild. Science Robotics, 7(62):eabk2822, 2022.
[22] I. M. Mitchell and C. J. Tomlin. Overapproximating Reachable Sets by Hamilton-Jacobi Projections. Journal of Scientific Computing, ((()):323-466 Dec. 2003. ISSN 1573-7691.
URL https: /twii wwg..0.g///.. 1023 /A A 1025364227663.
[23] S. Bansal, M. Chen, S. Herbert, and C. J. Tomlin. Hamilton-Jacob reachability: A brief overview and recent advances. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages 2242-2253, Melhourne, Australia, Dec. 2017. IEEE Press. 1oi:10.1109/CII 2017.8263977. URL http:::::////o..or////// 1109/CDC. 2017 8263977.
[24] S. Singh, A. Majumdar, J.-J. Slotine, and M. Pavone. Robust online motion planning via contraction theory and convex optimization. In 20/7 IEEE International Conference on Robotics and Automation (ICRA), pages 5883-5890, May 2017. 00::0..10990CKA22177778666
[25] A. Majumdar and R. Tedrake. Funnel libraries for real-time robust feedback motion planning. The International Journal of Robotics Research, 36(8):947-982, 2017. doi: 10.1177/027836499177
URL https: htttpp://aoi..rgg11...11.
[26] C. K. Verginis and D. V. Dimarogonas. Adaptive robot navigation with collision avoidance subject to 2nd-order uncertain dynamics. Automatica, 123:109303, Jan. 2021. ISSN 0005- 1098. doi: 2101:00000...uummmiiiaa0....... sccbe///errta//p/////00002222220
URL httph: btttps://www.ett http://///wccceeeeeereeettt com/
[27] C. K. Verginis, D. V. Dimarogonas, and L. E. Kavraki. KDF: Kinodynamic Motion Planning via Geometric Sampling- -aasld Based Algorithms and Funnel Control. IEEE Transactions on Robotics,
Conference 39(2)978-9977, Apr. 2023. ISSN 1941-0468. doi: 10. 109.1190022222232208852
Name: IEEE Transactions Robotics.
[28] Darbon and S. Osher. Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere. Research the Mathemati- cal Sciences, 3(1):19, Sept. 2016. ISSN 2197-9847. doi:10. 000111111660000777-100000----11- URL https: //t::://ooii.. 10g/10..o/ 011.:011111/000000000-0000000000
10

---

[29] S. L. Herbert, M. Chen, S. Han, S. Bansal, J. F. Fisac, and C. J. Tomlin. FaSTrack: A modular framework for fast and guaranteed safe motion planning. In 2017 IEEE 56th Anmual Conference on Decision and Control (CDC), pages 1517-1522, Melbourne, Australia, Dec. 2017. IEEE Press. 100:100.100 276668777 URL htRps:tp://ddo 101r//0..000/CCC.. 2017 8263867.
[30] R. Isaacs. Difffrrnntial Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. Dover books on mathematics. Wiley, 1965. ISBN 978-0-471-42260-2. URL https: //woks////oooooe/e www.oooooooo.eee..oooooooooooooe www.cooomooc.eeee comm/bobtss.ddegtIlAAAAAAA
[31] I. Mitchell, A. Bayen, and C. Tomlin. A time-dependent CommitonnJJacoll formulation of
reachable sets for continuous dynamic games. IEEE Transactions on Automatic Control, 50 (7):947-957, July 2005. ISSN 1558-2523, 401100.100//AAC22055844499999 Conference Name: IEEE Transactions on Automatic Control.
[32] A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming, (6(2))2633-)333) May 2003. ISSN 1436-4646. 200:100.007//10107-00---0030
URL https://doi. org/ 10. 10t.:1000//111100 000107000000088/77
[33] R. R. Burridge, A. A. Rizzi, and D. E. Koditschek. Sequential Composition of Dynamically Dexterous Robot Behaviors. The International Journal of Roboties Research, 18(6):534 555, June 1999. ISSN 0278-3649, 112:0011777/027836999222200
URL https://doi. https://boi.orr//D. Publisher: SAGE Publications Ltd STM.
1177/02773364992266633
[34] E. Hazan et al. Introduction online convex optimization. Foundations and Trends@ in Optimization, 157-335 2016.
[35] Hannan. Approximation Bayes Risk in Repeated Play. In Approximation to Bayes Risk in Repeated Play, pages 97-140. Princeton University Press, 1958. ISBN 978-1-40888-11 doi: 11.1100.11111 1011 URL htw.h:tt//://tt https::/www..egruytter com/document/6oi/10 (516//9884400822111-0///mmmmmm
[36] N. Cesa-Bianchi and G. Lugosi Prediction, Learning, and Games. Cambridge University Press, 2006. 10. 0111:000007//80077155556565
[37] A. Cohen, A. Hasidim, T. Koren, N. Lazic, Y. Mansour, and K. Talwar. Online Linear Quadratic Control. In Proceedings of the 35th International Conference on Machine Learning, pages 1029- 1038. PMLR, July 2018. URL https://proceeddii ISSN: 2640-3498.
mlr. ppress/v0/ccohn
html.
[38] N. Agarwal, B. Bullins, E. Hazan, S. Kakade, and K. Singh. Online Control with Adversarial Disturbances. In Proceedings of the 36th International Conference on Machine Learning, pages 111-119. PMLR, May 2019, URL html. ISSN: 2640-3498.
mlr. wwt.tppresss///ppeeeeee http:///aaaaaaa1aaa
[39] N. Agarwal, E. Hazan, and K. Singh. Logarithmic Regret for Online Con- trol. In Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL https: http::/papppeaeeemm 187781111a2df0117666100335511111 Abwtratt..t.tt...........aaaa... html.
[40] U. Ghai, D. Snyder, A. Majumdar, and Hazan. Generating Adversarial Disturbances for Controller Verification. In Proceedings of the 3rd Conference on Leurning for Dynumics and Control, pages 1192-1204. PMLR, May 2021. URL attps://proceeding mlr aalrppe presss v144/ 2/44/ghai21a. html. ISSN: 2640-3498.
[41] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu. On the Sample Complexity of the Linear Quadratic Regulator. Foundations of Computational Mathematics, 20(4):633-679, Aug. 2020. ISSN 1615-3375. URL attps://resolvet caltech, edtuCCaltochAUTHORSS 20190806 1307 Number: 4 Publisher: Springer.

---

[42] E. Hazan, S. Kakade, and K. Singh. The Nonstochastic Control Problem. In Proceedings of the
st International Conference on Algorithmic Learning Theory, pages 408-421. PMLR, Jan.
2020. URL attps://prooceeddngs memiiinngnmmrrll....mmmm wwt.smml.................mmmmmre wwwpppeeesss/sappeeeeee
html. ISSN: 2640-3498.
[43] Y. Xia. A Survey of Hidden Convex Optimization. Journal of the Operations Research Society of China, 8:1-28, Jan. 2020. doi: 1100:00000//40305-01--000022
[44] A. Ben-Tal and M. Teboulle. Hidden convexity in some nonconvex quadratically constrained quadratic programming, Mathematical Programmingg 72(1):51 Jan. 1996. ISSN 1436-4646. doi: 10011000007/BF0252333.1 URL https:///bii.org///// 1tw.
[45] H. Konno and T. Kuno. Multiplicative Programming Problems. In R. Horst and P. M. Pardalos, editors, Handbook of Global Optimization, Nonconvex Optimization and Its Applications, pages 369-405. Springer US, Boston, MA, 1995. ISBN 978-1-4615-2025- doi:10. 1007/ 978- 178-1-4615-2025-22 8. URL https://doi. org/10 1007/978- 1-11--2-------2
[46] J. Voss, M. Belkin, and L.. Rademacher: The hidden convexity of spectral clustering. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI' 16, pages 2108 2114, Phoenix, Arizona, Feb. 2016. AAAI Press.
[47] T. Matsui. NP-hardness of linear multiplicative programming and related problems. Journal of Global Optimization, 922:113-119, Sept. 1996. ISSN 1573-2916. doi: 1001100.000//FF00116555
URL https: orgooo///// 1111111.... 101010000001000 /B07/BF0022658.
[48] A. Şucan, Moll, and I.. Kavraki. The Open Motion Planning Library. IEEE Robotics
& Automation Magazine, 19(4):72-82, December 2012. 110.1.1100//MAA222222225555 http::///mmll.avrakk///a
org.
[49] D. C. Sorensen. Newton's Method with a Model Trust-Region Modification, Sept. 1980. URL https://digital. librrryy....... unt. edw.b.k: / Number: ANL-80- 106 Publisher: Argonne National Laboratory.
[50] F. Hazan and T. Koren. A linear-time algorithm for trust region problems. Mathematical Programming, 156(1)333,338, 2016.
[51] N. Agarwal, A. Gonen, and E. Hazan. Learning in non-convex games with an optimization oracle. In Conference Learning Theory, pages 18-29. PMLR, 2019.
[52] A. S. Suggala and P. Netrapalli. Online Non-Convex Learning: Following the Perturbed Leader Optimal. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, pages 845-861. PMIR, Jan, 2020. URL httpps://proceeddiggge mll. paal..press/v11// suggala20a. html. ISSN: 2640-3498.
[53] E. Hazan. Introduction to Online Convex Optimization. Dec. 2021. URL htttt://aaxiiii h/tp://rrxxvor//////// aba/1900.000 arXiv: 1909.05207.
[54] E. Hazan. Approximate Convex Optimization by Online Game Playing. arXiv:cs/0610119, Oct. 2006. URL http::/arxivv www.//////////oo httgg/abss////6/11/// arXiv: cs/0610119.
[55] Unitree. unitreerobotics, 2023. URL http:p////ggttttb...ommmmeeeeeee
[56] J. Bradbbry, R. Frostig, P. Hawkins, J. Johnson, C. Leary, Maclaurin G. Necula, A. Paszke,
J. VanderPlas, S. Wanderman-Miin Milne, and Q Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
com/ jax.
[57] Gradu, J. Hallman, D. Suo, A. Yu, N. Agarwal, U. Ghai, Singh, C. Zhang, A. Majumdar, and E. Hazan. Deluca-a differentiable control library: Environments, methods, and benchmark- ing. Differentiable Computer Vision, Graphics, and Physics in Machine Learning (Neurips 2020 Workshop), 2020.
12

---

[58] S. ASL. Hj-reachability in http:///gghthiioooo/a/aaaaraellr 2021.
[59] H. Zhou. Path planning. http::///tttthh.ccmmmmaarsass/as
2020.
[60] T. Shan, B. Englot, D. Meyers, W. Wang, C. Ratti, and R. Daniela. Lio-sam: Tightly-couled lidar inertial odometry via smoothing and mapping. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5135-5142. IEEE, 2020.
[61] S. Sun. Lidar obstacle detector, 12 2021. URL citeaccle_dtecctin
[62] P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, 1968. 1ww.11000/ssc..198.000010010
URL https://aoi.oor//100/ 1109/tss.s 19w.es......33300 300136.
[63] J. Kivinen and M. K. Warmuth. Exponentiated gradient versus gradient descent for linear predic- tors. Information and Computation, 132(1):1-63, 1997. ISSN 0890-5401. hwwt://///ttttt//oioooooo///////
199.2662... URL https: htww///www..oo/./ooo....e.// http://wcccccceeeaeecccco///o//r 508905401969926277.
13

---

A Full Regret Proof
A.0 Outline of Proof
1. Reduce path planner to linear dynamical systems model
2. Demonstrate that general instance of Alg. is trust region problem
3. Reduce Eqn. 9 in Alg. to instance of Alg. 2
4. Justify necessary analogous quantities in problem to those of the proofs in [40, 38]
5. Apply the results for Nonconvex FPL with Memory from [40] Alg. obtain the regret bound
A.1 Reduction of Path Planned case to Standard Controls case
Assume that the planner devises nominal path (denoted with a (7) notation) in coordinates x and inputs u: so the path is fully specified as P {x], u, J Assume that the path chosen so that every x on or near the path, the following dynamics hold around perturbations of the path:
A(x x B(u-- up-1) Dw;-1-
(10)
Using this change of coordinates, can essentially negate the path and study the relevant perturbation dynamics dx,- := Xx xi and ou, :- u, u. we recover the desired equation:
8x:- = Aox, + Bōu;-1 + Dw:-1-
(11)
For shorthand, we will define represent perturbations from the nominal path. Intuitively, this is reasonable model for 'quasi-static' systems (e.g., drone car or aircraft using path planning for non-aggressive maneuvers).
8x and u ou ease exposition, remembering that they
A.2
Algorithm 2 is Trust Region Solver
The proof that Alg. 2 a trust region solver is given in Supp. B.1- B.3.
A.3
Algorithm Solves Equation
The proof that Eqn. 9 is special instance of admissible arguments Alg. 2 shown in Supp. B.4.
A.4
Technical Notes
A.4.1
Continuity and Conditioning Parameters
We begin with an analysis of the Lipschitz constant for the approximate cost functions (this will follow a similar path to [40]).
First, note that the diameter of the decision set 2DM and that the gradient of the quadratic cost above is V &
pT) m p. As such,
== max ( m.t
max [[1 |PIl [|p]
< 2Hd RD R
We consider as well bound the conditioning number of the optimization problem. Because the size of the optimization grows linearly in time, the condition number grows at most linearly as well. Therefore, the run-time of the algorithm is polynomial (neither the condition number nor the dimension grows too rapidly).
Finally, note bounds on the elements of P and p in the trust region instance. The bounds on costs, states, inputs, and disturbances together imply that the elements of P. are bounded by C2 and the clements of p bounded by C2 (this again follows [40]).
14

---

A.4.2 Truncated State Approximation
The idea of this proof follows directly from [40]; however, we show the proof in detail because in the truncated state history affects the resulting vectors a, in the optimization, leading to different instantiation of the problem.
To give a sense of the added subtlety for obstacle avoidance, observe that in certain scenarios, small perturbations in the observed relative obstacle positions could yield large changes in the optimal policy. For example, imagine that there one obstacle, located directly on the centerline of the nominal planned motion. Then small perturbation of the obstacle the right makes the optimal action "Left," " while small perturbation of the obstacle to the left makes the optimal action "Right."
This phenomenon is not problem the regret outline because, while the optimal decision is fragile, the loss incurred of choosing incorrectly is bounded by the quadratic (and therefore, continuous) nature of the cost functions themselves.
For the dynamics and control we have assumed that
T++1 = Ax, - Bu, + Dw:
u, = Kx; + b, + M.W.
(12)
= Kx; + Σ w
where the bias is included by one me-padding the disturbance vector. For simplicity we will omit the explicit bias from ensuing analysis; in all cases it can be understood to be incorporated into the measured disturbance. We can then show (as in [40]) that the state can be expressed as the sum of disturbance-to-ssttte transfer function matrices Me.::
2H
A X
H A
V We-i, where
k=0
Ā = A+ BK and
1, = D1 - H + Σ
A
(1,.., H)).
j=0
We define the state estimate and cost
28
Yt+1 = Σ
Vr, W:
1=0
4 H*) = ca 1 (M H:), ū.)
where ü, M.w, (the residual input on top of the closed-loop controller).
Now, assume that ||||| 1 - y. that ||A ||-||, ||DII, |||||| 3, and that for all t it holds that ||w/|| I Cw, || < Cu. and ||l || Rell S &. Then we can show that the approximation error of the costs sufficiently small. Let the condition number be defined as k = || A-
A.4.3 Bounding the States Along a Trajectory
Note that ú, M,w,; this implies that [| I HDC,. This implies further that |üū + Dwell S 23H DCw by the triangle inequality, Assuming that there exists such that
| 212 2,3
7
we have that for every t > H+T+1, |x - S 23H.D... (WLOG, we can assume the initial state Xg bounded in this domain that is, that the assumptioo satisfied with 0: the region defined above is the long-term reachable set of the state x, driven by bounded disturbances w, and (implicitly bounded) residual inputs ú, [the norm is limited by the stability parameter y of the closed-loop A-matrix]).
15

---

A.4.4 Bounding the Change in Costs
Now, we analyze the change in costs
lee (x ūt) - (M, Ha)l
Imin JEpp
||y + B....
min JE
|ر, + B.W.
Noting the definition of م and of aj,a, we can bound the difference between them function of the error in approximation of x (see [40]):
agt == Pj. Xt
ag.t aj = (Pitt - x1) - -(pj. xx)
Xt X1
= |āيز - ag,t112 = =1|xe- - &ell2
Now, we argue that the loss incurred due to the noise in X₁ is less than simply twice the change in cost due to the error in åz.t. Let jr == arg minje(n) f|l,,, BM, (12) Let j be defined analogously. If = j. then the difference in cost is less than or equal to the extra loss incurred by the error in å. then it is possible that the true 'binding obstacle' was biased away, and that the 'guessed' binding obstacle was 'biased towards'; therefore, the cost error is possibly due to deviations up to twice the error in the åيي vectors. This means that, defining & such that ||0,|12 X/ 2. we have that the following holds:
A = (x/4 ū.) Le :x)1 = |min |ay, + BM. min|la,, + B.W.W.1.. 5Ebp
jE(p]
{ll(ā,+ + +.00 + 11 1 + BMW [13]
max 2::1
= = + 255 āz, 25% (BM...
S 1101112 2(C + 11..112)166 2118,
= =3 + + 16.111 Mrr
$ 502116ell2+22 + +C 11::12
550k2gge-1t (1 + Mw)C)))
Letting H = -T log C55+ BD CT))], we have that
A <
T
16

---

Remark 3. Recursive Definition of H and Czi
Currently, there is a recursive nature to the definition of and C.: H == log C5k²Cz(1 + (DC and C2 == 28HDC. However, this is not problematic because the definitions will have a solution (that can be found efficiently); namely:
H 2 < log (c2Cx)
C2 = k
H log (02k1H)
And for any c1, C2, k1 E RK and fixed T >> O, there exists positive integer H such that the above result holds (e.g,, following from the fact that log H = H)) Further, the resulting H will not be too large wrt T for sufficiently large T (e.g., large enough T to overcome the constants).
A.5
Finalizing the Regret Bound
A.5.1
Apply Nonconvex Memory Follow-the-eertubee--Laaddd
This result is from [40], Theorem 13 (Corollary 14 gives equivalent result to our setting in the asymptotic regret behavior, optimal choice of n and differs slightly).
A.5.2 Completing the Bound
Finally, we use Alg. (which acts as an efficient c-oracle) with an approximate trust region imple- mentation of our desired optimization problem (Alg. 2) acting as a subroutine, in order to compose the regret components into a complete bound.
T
T Σ
Regret(A) = max Men
(a (((M))
ce(27, ū.())
t=
1=
Cn
Cn
Σ
(JMM, M, M,....M M)
7
Σ
(J((Mi-ma)) +
MEll
T
1=H
(13)
T Σ
max
1,M,M ..., M)
Je(M-HH.) m::) + O(lgg
MEll
1=
1=
<
<Óppoly(C)VT
To clarify the steps: the second line incorporates the approximation error from Section A.4.2 (which logarithmic in as noted in the third line) and the final line follows from the Nonconvex Memory FPL result of [40].
17

---

B Convex-Concave Game: Algorithm and Correctness
For completeness and easier reference, we include a copy of Alg. I below. To improve clarity, references to equations within this section (Supp. B) will use their numbering as given in Supp. B, rather than in the main text. The key technical results of this section are demonstrate: (1) that Alg. is trust region instance that be solved efficiently, and (2) that the optimization procedure in Eqn. 15 is solved correctly and efficiently by the trust region procedure Alg. 2. Given these results, obstacle avoidance algorithm will be computationally efficient and attain low regret.
Algorithm 1 Online Learning Control (OLC) for Obstacle Avoidance
Input: Observed obstacle positions {pt | history length И = T)og
Input: Full horizon T, algorithm parameters {n, e, AJ, initial state Xo-
Input: Open-loop plan: uy for t I....T.
Initialize: Closed-loop correction MM [1: fixed perturbation Po Exp(r)).xHdd
Initialize: Play randomly for {0, .... H 1}, observe rewards, states, noises, and obstacles.
for t == H... 1 do
Play M, 1:H]] and observe state X and obstacles {p'+1IsEMMl
Reconstruct disturbance w, using observed Xx+1-
Construct the reward function in M:
( min { ||x P1+111 jEl
||x | 11.
(14)
Receive realized reward 44+1 (M.().H)) Solve for 'perturbed leading policy" M/1li
(1:M)
the solution to:
++1
arg max M
Σ (MT)+ A Po)
(15)
end for
Algorithm 2 (General) Hidden-Convex Formulation for Objective in Eqn.
Input: Set of vectors [a k.H -j= matrix B, vectors b, bo, time history He S Input: Iterations N, learning n, approx. error e, perturbation Po. diameter DM- Initialize: Vector c/-l R r I...., He. for n=O...N do (1) Solve for Mn
H.
M, = arg max
C, (1 BMB b1 1
D
(16)
|bb]] BMb
11 1.f82-I-bbll || + X(M Po)
(2) Update Cn-1
[r]
II - Ae
noo (E, el,.elonm (00 YT (1...,,, H.). (17)
n+1
end for return M
18

---

B.1 Non-convex Memory FPL for Obstacle Avoidance
Intuitively, Alg. I operates by updating the gain matrices M via counterfactual reasoning: in hindsight, given the actual observed disturbances and obstacle locations, what gain matrices would have resulted good performance (in terms of obstacle avoidance and the state-input penalties)? In Supp. A, we demonstrate that this algorithm results in low regret as formalized in Eqn. 5 of the main text. For reference: Eqn. 9 (main text) corresponds to Eqn. 15 (Supp. B) henceforth; similarly, Eqn. 8 (main text) corresponds to Eqn. 14 (Supp. B).
B.2 Efficient Solution of Eqn. 15 (Part 1): Reduction of Alg. 2 to Trust Region Instance
We now prove that Alg. does indeed solve Eqn. 9. Consider the relaxed optimization problem
max MEM
ΣΣ
br rl lay
BM
(18)
We will first describe some useful quantities and pphysically-motvvaae assumptions. The physical quantities of interest have the following characteristics: x Rd,, u E R and w Rd=
Assumption B E TRd xd., with dyg S dgs and rank (B) = du- This corresponds the following physical assumptions: (I) there are no more inputs than states, and (2) there are no 'extraneous' inputs (if there are such imputs, then we can find minimal realization of B and wlog set extraneous inputs to always be zero). Similarly, if (1) fails, then setting them equal to zero uniformly (just as in (2)).
remove extraneous inputs by again
The dimension of several other variables of interest are: I Hdw and for the decision variable M, M E x We want show that the optimization in Eqn. 18 is equivalent to a convex trust region problem, which is efficiently solvable.
Further, let the quantity BT B have a singular value decomposition denoted by:
B"B=UU UU. AU.
We see that this decomposition has an orthogonal U E Rd.xdd and positive definite A because rank(B)= dy and thus the symmetric B" B Rdd xd. has Bdd B >
Now, consider the problem of Eqn. 18, assuming that VT E {l....,, Ht,, there are fixed ||r] e Ap. B, {a [r) & , bl), For now, choose a single time element, notated as [t]. For simplicity, will only include this notation at the beginning and end, where sum the result back together. We rearrange the objective for this case follows:
OBJ OBJ partial
1911a + BMb 11
Σ My(ay + BMM) (ay + BMb)
Easaaaay a, + 22 BMb+ bJ B
BJ BMB)
E Mb Mb +b
Here, we are searching for the argmax M", so the a a, is irrelevant. Further, we have defined of a B. Now, let M, = UM, and decompose M, [mf mT; :m.. The optimization
19

---

objective is now:
OBJ partial
Agllay + BMb
1222c Mb + b' AUMb)
Σ 1,(2 Mb. b AM,
= [v(22 + bb M AM
The last simplification follows from the fact that Σ, = 1 (because À E Ad,). Now, using our knowledge of the diagonal nature of A and the column partition of My, see that
du of m
M AM,
Substituting into the OPT formulation, we can further simplify all the way to the desired form:
OBJpariial
Σ d >illa
BMb
E 11(of Mb)] + AM,
Σ X1e2f Mb) + +b² Σ
o
}b
j=1
Σ M12CTUU + Σ
=
==1
du
= 2 Σ Ao Σ m b)]
Σ
وf m
bb T m,)
j=1
Σ (2 Σ \²
my)
mf "
m T Pm + p" m.
where is vector concatenation of the transposed rows of M,. Now, combine the results time, utilizing the convexity-preservinn property of function addition, simply reintroduce the (il-indexing and sum:
OBJ O purtial
Σ
Ea + BMM
= =m² pisl m + (p 1 m
OBJ = ΣΣ 2111 laafi + BMb
Σ m" pl m + (p m
= -
m Pm Pm+ppm
Once we solve for m² using a trust region solver, we unpack into M and get M = UT U (UM*) M²) desired. Further, we can translate a norm bound M into an equivalent one on m (at least, for appropriate choice of norm bound e.g., the Frobenius norm M becomes the 2-norm m).
20

---

B.3 Solving the FPL Sub-Problem
In order to feasibly engage the obstacle avoidance algorithm, is necessary to solve for optimal solutions to the objective Equ. 15, which is an instance the following max-min problem:
L+1 min |a + BMB l + BMb
arg max | MM
Mb A(M Po),
where a// B, (b]) blrl depend on the dynamics (Eqn. 4, main text) and the obstacle locations. The resulting algorithm is shown in Alg. 2, which converges to M [1:41 in Eqn. 15 of Alg. 1.
++1
Finally, we need to demonstrate that Alg. 2 will converge to pair {cN, My that corresponds to the optimal solution Eqn. 15. This follows immediately from Theorem 7, Part II of [54]. We have an instance of a repeated game in which an optimization oracle efficiently solves Eqn. 16, and then the low-regret exponentiated gradient algorithm [63] iteratively updates Cn (Eqn. 17). Again,
utilize the fact that the operation of function addition preserves, respectively, the convexity and concavity properties of pairs of operand functions as a necessary tool to allow for the results to still hold when applying the summation over time steps.
B.4 Efficient Solution of Eqn. 15 (Part 2): Reduction of Obstacle Avoidance to Alg. 2
This proof works as a reduction, where we show that the obstacle avoidance problem (Eqn. 15) constitutes a particular set of inputs to the general formulation Alg. 2. Recall that at time the algorithm A has access the state trajectory (x,] 14 JT=I, the disturbance history {w, } and the sets of sensed obstacles {p:
For any {H, ..., t). the loss function can be written of Alg. 2. Specifically, let a = Ax,-1 + Dw,-1 p b, W--H:r-1- bo.- 1 Dw--1- Then, for an appropriate C, E Ak.. the optimization problems are equivalent. Concatenating over the r-formulations, we have an instance of Eqn. 16. Specifically, for some choice of c, we will have an equivalent problem as Eqn. 15; here is an encoding unknown priori the relevant (nearest) obstacles at each time step.
instance
21

---

C Hardware Experiment Details
C.1 Equations of Motion
The equations of motion for the high-level Gol control are:
F++1
22
ccos v
0
Wxx1
Mt+1
9t sin 3
Ug
+
Wytt
(19)
0 1
Mug
where is the commanded forward velocity and up is the commanded yaw rate, The disturbances Wz, Wy and we capture unmodeled disturbances including imperfect velocity tracking by the robot's low-level controller and deviations due to localization noise.
C.2 Boschloo Test for Significance
In order evaluate the improvement of OLC A' in our hardware experiments, perform Boschloo Exact Test the outcomes of the experiment. This test (for our purposes) essentially provides a statistical evaluation of the difference in means of two Bernoulli variables in the small-data regime. In our experiments, we have a 2x2 test matrix in which OLC and A are each run 21 times, with the number failures random variable depending on each algorithm's ' behavior subject to the realized obstacle layouts. While we do not claim that our distribution of layouts exactly matches 'true distribution in the world,' believe be similar enough such that the statistic should be meaningful here.
To be precise, the statistic encapsulates the probability, in the null hypothesis that the two means are equal (or that one mean is greater), of achieving small sample of realizations that is more extreme than that observed in the true data. By choosing the alternative hypothesis "collision rate of A is higher," a significant result (say, at a 10% a 5% significance) would mean that we reject the null hypothesis. This, then, would provide evidence that the of OLC meaningfully reduced the collision rate.
Using the existing scipy implementation (scipy.stats. boschloo peaschloo_exact),, we find that for the data presented in Table 2, the test statistic is 0.1073 with p = 0.074, indicating significance at a = 0.1 not a = 0.05. Though not conclusive, this provides reasonable evidence that the reported improvement the collision rate is not due random chance in the obstacle layout realizations.
C.3
Obstacle Layouts
We provide bird's eye view of the layout configurations used during the experiments in Figure 3. Additionally see the supplementary video for the physical instantiation of the layouts used in the experiments.
22

---

Layout 1: Domino
Layout Diagonal
Layout Random
(ml
0
30
10
(m)
x (m)
(m)
Leyout 4: Random 2
Leyout 5: Rendom
Layout 6: Occluded Otatacle
0P0
8
O
10
10
Layout Tight Diamond
Figure Obstacle layouts from bird's eye view used during experiments. Obstacles are denoted by the circles. The quadruped was placed at (0, 0) and tasked with traversing 10m in the the x direction.
23

---

D Simulation Details and Resources
D.1 Simulation Implementation: Parameters, Setup, and Runtime
In this section, report the hyperparameters used for the experiments results in the main text. We implemented our algorithm and environments in JAX. All experiments were carried out on single CPU in minutes.
We set the full horizon to 100 and the history length to 10. For random perturbation across environments, we sample noise from Gaussian distribution with mean and standard deviation 0.5. For directional perturbation, random seed of 0 is used for all experiments. We obtain the nominal control from LQR with Q set to 0,001 and R set to 1. We then learn the residual obstacle- parameter M via gradient descent. The learning rate of gradient descent is 0,008 in the centerline environment and is 0.001 for the other environments.
sample Gaussian noise with mean 0.5 and standard deviation 0.5. A
An important note for these experiments: we do not implement existing heuristic techniques like obstacle padding improve the RRT collision-avoidance performance. As such, this performance not meant suggest that RRT cannot work robustly in these settings, only that its nominal (and theoretically grounded) form does not account for disturbances or uncertainty and is therefore "optimistic" as compared to HJ methods, etc.
D.2
Additional Figures and Trajectories - CCeneelline Environment
This appendix includes sample trajectories and other relevant visualizations for each algorithm.
D.2.1
RRT /
Here, we demonstrate some sample paths for RRT in each disturbance regime. Fig. 4 shows uniform random noise, Fig. 5 shows sinusoidal noise, and Fig. shows adversarial noise. In each case, the shift at the final time (goal position, top of image) causing horizontal shift in the path should be ignored.
Actual Path
Actual Path
50
30
20
10
-10
-5
-10
10
Figure 4: RRT* Planner trajectories against uniform random disturbances. Obstacle the gray sphere, with the nominal trajectory a dashed black (vertical) line.
24

---

Actual Path
Actual Path
50
50
20
20
10
10
Figure RRT" Planner trajectories against sinusoidal disturbances. Obstacle the gray sphere, with
nominal trajectory a dashed black (vertical) line.
Actual Path
Actual Path
50
30
20
10
-10
-10
10
Figure 6: RRT Planner trajectories against adversarial disturbances. Obstacle is the gray sphere, with the nominal trajectory dashed black (vertical) line.
Figure 7: Racer backwards reachable set (inside thick black line) and the obstacle (dashed black line).
D.2.2 HJ Reachability Planner
For the centerline example, the HJ Reachability planner constructs in Fig. the Backwards-reachal set for given obstacle (dashed line), subject to the dynamics constraints imposed on the racer.
25

---

Note that every positive-value region denotes an unsafe region. The interpretation is that there is "pseudo-cone" in front of the obstacle from which the vehicle cannot escape hitting the obstacle if the disturbances are sufficiently adversarial. Note that this means that HJ planning is independent the actual disturbances. For each of the disturbance patterns (random, sinusoid, adversarial), we plot collapsed view of sample trajectories around an obstacle for the HJ planner Fig. 8. Note how similar each plot is, due to this independence of the control from the actual observed disturbances.
D.2.3 Online Learned Planner
The key illustration here is that the trajectories of the online planner follow the structure of the disturbances, as illustrated by the following comparison of the uniform random and sinusoidal disturbances Fig. and Fig. 10.
Centerline Trajectortes
Centerline Teajectories
Centeeline Tejjecoriis
Deviaton 0x
Deviation (.X
Figure 8: Planner trajectories against (L. uniform random, (C) sinusoid, and (R) adversarial disturbances. Obstacles are black spheres, with the nominal trajectory a dashed black (vertical) line.
Trajectories for Online Planner [Rand]
Trajectories for Online Planner [Sin]
10
-00
-25
-3.0
-2.5
04
2.5
5.0
255
10.0
-103
-7.5
-5.0
-2.5
0.5
2.5
5.0
75
100
X (m)
(mr)
Figure 9: Collapsed trajectories of the racer using the online planner with random disturbances. The racer passes each side evenly.
Figure 10: Collapsed trajectories of the racer using the online planner with sin disturbances. The racer leams pass the right.
26

---

D.3 Experiment Details: Dynamic Pedestrian Environment
The pedestrian environment comprises many dynamic obstacles moving through the Racer scene, in which the Racer must avoid collision (contact). In this setting, the robot is not given direct obstacle state information, but must act instead on history observations each (visible) obstacle's position only. The difficulty of the instances of this setting are illustrated in the following figures, which highlight several particular instances of success and collision respectively within the experiments conducted.
Racer
3.0mg
Figure 11: (L. Non-crash sequence of still images in which OLC successfully avoids a set of 4 close obstacles; (R) Crash sequence of images in which OLC cannot avoid crash with of 6 close obstacles.
We note several important details for the simulations. The pedestrians are non-avoiding, and in some cases move nearly as fast as the simulated Racer agent; the majority of collisions are observed due to a combination of (1) local density of pedestrians, (2) high relative speed of at least pedestrians, and (3) non-avoiding nature of the pedestrian trajectories. These environments are more dynamic and chaotic than most the related literature, as they are intended to demonstrate 'proof-of-coneept; not to rigorously compare the many available baselines (the comparison in static environments allows for more interpretable cases that highlight the relative advantages of stochastic (e.g., RRT), adversarial (e.g., HJ), and hybrid (e.g., OLC) methodologies. respectively). We think that adaptation to moving obstacles is very natural future work, and possibly valuable point of future development for our algorithm.
D.4 Failures in the Slalom Setting
We include an image of the four major environments in Fig. 12. Our simulated performance was strong in all environments except for the slalom environment, which we discuss further below.
The "slalom" setting allows us to tune its difficulty by varying the x-position (i.e. offset) of the gates or by narrowing their width. Fig. 13 illustrates the effect of increasing gate offset from center (i.e., error in the nominal planned trajectory x-axis) and decreasing gate width (i.e., greater sensitivity to disturbances y-axis) on failure rate through the slalom gates. As expected, reduced gate width
27

---

random
centerline
pedestrian
slalom
100
80
(mm)
-40
40
-40
-20
20
-40
40
(mm)
Figure 12: Illustration of the four environments used as proof-of-coneeee for our Online algorithm.
and increased offset broadly increase failure rates. This is due to the online planner being forced to overcome poor nominal planned trajectory; in combination with the gated passageways, this requires very precise sequences of inputs and a longer memory of previously observed gates (due to the limited sensing horizon). This is discussed further in Supp. D.4.1.
D.4.1 Discussion
The first answer is relatively direct: in all of our examples, we are implicitly acting in a kind of Frenet frame, where all obstacle positions and other referencing is to the ego vehicle (racer) position. As such, the nominal planned trajectory can always be thought of as mapped to a straight line ahead of the racer. In this context, some slalom gates represent 20m deviation from the nominal trajectory. However, this flies in the face of the central modeling intuition of the online framework that obstacle avoidance is local, with local sensing, local deviations from the nominal trajectory, and "reactive" control to disturbances as they arise. In this vein, the nominal slalom is challenging task, precisely because it stretches the limits of what can be met by our setup. Concretely: limited sensing makes each slalom wall a kind of "gradient-less" observation (shifting left and right yields only a continuation the wall unless the gap is already sensed), meaning that choosing the correct Left/Right action is difficult. Additionally, the map displays memory, because going the wrong way early through one gate render the next gate infeasible.
It is in light of these considerations that we argue that the slalom case is actually a case for our model, because it interpretably creates a setting in which the key assumptions are broken. Just like an actual skier who overshoots through one gate and cannot recover for the next gate, so too does our obstacle avoidance algorithm run the risk of "dooming" itself due to a wrong turn but this is, as described, fundamental to the hardness of the obstacle avoidance problem! As such, we consider the slalom gate fundamentally hard problem, and consider case for future work fuller characterization of how our planner works for slaloms of varying difficulty, as measured by the sensor range, the distance between gates (both laterally and longitudinally), and the fundamental "cost memory" as it depends on these and other parameters.
D.4.2 Experimental Parameter Sweep - Slalom Course
In an effort to better represent the effects of the slalom setting and the dependence on gate width and offset, Fig. 13 illustrates the effect of increasing gate offset from center (i.e., error in the nominal planner trajectory x-axis) and decreasing gate width (i.e., greater sensitivity to disturbances y-axis) on failure rate through the slalom gates. As expected, reduced gate width and increased offset broadly increase failure rates.
We note that for narrow gates, a zero-offset slalom is actually quite challenging to ensure we believe this is due to the fundamental Hos limit of stabilization of disturbances for this system; namely, too-narrow gate requires too-strong robustness about the setpoint (origin), causing failure. This also explains why failure rates high but not one for moderate offsets in the narrow-gate environment as well: specifically, they allow some freedom away from the zero-offset regularization problem.
28

---

Fraction of collisions Gate Width (y) and Gate Offset (x)
0.9
Width of gate (m)
0.7
0.5
0.3
11
10
12
Gate Offset (m)
Figure 13:
Failure rate heatmap for increasing gate offset (left right) and decreasing gale width (bottom top). expected, failure increases with narrower gates (top) and larger offsets (right).
Besides this, the trend quite clearly demonstrates the fundamental increases in difficulty observed for narrower gates and larger offsets, as expected.
29


Reviews:
[{"review_id": "r-uJTW1-5x", "reviewer": "Reviewer_DrfS", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper presents an online learning approach to robust obstacle avoidance in the presence of unmodelled system dynamics and environmental perturbations. The proposed algorithm performs online trust-region optimization of a linear dynamic controller using an obstacle margin loss regularized by perturbations to the nominal plan, to ensure robustness while straying as little as possible from the nominal plan.", "summary_of_recommendation": "Overall this seems like a strong paper, though there is room for improvement in the technical presentation, and in the explanation of the algorithm. If they can be resolved satisfactorily, I would be happy to revise my recommendation.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Sufficient demonstration on hardware", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "Please respond to the questions under the detailed comments above.\n* How sensitive is the algorithm to accurate estimation of the disturbances $w_t$?\n", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review Summary\nOverall the problem is well-motivated, and the problem well set up. There are a couple of unclear sections in the technical presentation (see below), but overall the approach seems both correct and reasonable. The empirical results are good.\n\nDetailed Comments\n* The symbol $A$ seems to be overloaded: in eq. 2, it is the controller, and in eq.1, it is the state transition matrix. Is this correct? \n* In Section 4.3, it is unclear what the connection between the optimization in eq. 9 and FPL is. It seems to just be a trust-region (potentially nonlinear, non-convex) optimization problem. What algorithm is used? If a local optimization solver is used, how is the solution initialized? \n* It seems that the horizon $H$ should be carefully chosen to be long enough to allow for observability of unmodelled dynamics at all times, while minimizing it for computational tractability. Is this true? How is it chosen?\n* The switching of planning algorithms between sim and real is odd - why not try both RRT* and A* in both sim and real, as baselines?\n* The robustness of both A* and RRT* is dependent on the margin, as identified in the paper. However, this can affect the planner's ability to find narrow paths - it would be nice to highlight this empirically and compare it to the proposed approach.", "extra_scores": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning."}, "extra_text": {}}, {"review_id": "HhSKup59rh1", "reviewer": "Reviewer_63fg", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper presents an algorithm for robot navigation with obstacle avoidance. \nThe algorithm is robust against uncertainties and perturbations and adapts online, also to local obstacle sensing.  \nTheoretical results are provided and extensive simulation and experimental results are conducted. ", "summary_of_recommendation": "I believe the paper presents a strong algorithm for navigation and collision avoidance, but modifications are needed based on contribution, literature, and clarity. ", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Sufficient demonstration on hardware", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "- Please clarify the theoretical contribution wrt previous works, especially [38,52]\n- Please include adaptive-control works in the related literature, like the ones suggested.\n- Please clarify details of the proposed algorithm as per my comments above\n", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The topic addressed is significant and very relevant to robotics and the proposed algorithm seems promising.\nThe paper adapts an algorithm combining previous works ([38]+[52]) for obstacle avoidance. Therefore, the theoretical contribution needs to be clarified here - this is also due to the fact that it is not explained what exactly these previous works do. \n\nThe related-work part does not seem complete; there are more works than ones that probabilistic model - based and worst-behaviour-based. For example, the adaptive control works by Dimarogonas group: \n\nVerginis and Dimarogonas. \"Adaptive robot navigation with collision avoidance subject to 2nd-order uncertain dynamics.\" Automatica, 2021.\nVerginis, Dimarogonas, and  Kavraki. \"Kdf: Kinodynamic motion planning via geometric sampling-based algorithms and funnel control.\" IEEE Transactions on robotics, 2022.\n\nthat adapt online to uncertainties and disturbances. \n\nThe proposed algorithm further needs some clarification. For instance, what exactly tilde{M} is and how are the corresponding x and u (with tilde{M} superscripts) rigorously defined. Is the Initialize procedure in Alg. 1 executed offline in some simulation environment? Because it requires runs of the system to observe the several properties.    \n\nSimilarly, some more details throughout the paper can be provided, such as how is (4) exactly derived from (1)-(3), what exactly is the FPL methods, or what [38,52] consider.\n\nReferences to the supplementary material should be avoided (like see Supp. B in Theorem 2) and the picture references in the experiments. \n\nI understand the space limit (also with respect to my comment on more clarifications) and that a lot of information is in the appendices, but the paper needs to be compact in that sense. \n\n\n\n\n\n\n\n\n ", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed."}, "extra_text": {}}, {"review_id": "6IjsewjTrFI", "reviewer": "Reviewer_x84o", "summary": "", "questions": "", "limitations": "", "rating": 2, "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": "The paper frames the robot obstacle avoidance problem from the viewpoint of online learning. The policy adapts online to uncertainty and is shown in hindsight to be provably comparable to the best obstacle avoidance policy (from a restricted class). The method is validated in simulation and compares favorably to baselines (open loop planning and Hamilton-Jacobi reachability). It is also implemented on a hardware example. ", "summary_of_recommendation": "This paper has some nice aspects but is not significant enough to be published at CoRL. ", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Relevant but unlikely to deploy to hardware in near future", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "Since my main negative comment about the work is its significance, I'd appreciate hearing why the authors think pursuing this problem is worthwhile. A second, less important issue is the comparison with existing methods. Most obstacle avoidance on real systems is never done open loop. Can the authors provide a comparison with 1. a reactive system and 2. a setting in which obstacles are dynamic? \n", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Strengths: The paper makes a novel technical contribution in that it a. poses the obstacle avoidance problem in a regret minimization framework and b. develops a trust region-based online learning algorithm for obstacle avoidance with provable bounds. The paper is clearly written and easy to understand. \n\nWeaknesses: Modern robots have many failings. However, running into things is not high on the list. When we live in an era of driverless cars that have driven on public roads for millions of miles without a collision, it is questionable whether stationary obstacle avoidance is a significant enough problem to warrant an attack. I am (largely) on board with this paper in terms of its intellectual contributions, but I am not convinced it is solving a significant or important problem. A further limitation is that the comparisons are made with a narrow class of baselines and only in a setting where the obstacles are stationary. \n", "extra_scores": {"impact": "1: Not very relevant to the robot learning community."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Scores:    DrfS: Weak Accept   x84o: Weak Reject,   63fg: Weak Accept

Quality: The paper presents an online learning algorithm for obstacle avoidance in robot navigation. The resulting policy is robust against uncertainties and perturbations and  in hindsight is provably comparable to the best obstacle avoidance policy (from a restricted class). Theoretical results are provided and extensive simulation and experimental results are conducted. All reviewers  have acknowledged that the paper presents a strong algorithm and is well executed.

Clarity: The paper is clear and well organized.

Originality: Good. The paper makes a novel technical contributions by formulating  the obstacle avoidance problem in a regret minimization framework and by developing a trust region-based online learning algorithm with provable bounds, which  is important for safety considerations.

Significance: As online obstacle avoidance algorithm with guaranteed safety bounds are rare, this paper provides a significant contribution.

Cons:

- the significance of the provided method in comparsion with other more data-driven, obstacle avoidance algorithm is not entirely clear

Pros:

- adaptive online obstacle avoidance algorithm (including dynamic obstacles) with policy safety certification (regret minimization)
- algorithm is robust against uncertainties and perturbations
- theoretical results are provided and extensive simulations and hardware experiments are conducted
Decision: Accept (Poster)