From NLVO to NAO: Reactive Robot Navigation using Velocity and Acceleration Obstacles

Asher Stern; Zvi Shiller

REVIEW 3 major objections 7 minor 10 references

From NLVO to NAO: Reactive Robot Navigation using Velocity and Acceleration Obstacles

T0 review · 3 major / 7 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper extends velocity and nonlinear velocity obstacles from velocity space to acceleration space, letting a robot choose a constant acceleration outside the Nonlinear Acceleration Obstacle (NAO) to guarantee collision-free motion…

desk verdict NAO is a clean extension of the AO idea, and the core math is sound, but the multi-robot and efficiency claims outrun the evidence. read the letter →

arxiv 2506.06255 v1 pith:CZO6MPSV submitted 2025-06-06 cs.RO

Asher Stern , Zvi Shiller This is my paper

classification cs.RO

keywords velocityobstaclenonlinearaccelerationcollisionavoidancereactivenavigationmulti-robotdynamicenvironments

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

To plan a robot's motion reactively in a dynamic environment, this paper moves the classical velocity-obstacle idea from velocity space into acceleration space. It defines the Acceleration Obstacle (AO) for obstacles moving with constant acceleration, and the Nonlinear Acceleration Obstacle (NAO) for obstacles following arbitrary curved trajectories. The NAO is the union, over all future times, of constant accelerations of the robot that would put it at the obstacle's predicted position at that time. If the robot can pick an acceleration outside every obstacle's NAO, within its acceleration limits, that acceleration is collision-free as long as the obstacle keeps its predicted trajectory. The paper argues this yields smooth driving with fewer adjustments than velocity-based methods, and demonstrates it in multi-lane roundabout scenarios.

What carries the argument

The central object is the Nonlinear Acceleration Obstacle (NAO): the set of constant robot accelerations that would collide with an obstacle moving on a predicted curved path. It is built from temporal slices, each obtained by a homothety (a time-dependent scaling) of the obstacle's geometry into acceleration space around the robot's initial velocity, then taking the union over all future times. The robot's current velocity enters as a shift term $\frac{2v_A(t_0)}{t}$, so the NAO shape depends on the robot's own state, unlike the velocity obstacle. The AO is the special case for obstacles with constant acceleration, and the NAO generalizes it to arbitrary trajectories.

What would settle it

Run the roundabout scenario with one vehicle that abruptly changes its acceleration (for example hard braking) between replanning steps; if the NAO-selected acceleration leads to a collision, the prediction assumption is what failed. A cleaner test: compare NAO and AO on identical curved-road traffic, counting the number of replanning adjustments and collisions, to see whether the NAO's fewer adjustments hold.

Watch

Extended reading notes

Core claim

For an obstacle moving along an arbitrary trajectory $c(t)$, the paper derives the set of constant accelerations of the robot that would cause collision at some future time $t$. Setting the robot's second-order motion $v_A(t_0)t + \frac{1}{2} a_A t^2$ equal to the obstacle's swept set $c(t)\oplus B$ and solving for $a_A$ gives a temporal slice $NAO(t) = \frac{2B}{t^2} \oplus \left(\frac{2c(t)}{t^2} - \frac{2v_A(t_0)}{t}\right)$. The full NAO is the union of these slices over all $t > t_0$. Selecting an acceleration outside the NAO at each replanning step avoids the obstacle for the prediction horizon; the same construction with $c(t)$ replaced by $c(t_0)+v_B t + \frac{1}{2} a_B t^2$ gives the AO for linearly accelerating obstacles. Geometrically both are warped cones in acceleration space, and for a bounded trajectory the NAO converges to the origin as $t\to\infty$.

Load-bearing premise

The avoidance guarantee rests on the predicted obstacle trajectory staying valid until the next replanning step; if an obstacle changes its acceleration, an acceleration chosen outside the NAO can become a colliding one.

Editorial extensions

If this is right

For obstacles on curved or circular trajectories, the NAO removes false collision alarms that a linear velocity obstacle would create, so the robot avoids unnecessary braking or acceleration changes.
Using acceleration as the control variable lets the robot respect its own velocity and acceleration limits directly, producing smooth maneuvers rather than piecewise-constant velocity changes.
The same NAO algorithm can be run by every robot in a multi-robot scene, giving each robot a reactive collision-avoidance law without a central coordinator.
Because the NAO is a union of time-indexed slices, it can be recomputed at every replanning step in real time, which the paper demonstrates in a 30-vehicle roundabout.
The construction extends to three-dimensional and higher state spaces, so drones and air vehicles could use the same acceleration-space avoidance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If obstacle trajectories are uncertain, the NAO's guarantee degrades; one testable extension is to widen each temporal slice by the predicted trajectory's uncertainty, generating a probabilistic NAO instead of a deterministic one.
The NAO's shape depends on the robot's current velocity, which suggests hysteresis or oscillation behavior could be analyzed by tracking how the chosen acceleration moves relative to the moving cone boundary over replanning cycles.
The roundabout results imply a direct comparison metric: count the number of acceleration changes (or total control effort) for NAO versus AO on the same traffic, which would quantify the paper's claim of fewer adjustments.
The same time-scaling construction can be applied to other control spaces, such as jerk or steering-rate space, for vehicles whose dynamics are third-order.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version. The useful contribution is Eq. (25): extending the acceleration obstacle to arbitrary obstacle trajectories c(t) by the same homothety argument used in NLVO. That is a natural, correct definition, and the paper presents it clearly. The AO part is not new — [8] and [5] already did acceleration obstacles, and the authors admit it. So the real novelty is NAO, plus the observation about how the AO/NAO shape depends on initial velocity (e.g., straight cone at zero relative velocity), which is stated rather than proved.

The derivations in Eqs. (17)–(25) check out under the stated assumptions. For one robot avoiding obstacles whose future trajectories are fixed, choosing an acceleration outside the temporal union of NAOs is a valid sufficient condition. No fitted parameters, no hidden normalization; that part is honest. The roundabout examples are suggestive, and the comparison to AO in Fig. 11 is plausible, but this is not a real experiment: no parameters, no code, no quantitative metrics, no repeated trials. So the “efficiency” claim (fewer adjustments) is unproven.

The bigger soft spot is the multi-robot claim. The abstract says multi-robot navigation is achieved by all robots using the same algorithm, predicting each other's trajectories from current velocity and acceleration. But Section V explicitly limits the guarantee to “as long as the obstacle maintains its current trajectory.” If every robot replans at each time step, the obstacle trajectories change at the replan times, so the condition is violated by the algorithm itself. That is not an external prediction-error caveat; it is an internal mismatch between claimed capability and stated assumption. The examples don't help: Figures 10–12 involve passive or lane-constrained vehicles, not multiple agents all running the same NAO replanner. A proof for reciprocal replanning, or a two-robot mutual-avoidance demo, would be needed before the multi-robot statement is credible.

Citations are fine. The authors cite the relevant AO works and distinguish their own contribution. The writing is clear, though the abstract oversells.

Bottom line: this is a competent short paper that will be most useful to people who want a clean definition of NAO for reactive navigation. It deserves a serious referee only if the venue accepts theory-only incremental results and will push the authors to either prove the shape claims and add quantitative evaluation or drop the multi-robot claim. As it stands, I would not cite it as a demonstrated system.

Referee Report

3 major / 7 minor

Summary. This paper extends the classical Velocity Obstacle (VO) and Nonlinear Velocity Obstacle (NLVO) to the acceleration domain, introducing the Acceleration Obstacle (AO) and Nonlinear Acceleration Obstacle (NAO). For a point robot with circular obstacles, it derives the set of constant robot accelerations that would collide with an obstacle at a given time, and then integrates these temporal sets into global AO and NAO sets (Eqs. (17)-(25)). Selecting an acceleration outside all NAO sets, when one exists within the acceleration bounds, is claimed to yield collision-free motion. The paper further claims that multi-robot navigation is achieved by having all robots use the same avoidance algorithm, with trajectories predicted from current velocity and acceleration. The examples illustrate smooth crossing of roundabouts and curved-road scenarios using NAO-based acceleration selection.

Significance. If the claims are established, the AO/NAO construction is a useful conceptual extension of the VO paradigm: it moves the obstacle-avoidance decision into the acceleration domain, accounts for the robot's dynamic constraints, has no fitted parameters, and the temporal-union construction is geometrically transparent. The examples with curved obstacle trajectories show a plausible advantage over linear VO and constant-acceleration AO, and the paper explicitly identifies the assumption under which the single-robot guarantee holds. However, the paper's advertised multi-robot capability is not supported by the presented analysis or experiments: the safety guarantee in Section V is conditional on obstacles maintaining their current trajectories, while the multi-robot scheme violates that condition by construction. The efficiency claim (fewer adjustments than AO) is also not quantified. The core kinematic derivation is sound, but the breadth of the claims exceeds the evidence.

major comments (3)

[Abstract and Section V] The central multi-robot claim is internally inconsistent with the paper's own safety condition. The abstract states that multi-robot navigation is achieved by all robots using the same avoidance algorithm with trajectories predicted from current velocity and acceleration, while Section V states that a selected safe acceleration is safe only 'as long as the obstacle maintains its current trajectory.' In a multi-robot loop every robot changes its acceleration at each replan, so the obstacle trajectories used to build the NAO are not maintained; the very assumption behind the avoidance guarantee is violated by the algorithm itself. The examples do not test the multi-robot setting: Figures 10-12 involve passive vehicles or vehicles constrained to fixed lanes, not multiple agents all executing the same NAO replanning. To retain the multi-robot claim, the paper needs either a proof that reciprocal replanning preserves separation (for example, an invariant or an RVO-style construction) or a simulation with several mutually avoiding NAO controllers.
[Section VI and Section VII] The claimed advantage that NAO requires fewer adjustments than AO is not substantiated. Section VI reports that using AO in the roundabout scenario 'resulted in multiple collisions' and Section VII concludes that NAO 'allows for more efficient avoidance (fewer adjustments),' but no quantitative comparison is provided: no number of replanning steps, no minimum-distance metrics, no direct comparison of NAO against AO under identical conditions. Since 'efficient' and 'fewer adjustments' are central advertised benefits, the paper should include a quantitative evaluation (for example, a table listing number of acceleration adjustments, replan rate, and clearance for AO versus NAO).
[Section V] The safety statement for the closed-loop replanning policy needs a precise formulation. Equation (25) defines the set of constant accelerations chosen at time t0 that would avoid collision for all future time if that acceleration were held fixed. The described algorithm, however, replans and changes the acceleration at every time step. For a single robot confronting a fixed obstacle trajectory, an inductive argument can probably be made, but the paper does not state it; for multiple reactive robots the argument fails as noted above. The paper should define the replan interval, the state used for replanning, and an explicit induction/invariant that establishes safety of the aperiodic or periodic replanning policy.

minor comments (7)

[Section II] The notation for c(t) is inconsistent: it is first introduced as the robot's configuration, then immediately used as the obstacle center's trajectory in B(t) = c(t) ⊕ B. Please use distinct symbols for the robot position and the obstacle center.
[Abstract and Section I] The phrase 'accounting for robot kinematic and a direct consideration' is grammatically incomplete; it should likely be 'accounting for robot kinematics and directly considering dynamic constraints.'
[Definition 4] Definition 4 contains a typo: 'moving along and an obstacleB' should read 'moving along an arbitrary trajectory while the obstacle B...'.
[Equations (19) and (24)] The notation 2B/t^2 for a Minkowski-scaled set is compact but should be explicitly defined as elementwise scalar multiplication of the set B, to avoid confusion with matrix or vector division.
[Section V] 'It also nullifies the use velocity based avoidance' should be 'it also nullifies the use of velocity-based avoidance.'
[Figures 11 and 12] The NAO maps in Figures 11 and 12 lack labeled axes and units, and the selected acceleration is shown only as a red arrow; adding coordinate labels and a legend would make it possible for the reader to verify that the selected acceleration lies outside all NAO sets.
[Definition 4] Definition 4 uses the interval t ∈ (t0, t∞) without defining t∞; if this denotes a finite prediction horizon, it should be stated, and if it denotes infinity it should be written as ∞.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: AO/NAO are derived by inverting collision kinematics; the authors' self-citations are background and re-derived in-line.

full rationale

The derivation chain in this paper is self-contained. The central objects AO (Eq. 21) and NAO (Eq. 25) are constructed by inverting the collision kinematics: Eq. 17 equates the obstacle position (c(t0) + vB(t0)t + (1/2)aB t^2 for constant acceleration, or the general trajectory c(t) in Eq. 22) with the robot's second-order motion vA(t0)t + (1/2)aA t^2, and solving for the constant acceleration aA yields Eqs. 18 and 23. The forbidden set is then NAO(t) = 2B/t^2 xor (2c(t)/t^2 - 2vA(t0)/t), a derived time-scaled map of the obstacle geometry plus a kinematic term, not a fitted or calibrated quantity. The avoidance statement in Section V ('selecting a safe acceleration, if one exists, would generate a safe avoidance maneuver as long as the obstacle maintains its current trajectory') is a contrapositive of the definition: any collision at time t would force aA into NAO(t) subset of NAO. Although VO and NLVO originate in the authors' prior work ([4], [6]), both are re-derived from first principles in Sections II.A-II.C via homothety, so those self-citations are background rather than load-bearing. The AO discussion also acknowledges the prior acceleration-obstacle literature [5], [8] and contributes a derived generalization (the initial-relative-velocity term -2vA/B(t0)/t in Eq. 18, with the straight-cone property when vA/B = 0), so it is not a renamed known result. No parameters are fitted and no 'prediction' reduces to its input by construction, and no uniqueness theorem is imported from the authors' prior work. The genuine weakness is evidential and internal-consistency related, not circular: the abstract claims multi-robot navigation by all robots running the same replanning algorithm, while Section V's guarantee holds only 'as long as the obstacle maintains its current trajectory'; under mutual replanning that assumption is violated by the algorithm itself, and the examples (Figs. 10-12) use passive or lane-constrained vehicles rather than multiple mutually replanning agents. That is a validation gap, not a circular derivation, so it does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No parameters are fitted to data; the only inputs are kinematic states and chosen obstacle trajectory models. The listed domain assumptions are standard for VO-based planners and are stated explicitly. No new physical entities are introduced; AO and NAO are mathematical sets derived from the kinematics.

assumptions (5)

domain assumption Robot and obstacles are modeled as circles; obstacles are grown by the robot radius to reduce the robot to a point.
Used throughout Section II to build VO and RVC and carried into AO/NAO; standard but a modeling choice.
domain assumption Instantaneous states (position and velocity) of obstacles are known or measurable.
Stated in Section II; all avoidance sets are functions of these states.
domain assumption For AO, the obstacle moves with constant acceleration aB during the whole horizon; for NAO, the obstacle trajectory c(t) is known in advance.
Eq. (17) for AO and Eq. (22) for NAO assume these motion models.
domain assumption The host robot is a second-order system with acceleration as its control input, selectable instantaneously within acceleration constraints.
Section V states: 'We assume the host to be a second order system for which the acceleration serves as the control variable.'
domain assumption Obstacle trajectories predicted from current velocity and acceleration remain valid until the next replan.
Section V says 'as long as the obstacle maintains its current trajectory'; the safety guarantee depends on this.

how reviews work

0 comments

Cite this review

Pith. "Pith review of From NLVO to NAO: Reactive Robot Navigation using Velocity and Acceleration Obstacles." pith.science (2026). https://pith.science/paper/CZO6MPSV

@misc{pith2026250606255,
  author       = {Pith},
  title        = {Pith review of: From NLVO to NAO: Reactive Robot Navigation using Velocity and Acceleration Obstacles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CZO6MPSV}},
  note         = {Machine review of arXiv:2506.06255}
}

read the original abstract

This paper introduces a novel approach for robot navigation in challenging dynamic environments. The proposed method builds upon the concept of Velocity Obstacles (VO) that was later extended to Nonlinear Velocity Obstacles (NLVO) to account for obstacles moving along nonlinear trajectories. The NLVO is extended in this paper to Acceleration Obstacles (AO) and Nonlinear Acceleration Obstacles (NAO) that account for velocity and acceleration constraints. Multi-robot navigation is achieved by using the same avoidance algorithm by all robots. At each time step, the trajectories of all robots are predicted based on their current velocity and acceleration to allow the computation of their respective NLVO, AO and NAO. The introduction of AO and NAO allows the generation of safe avoidance maneuvers that account for the robot dynamic constraints better than could be done with the NLVO alone. This paper demonstrates the use of AO and NAO for robot navigation in challenging environments. It is shown that using AO and NAO enables simultaneous real-time collision avoidance while accounting for robot kinematics and a direct consideration of its dynamic constraints. The presented approach enables reactive and efficient navigation, with potential application for autonomous vehicles operating in complex dynamic environments.

Figures

Figures reproduced from arXiv: 2506.06255 by the authors.

**Figure 3.** To reach point p ∈ B at time t, va/b must satisfy va/b = 1 t − t0 p, (3) where p is a position vector relative to A (For brevity, we will denote A(t0) by A). The mapping of p to va/b (3) is a homothety transformation HA,k that maps A to itself and maps any other point p to point p ′ such that Ap and A(t0) v b v b RVC VO v a1 v a2 [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗

**Figure 4.** A temporal element of the non-linear v-obstacle. [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗

Figures from the paper (5 more)

**Figure 7.** Figure 7: A moving robot A, and obstacle B that is centered initially at c(t0) and moving at an initial velocity vB and a constant acceleration aB. all constant accelerations that would collide with B(t) at time t: AO(t) = 2B t 2 ⊕ ( 2c(t0) t 2 − 2vA/B(t0) t ) + aB (19) Integrat…

**Figure 6.** Figure 6: A comparison between VO and NLVO for an obstacle that is moving along a curved trajectory c(t). The NLVO terminates at A(t0), whereas the VO that accounts only for the initial velocity at time t0 is shifted by v(t0) from A(t0). III. Acceleration Obstacle (AO) Following…

**Figure 8.** Figure 8: Constructing the AO for B moving at a constant acceleration with an initial velocity vB(t0), and A moving at an initial velocity vA(t0). IV. Nonlinear Acceleration Obstacle (NAO) The Nonlinear Acceleration Obstacle, NAO, accounts for obstacles that are moving on genera…

**Figure 12.** Figure 12: Navigating through a busy roundabout using [PITH_FULL_IMAGE:figures/full_fig_p007_12.png]

**Figure 11.** Figure 11: A vehicle crosses at a constant acceleration [PITH_FULL_IMAGE:figures/full_fig_p007_11.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[8]

Reciprocal velocity obstacles for real-time multi-agent navigation

Jur van den Berg, Ming Lin, and Dinesh Manocha. Reciprocal velocity obstacles for real-time multi-agent navigation. In 2008 IEEE International Conference on Robotics and Automation , pages 1928--1935, 2008

work page 2008
[5]

Fiorini and Z

P. Fiorini and Z. Shiller. Motion planning in dynamic environments using velocity obstacles. International Journal of Robotics Research , 17(7):760--772, July 1998

work page 1998
[1]

" id="W5M0MpCehiHzreSzNTczkc9d

11em plus .33em minus .07em @technote 4000 4000 100 4000 4000 500 `\.=1000 = #1 #1 #1 0pt [0pt][0pt] #1 * \| ** #1 \@IEEEauthorblockNstyle \@IEEEauthorblockAstyle \@IEEEauthordefaulttextstyle \@IEEEauthorblockconfadjspace -0.25em \@IEEEauthorblockNtopspace 0.0ex \@IEEEauthorblockAtopspace 0.0ex \@IEEEauthorblockNinterlinespace 2.6ex \@IEEEauthorblockAinte...

work page 2024
[2]

Generalized reciprocal collision avoidance

Daman Bareiss and Jur van den Berg. Generalized reciprocal collision avoidance. The International Journal of Robotics Research , 34(12):1501--1514, 2015

work page 2015
[3]

Chakravarthy and D

A. Chakravarthy and D. Ghose. Obstacle avoidance in a dynamic environment: A collision cone approach. IEEE Transactions on Systems, Man, and Cybernetics, Part A -- Systems and Humans , 28(5):562--574, September 1998

work page 1998
[4]

C. W. Dodge. Euclidean Geometry and Transformations . Dover Publications, 2004

work page 2004
[6]

Gonon, Diego Paez-Granados, and Aude Billard

David J. Gonon, Diego Paez-Granados, and Aude Billard. Robots' motion planning in human crowds by acceleration obstacles. IEEE Robotics and Automation Letters , 7(4):11236--11243, 2022

work page 2022
[7]

Shiller, F

Z. Shiller, F. Large, and S. Sekhavat. Motion planning in dynamic environments: Obstacle moving along arbitrary trajectories. In Proceedings of the IEEE International Conference on Robotics and Automation , 2001

work page 2001

Show all 10 references

[9]

Reciprocal collision avoidance with acceleration-velocity obstacles

Jur Van Den Berg, Jamie Snape, Stephen J Guy, and Dinesh Manocha. Reciprocal collision avoidance with acceleration-velocity obstacles. In 2011 IEEE International Conference on Robotics and Automation , pages 3475--3482. IEEE, 2011

2011
[10]

A survey on velocity obstacle paradigm

Federico Vesentini, Riccardo Muradore, and Paolo Fiorini. A survey on velocity obstacle paradigm. Robotics and Autonomous Systems , 174:104645, 2024

2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [8]

Reciprocal velocity obstacles for real-time multi-agent navigation

Jur van den Berg, Ming Lin, and Dinesh Manocha. Reciprocal velocity obstacles for real-time multi-agent navigation. In 2008 IEEE International Conference on Robotics and Automation , pages 1928--1935, 2008

work page 2008

[2] [5]

Fiorini and Z

P. Fiorini and Z. Shiller. Motion planning in dynamic environments using velocity obstacles. International Journal of Robotics Research , 17(7):760--772, July 1998

work page 1998

[3] [1]

" id="W5M0MpCehiHzreSzNTczkc9d

11em plus .33em minus .07em @technote 4000 4000 100 4000 4000 500 `\.=1000 = #1 #1 #1 0pt [0pt][0pt] #1 * \| ** #1 \@IEEEauthorblockNstyle \@IEEEauthorblockAstyle \@IEEEauthordefaulttextstyle \@IEEEauthorblockconfadjspace -0.25em \@IEEEauthorblockNtopspace 0.0ex \@IEEEauthorblockAtopspace 0.0ex \@IEEEauthorblockNinterlinespace 2.6ex \@IEEEauthorblockAinte...

work page 2024

[4] [2]

Generalized reciprocal collision avoidance

Daman Bareiss and Jur van den Berg. Generalized reciprocal collision avoidance. The International Journal of Robotics Research , 34(12):1501--1514, 2015

work page 2015

[5] [3]

Chakravarthy and D

A. Chakravarthy and D. Ghose. Obstacle avoidance in a dynamic environment: A collision cone approach. IEEE Transactions on Systems, Man, and Cybernetics, Part A -- Systems and Humans , 28(5):562--574, September 1998

work page 1998

[6] [4]

C. W. Dodge. Euclidean Geometry and Transformations . Dover Publications, 2004

work page 2004

[7] [6]

Gonon, Diego Paez-Granados, and Aude Billard

David J. Gonon, Diego Paez-Granados, and Aude Billard. Robots' motion planning in human crowds by acceleration obstacles. IEEE Robotics and Automation Letters , 7(4):11236--11243, 2022

work page 2022

[8] [7]

Shiller, F

Z. Shiller, F. Large, and S. Sekhavat. Motion planning in dynamic environments: Obstacle moving along arbitrary trajectories. In Proceedings of the IEEE International Conference on Robotics and Automation , 2001

work page 2001