Brian Axelrod
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Brian Axelrod has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Aaron Sidford
Stanford University
1 shared publication - Gregory Valiant
Stanford University Stanford University Stanford University
1 shared publication Leslie Kaelbling
1 shared publicationLeslie Pack Kaelbling
Massachusetts Institute of Technology, Cambridge, MA, USA
1 shared publicationLuke Shimanuki
Massachusetts Institute of Technology
1 shared publication- Luke Shimanuki
Optimus Ride, USA
1 shared publication
Latest Publications
- 15 December 2022
- Published by Springer Nature
- p. 68-84
Efficient Motion Planning Under Obstacle Uncertainty with Local Dependencies
- 15 December 2022
- Published by Springer Nature
- p. 68-84
Efficient Motion Planning Under Obstacle Uncertainty with Local Dependencies
- 18 February 2021
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 40 (10-11) , 1151-1166
Hardness of Motion Planning with Obstacle Uncertainty in Two Dimensions
We consider the problem of motion planning in the presence of uncertain obstacles, modeled as polytopes with Gaussian-distributed faces (PGDFs). A number of practical algorithms exist for motion planning in the presence of known obstacles by constructing a graph in configuration space, then efficiently searching the graph to find a collision-free path. We show that such an exact algorithm is unlikely to be practical in the domain with uncertain obstacles. In particular, we show that safe 2D motion planning among PGDF obstacles is -hard with respect to the number of obstacles, and remains -hard after being restricted to a graph. Our reduction is based on a path encoding of MAXQHORNSAT and uses the risk of collision with an obstacle to encode variable assignments and literal satisfactions. This implies that, unlike in the known case, planning under uncertainty is hard, even when given a graph containing the solution. We further show by reduction from -SAT that both safe 3D motion planning among PGDF obstacles and the related minimum constraint removal problem remain -hard even when restricted to cases where each obstacle overlaps with at most a constant number of other obstacles.- 18 February 2021
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 40 (10-11) , 1151-1166
Hardness of Motion Planning with Obstacle Uncertainty in Two Dimensions
We consider the problem of motion planning in the presence of uncertain obstacles, modeled as polytopes with Gaussian-distributed faces (PGDFs). A number of practical algorithms exist for motion planning in the presence of known obstacles by constructing a graph in configuration space, then efficiently searching the graph to find a collision-free path. We show that such an exact algorithm is unlikely to be practical in the domain with uncertain obstacles. In particular, we show that safe 2D motion planning among PGDF obstacles is -hard with respect to the number of obstacles, and remains -hard after being restricted to a graph. Our reduction is based on a path encoding of MAXQHORNSAT and uses the risk of collision with an obstacle to encode variable assignments and literal satisfactions. This implies that, unlike in the known case, planning under uncertainty is hard, even when given a graph containing the solution. We further show by reduction from -SAT that both safe 3D motion planning among PGDF obstacles and the related minimum constraint removal problem remain -hard even when restricted to cases where each obstacle overlaps with at most a constant number of other obstacles.- 8 May 2020
- Published by Springer Nature in Springer Proceedings in Advanced Robotics
- p. 852-867
Hardness of 3D Motion Planning Under Obstacle Uncertainty
- 8 May 2020
- Published by Springer Nature in Springer Proceedings in Advanced Robotics
- p. 852-867
Hardness of 3D Motion Planning Under Obstacle Uncertainty
- Open Access
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on $n$-elements with range $[-1, 1]$, computes an $\epsilon$-additive approximate minimizer in $\tilde{O}(n/\epsilon^2)$ oracle evaluations with high probability. This improves over the $\tilde{O}(n^{5/3}/\epsilon^2)$ oracle evaluation algorithm of Chakrabarty \etal~(STOC 2017) and the $\tilde{O}(n^{3/2}/\epsilon^2)$ oracle evaluation algorithm of Hamoudi \etal. Further, we leverage a generalization of this result to obtain efficient algorithms for minimizing a broad class of nonconvex functions. For any function $f$ with domain $[0, 1]^n$ that satisfies $\frac{\partial^2f}{\partial x_i \partial x_j} \le 0$ for all $i \neq j$ and is $L$-Lipschitz with respect to the $L^\infty$-norm we give an algorithm that computes an $\epsilon$-additive approximate minimizer with $\tilde{O}(n \cdot \mathrm{poly}(L/\epsilon))$ function evaluation with high probability.Open AccessNear-optimal Approximate Discrete and Continuous Submodular Function Minimization
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on $n$-elements with range $[-1, 1]$, computes an $\epsilon$-additive approximate minimizer in $\tilde{O}(n/\epsilon^2)$ oracle evaluations with high probability. This improves over the $\tilde{O}(n^{5/3}/\epsilon^2)$ oracle evaluation algorithm of Chakrabarty \etal~(STOC 2017) and the $\tilde{O}(n^{3/2}/\epsilon^2)$ oracle evaluation algorithm of Hamoudi \etal. Further, we leverage a generalization of this result to obtain efficient algorithms for minimizing a broad class of nonconvex functions. For any function $f$ with domain $[0, 1]^n$ that satisfies $\frac{\partial^2f}{\partial x_i \partial x_j} \le 0$ for all $i \neq j$ and is $L$-Lipschitz with respect to the $L^\infty$-norm we give an algorithm that computes an $\epsilon$-additive approximate minimizer with $\tilde{O}(n \cdot \mathrm{poly}(L/\epsilon))$ function evaluation with high probability. - Open Access
An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood
The log-concave maximum likelihood estimator (MLE) problem answers: for a set of points $X_1,...X_n \in \mathbb R^d$, which log-concave density maximizes their likelihood? We present a characterization of the log-concave MLE that leads to an algorithm with runtime $poly(n,d, \frac 1 \epsilon,r)$ to compute a log-concave distribution whose log-likelihood is at most $\epsilon$ less than that of the MLE, and $r$ is parameter of the problem that is bounded by the $\ell_2$ norm of the vector of log-likelihoods the MLE evaluated at $X_1,...,X_n$.Open AccessAn Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood
The log-concave maximum likelihood estimator (MLE) problem answers: for a set of points $X_1,...X_n \in \mathbb R^d$, which log-concave density maximizes their likelihood? We present a characterization of the log-concave MLE that leads to an algorithm with runtime $poly(n,d, \frac 1 \epsilon,r)$ to compute a log-concave distribution whose log-likelihood is at most $\epsilon$ less than that of the MLE, and $r$ is parameter of the problem that is bounded by the $\ell_2$ norm of the vector of log-likelihoods the MLE evaluated at $X_1,...,X_n$. - 7 June 2018
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 37 (13-14) , 1760-1774
Provably safe robot navigation with obstacle uncertainty
As drones and autonomous cars become more widespread, it is becoming increasingly important that robots can operate safely under realistic conditions. The noisy information fed into real systems means that robots must use estimates of the environment to plan navigation. Efficiently guaranteeing that the resulting motion plans are safe under these circumstances has proved difficult. We examine how to guarantee that a trajectory or policy has at most collision probability ( -safe) with only imperfect observations of the environment. We examine the implications of various mathematical formalisms of safety and arrive at a mathematical notion of safety of a long-term execution, even when conditioned on observational information. We explore the idea of shadows that generalize the notion of a confidence set to estimated shapes and present a theorem that allows us to understand the relationship between shadows and their classical statistical equivalents such as confidence and credible sets. We present efficient algorithms that use shadows to prove that trajectories or policies are safe with much tighter bounds than in previous work. Notably, the complexity of the environment does not affect our method’s ability to evaluate whether a trajectory or policy is safe. We then use these safety-checking methods to design a safe variant of the rapidly exploring random tree (RRT) planning algorithm.- 7 June 2018
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 37 (13-14) , 1760-1774
Provably safe robot navigation with obstacle uncertainty
As drones and autonomous cars become more widespread, it is becoming increasingly important that robots can operate safely under realistic conditions. The noisy information fed into real systems means that robots must use estimates of the environment to plan navigation. Efficiently guaranteeing that the resulting motion plans are safe under these circumstances has proved difficult. We examine how to guarantee that a trajectory or policy has at most collision probability ( -safe) with only imperfect observations of the environment. We examine the implications of various mathematical formalisms of safety and arrive at a mathematical notion of safety of a long-term execution, even when conditioned on observational information. We explore the idea of shadows that generalize the notion of a confidence set to estimated shapes and present a theorem that allows us to understand the relationship between shadows and their classical statistical equivalents such as confidence and credible sets. We present efficient algorithms that use shadows to prove that trajectories or policies are safe with much tighter bounds than in previous work. Notably, the complexity of the environment does not affect our method’s ability to evaluate whether a trajectory or policy is safe. We then use these safety-checking methods to design a safe variant of the rapidly exploring random tree (RRT) planning algorithm.- 12 July 2017
- Published by Robotics: Science and Systems Foundation
Provably Safe Robot Navigation with Obstacle Uncertainty
- 12 July 2017
- Published by Robotics: Science and Systems Foundation
Provably Safe Robot Navigation with Obstacle Uncertainty
- 1 May 2015
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (10504729) , 503-508
Reducing FPGA algorithm area by avoiding redundant computation
We develop a new paradigm for designing fully streaming, area-efficient FPGA implementations of common building blocks for vision algorithm. By focusing on avoiding redundant computation we achieve a reduction of one to two orders of magnitude reduction in design area utilization as compared to previous implementations. We demonstrate that our design works in practice by building five 325 frames per second, high resolution Harris corner detection cores onto a single FPGA.
- 1 May 2015
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (10504729) , 503-508
Reducing FPGA algorithm area by avoiding redundant computation
We develop a new paradigm for designing fully streaming, area-efficient FPGA implementations of common building blocks for vision algorithm. By focusing on avoiding redundant computation we achieve a reduction of one to two orders of magnitude reduction in design area utilization as compared to previous implementations. We demonstrate that our design works in practice by building five 325 frames per second, high resolution Harris corner detection cores onto a single FPGA.