Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 1: strong reject
review_content: 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.
strength_and_weaknesses: Strength:

+ The paper is generally well written with clear motivation and good overview about the high level idea of the algorithm.
+ A good coverage of the related work in multiple relevant fields.
+ The idea of contextualizing standard online non-convex FPL framework in robotic planning is interesting.
 
Weakness:

- The technical contribution seems rather incremental as the adapted non-convex memory FPL is a standard approach in many existing work.
- For the target application of obstacle avoidance, there is no formal discussion or proofs in terms of the safety assurance.
- 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.
- There is no comparison between the proposed method and other existing learning-based approaches.

clarity,_quality,_novelty_and_reproducibility: The studied problem of learning-enabled safe control with unmodelled uncertainty is an very interesting topic and has gained significant attention lately by the learning and control community. The paper is in overall well written to highlight the motivation, existing challenges, and the adapted approach of the non-convex memory FPL framework. With that being said, however, the presented framework seems to be a simple contextualization of the existing FPL framework, with incremental changes of the defined objective function to adapt to the collision avoidance problem. The main proofs of the bounded regret is natural unleashed from standard FPL framework, making the contribution too incremental. Please see detailed comments as follows.


- Contribution and Novelty: while the presented motivation is clear that focuses on episodic online learning for safe control to address unmodelled uncertainty, the reviewer feels the contribution is quite incremental, given that the Algorithm 1 mainly follows the standard non-convex memory FPL and it is difficult to see what is the additional challenge given the targeted application of collision avoidance. The main results of the bounded regret also directly comes from the one for FPL from [Ghai et al 2021, Agarwal et al 2019a, Hazan et al 2020].

- Quality: as a follow-up comment from above, the challenge of collision avoidance itself is not well addressed by the contextualized approach of FPL. For example, there has been extensive results on safe reinforcement learning for robotic control that requires high probability or zero violation of safety during both learning/exploration and execution. The interesting tension comes from how to enforce safety such as collision avoidance when the uncertainty is not fully modelled. In this paper, however, safety is simply embedded as a soft constraint in the objective function with all properties inherited from the low regret FPL, which may make it not applicable in the real world applications of safety-critical control.

- Experimental results: from the reported results, it seems the experiments are only performed with one or a small number of trials and thus makes the results questionable to well support the claimed advantages. On the other hand, there is no metrics that reflect the learning efficiency such as regret.

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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strength:
1. The author does not make any assumption on the distribution of uncertainty and proposes a more generic pipeline using regret optimization.
2. The regret objective is well-formulated and an iterative algorithm based on Hidden-Convex is developed to solve it.
3. Regret bound of the problem is given with theoretical proof. 

Weakness:
1.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? 
2.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.
clarity,_quality,_novelty_and_reproducibility: The author is well-organized with a clear structure. The related work is well-written, especially for readers (like me), who are not very familiar with the field of robust planning. One issue is that the experimental analysis is not enough to support the low-regret claim. And it seems that the major contribution (the non-convex memory FPL algorithm) mainly comes from previous work. The reviewer believes that the results of the experiment are reproducible. 
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
Algorithms for doing so are introduced and regret bounds are proven.
The 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.
strength_and_weaknesses: Strength:
* The approach is possible to analyze formally and certain guarantees as well as performance measures (i.e. regret bounds) are proven.
* 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.


Weaknesses:
* 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)?
* 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?
clarity,_quality,_novelty_and_reproducibility: The paper is fairly clear, but it is difficult to follow the more technical parts. Algorithm 2 has inputs that are not easily mapped to Eqn. 8 (vectors a_j and b for example)..

The quality and novelity seems high. Then again, I would not use neither RRT* (too slow) or HJ planning for dynamic obstacle avoidance (nominal trajectory tracking or otherwise), but rather learning-based MPC [1].

The reproducibility does not seem easy to me, but I am not as experienced in implementation of some of the technical aspects of the paper. Releasing the code upon accept is highly encouraged.

[1]  L. Hewing, K. P. Wabersich, M. Menner, and M. N. Zeilinger, “Learning‐based model predictive control: Toward safe learning in control,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 3, pp. 269–296, 2020.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:

Online 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).

While 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.

Weakness:

My 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?

I 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?

Lastly, 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.
clarity,_quality,_novelty_and_reproducibility: This paper is well-written and easy to follow in general, while I suggest the authors to expand Section 3.3 about the trust region optimization. Specifically, when can the optimization problem (6) be solved efficiently? Currently, the readers need to check the references to understand this part. As I discussed in my answer to the previous question, I think the main novelties of this work are the problem setting and the iterative subroutine to solve optimization problem (8).
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.

strength_and_weaknesses: Strengths:
- 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
- The paper is mostly well-written
- The paper makes a good effort of citing related works on obstacle avoidance from control and robotics 

Weaknesses
- 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.
- 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).  
- 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.
- 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. 

[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.
clarity,_quality,_novelty_and_reproducibility: The paper is mostly well-written. Some details mentioned above could be improved. Unfortunately, its main result is a proof in a six page appendix, which I did not carefully check for correctness.
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. 

That 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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: summary:
The paper extends FPL to a simplified obstacle avoidance setting. The approach is validated experimentally.

strengths:
- well written paper
- sound idea
- good literature overview

weaknesses:
- the proposed method is an extension of non-convex memory FPL for obstacle avoidance - the authors said in the rebuttal there is essentially no theoretical contribution (besides reducing the novel setting to a known one)
- the reviewers still think the considered assumptions/setting is too simplified for real world obstacle avoidance
- still doubts about RRT* baseline
justification_for_why_not_higher_score: After the rebuttal 2 reviewers argue strongly against this paper, 2 reviewers have a weak accept.
The rebuttal was helpful to calcify a lot of points about this paper, however the in this case highlighted more clearly that the proof is not a major contribution. Some of the reviewers still have doubts how limiting the assumptions will be to make it work in a real obstacle avoidance scenario.
Decision: Reject