From Singleton Obstacles to Clutter: Translation Invariant Compositional Avoid Sets
This work addresses obstacle avoidance in cluttered environments for robotics and autonomous systems, offering incremental improvements through a compositional approach.
The paper tackles obstacle avoidance for translation invariant dynamics by proving that the value function is non-positive everywhere, zero outside obstacles, and negative inside, enabling reuse of a single template for translated obstacles. It introduces a blockwise composition framework to reduce conservatism in clutter, illustrated with a Dubins car example.
This paper studies obstacle avoidance under translation invariant dynamics using an avoid-side travel cost Hamilton Jacobi formulation. For running costs that are zero outside an obstacle and strictly negative inside it, we prove that the value function is non-positive everywhere, equals zero exactly outside the avoid set, and is strictly negative exactly on it. Under translation invariance, this yields a reuse principle: the value of any translated obstacle is obtained by translating a single template value function. We show that the pointwise minimum of translated template values exactly characterizes the union of the translated single-obstacle avoid sets and provides a conservative inner certificate of unavoidable collision in clutter. To reduce conservatism, we introduce a blockwise composition framework in which subsets of obstacles are merged and solved jointly. This yields a hierarchy of conservative certificates from singleton reuse to the exact clutter value, together with monotonicity under block merging and an exactness criterion based on the existence of a common clutter avoiding control. The framework is illustrated on a Dubins car example in a repeated clutter field.