CS Paper Radar

An Efficient Algorithm for Minimum-Pressure Growth Planning of Vine Robots

Andres C. Torres, Tobia Marcucci, Elliot W. Hawkes

cs.RO ·submitted 2026-09-16 03:15 UTC · v1
code/data

Abstract

Vine robots navigate cluttered environments by extending from their tip. Although their ability to operate in such environments has been extensively demonstrated, little work has addressed growth planning, i.e., finding optimal growth paths. Moreover, existing planners do not account for the growth pressure necessary to follow a given path, which can cause the robot to burst when it is too high. In this paper, we address the problem of finding minimum-pressure paths for vine robots growing around polytopic obstacles. We propose an efficient algorithm that is guaranteed to find globally optimal solutions in 2D and approximate solutions in 3D, with an error that vanishes as a discretization parameter approaches zero. First, we derive a growth pressure equation for vine robots of arbitrary shape, which we use to show that there always exists a minimum-pressure path that is piecewise-linear and can bend only at specific points on the obstacles. We then leverage this observation to reduce the growth-planning problem to a shortest-path problem with time-dependent weights, which we efficiently solve using a modified Dijkstra's algorithm. We demonstrate the speed and scalability of our approach through numerical simulations. We also validate our algorithm with hardware experiments and provide an open-source and high-performance implementation in the Python package, VinePlanner: https://github.com/Ahsoka/VinePlanner.

Closest papers

Nearest neighbours by meaning across the whole index.

Riemannian Optimization-based Whole-body Obstacle Avoidance for Mobile Continuum Robots in Cluttered Environments

cs.RO ·2026-11-04 ·Duo Tang, Ping Deng, Sophie Armanini, Yajing Shen, Toshio Fukuda +2 more
similarity 0.60
Abstract

Inspired by the coordination of global motion and local shape adaptation in snakes, elephant trunks, and octopus arms, we propose a unified planning and control framework for mobile continuum robots in cluttered and confined environments. Existing approaches often address high-level path planning and local motion control separately, limiting coordinated base-arm motion, kinematic consistency, and collision avoidance. Our framework integrates long-horizon trajectory planning with real-time geometric refinement under kinematic and environmental constraints. The global layer combines A* search with minimum-jerk planning to generate smooth reference trajectories. The local layer uses a geometry-consistent inverse kinematics solver and Riemannian optimization to coordinate mobile-base motion and continuum deformation while avoiding obstacles. We evaluate the framework through simulated pipe-traversal tasks with multiple baseline planners and real-world experiments involving navigation among dense obstacles and manipulation in confined spaces. Results demonstrate improved motion consistency, feasibility, and adaptability, supporting coordinated whole-body motion of mobile continuum robots in constrained environments.

0.27

A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation

cs.RO cs.AI ·2026-09-19 ·Antony Thomas, Giulio Ferro, Fulvio Mastrogiovanni, Michela Robba, Marco Baglietto
publishedhot direction similarity 0.59
Abstract · Accepted for publication in Intelligent Service Robotics

In this paper, we investigate the Minimum Obstacle Displacement Planning problem from a robot motion planning perspective. The problem involves determining a feasible path to a goal location by displacing movable obstacles when no collision-free path initially exists. We show that this problem is computationally challenging and, in particular, NP-hard when obstacles are modeled as polygons in the plane. Besides an exact formulation of the minimum obstacle displacement problem generalizing other problems in the literature, and the associated optimal solution, this paper proposes an approximate solution that is less intensive from a computational standpoint, and differs from the optimal solution by a fraction of the optimal cost, being able to trade-off between path length and amount of obstacle displacements.

0.38

FPTAS for Polygonal Multi-Robot Motion Planning

cs.CG cs.DScs.RO ·2026-10-14 ·Sayan Bandyapadhyay, William Lochet, Saket Saurabh, Jie Xue
top venue similarity 0.58
Abstract · To appear in SODA 2027

We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain $\mathcal{W}$ with $n$ vertices and $k$ robots $R_1,\dots,R_k$ translating in $\mathcal{W}$ each of which is represented by a polygon of constant complexity. Given a source configuration $\mathbf{s}$ and a target configuration $\mathbf{t}$ of the robots in $\mathcal{W}$, the goal of the problem is to find a collision-free motion plan from $\mathbf{s}$ to $\mathbf{t}$ that is shortest with respect to some cost function. We present the first fully polynomial-time approximation schemes (FPTAS) for motion planning with any fixed number $k$ of robots, under the min-sum objective, the min-max objective, and the min-makespan objective. Here, the min-sum variant aims to minimize the total traveling distance of all robots, the min-max variant aims to minimize the maximum traveling distance of a single robot, and the min-makespan variant aims to minimize the total time cost under the assumption that all robots move with a maximum speed $1$. The algorithm directly generalizes to the problem in any fixed dimension $d$, with a polytope environment and polytope robots. Our result settles an open question of Agarwal, Halperin, Sharir, Steiger [SODA'24] and Agarwal, Holmgren, Steiger [SODA'26], who gave an FPTAS for $k=2$ unit-square robots and a bicriteria-approximation algorithm for a fixed number $k$ of unit-square or unit-disk robots, respectively. Compared to the previous results, our algorithm is substantially simpler.

0.30

A Multi-Vine Soft Robot Enabling Accessible Working Channel and Steering

cs.RO ·2026-09-03 ·Reza Kashef, Cem Suulker, Mohammad Sheikh Sofla, Kaspar Althoefer
published similarity 0.58
Abstract · Hamlyn Symposium on Medical Robotics 2026

Soft eversion robots, also known as vine robots, have attracted growing interest for navigation and inspection tasks, including minimally invasive medical applications [1]. A vine robot consists of a thin, flexible, inextensible tube folded inward that everts and grows forward when pressurized. This tip-growth enables navigation with minimal friction, making vine robots well suited for complex environments such as the human colon [2]. While their inherent softness allows passive conforma- tion to curved pathways in confined spaces, navigation performance strongly depends on environmental inter- actions, including contact angle and the length of un- constrained deployed material [3], [4]. Sharp directional changes, such as those in the sigmoid colon, often limit passive growth and necessitate active steering. Existing solutions include distributed artificial muscles [5] or dedicated tip-based steering mechanisms [6]. In addition, many applications require payload delivery, such as sensors and tools [7], [8]. Within the ERC Synergy project EndoTheranostics, this motivates the development of vine robots capable of delivering micro- surgical tools during growth. Prior work has integrated working channels within the vine body [8], [9], but these approaches constrain tool size, introduce friction, and limit access to the environment to the robot tip. In this work, we propose a multi-vine architecture in which two vine robots are coupled to an externally integrated working channel via soft mounting tips [10]. Independent vine actuation enables active tip steering while advancing the working channel without embed- ding it within the vine bodies Figure 1. Experiments demonstrate sharp steering of nearly 90 degrees during growth, highlighting the potential of this architecture for versatile medical and non-medical applications.

0.35

PccDiffuser: Multi-solution Motion Planning for Continuum Robots

cs.RO ·2026-09-09 ·Ke Qiu, Sifan Chen, Si Wang, Rong Xiong, Yue Wang +1 more
hot direction similarity 0.57
Abstract · 8 pages, 8 figures, 1 video

We present the PccDiffuser, a conditional diffusion framework for continuum robots that learns a multimodal distribution over complete configuration-space paths and samples multiple candidate solutions in parallel, which are subsequently converted into an executable trajectory by time allocation considering actuator constraints. Under the piecewise constant-curvature model, we use exponential co-ordinates to describe the robot kinematics, and use graph neural network to encode a variable number of environment obstacles. Analytical differential kinematics is incorporated in the denoising process to improve terminal accuracy and whole-body clearance. On a mixed test set comprising workspace with zero to four obstacles, PccDiffuser achieved a success rate of 91\%. Compared with existing sampling- and optimisation-based benchmarks, it delivered both a higher success rate and greater computational efficiency, with the latter advantage becoming more substantial when sampling more candidate solutions. Experiments on a three-section tendon-driven continuum robot further demonstrate consecutive planning, multi-solution planning, and whole-body obstacle avoidance.

0.35

Path Planning with Motion Primitives in Dynamic Environments: SIPP on Lattices

cs.RO ·2026-09-25 ·Marat Agranovskiy
published similarity 0.56
Abstract · Accepted to International Conference on Interactive Collaborative Robotics (ICR 2026), Vladivostok, Russia

Autonomous navigation in dynamic environments is a critical challenge, particularly when spaces are shared with other mobile agents whose future trajectories are known. While traditional grid-based planners efficiently find collision-free paths, their reliance on stop-and-turn mechanics over $2^k$-connected grids produces piecewise-linear trajectories that are kinodynamically highly sub-optimal for differentially constrained robots. In this paper, we present an adaptation of Safe Interval Path Planning (SIPP) that operates on state lattices, utilizing precomputed, kinodynamically smooth motion primitives. To efficiently handle dynamic environments, we rasterize the spatiotemporal swept volumes of moving obstacles directly onto the grid, treating grid cells as atomic units of space, whose resolution is typically dictated by inherent localization noise. We perform a comprehensive comparative analysis between our lattice-based approach and $2^k$-connected grid planners across diverse topological environments. Our evaluation considers a broad spectrum of performance metrics, including planning time, path angularity, cumulative heading change (angle-over-length), and bending energy. The results demonstrate that while the expanded state space of lattice-based search increases computational overhead, it yields trajectories with significantly superior kinodynamic properties. Specifically, our method achieves a reachability comparable to highly connected grids while ensuring smooth, continuous, and physically executable paths ready for real-world deployment.

0.49

Continuous-Time Motion Planning and Steering with Global Convergence

cs.RO ·2026-10-22 ·Mohsen Amiri, Sima Didari, Davoud Ataee Tarzanagh, Hankyu Moon, Yeongdae Kwon
benchmark similarity 0.56
Abstract

Motion planning is central to robotics, and it is increasingly used to correct the motions proposed by learned planners and policies. In both uses, constraints must hold at every instant of the motion, not only at sampled times. To our knowledge, no algorithm provably converges to a globally optimal motion once a smoothness cost is combined with such constraints. We cast planning and steering as a single continuous-time program: robots avoid one another and static or moving obstacles, and a learned proposal is steered by keeping the motion close to it. The program is elementary to state, yet nonconvex. We propose GlobMP (Global Motion Planning), a gradient projection method over piecewise-polynomial curves, on which each constraint is one polynomial per piece that must stay nonnegative over the whole motion; it alternates cost reduction with feasibility restoration. Under mild assumptions, we show that, from a fine grid start, its cost approaches the global optimum as the number of polynomial pieces grows, with every constraint met to any chosen tolerance, or exactly on stable instances. We demonstrate its superior performance over strong baselines in real and synthetic experiments, including teams of up to $200$ robots, multi-robot planning on the Robotarium testbed and an extended benchmark, maze navigation, and steering tactile-reactive policies on a bimanual humanoid.

0.16

PoliMop: Policy-in-the-Loop Motion Planning in 3D Spaces for Mobile Robots

cs.RO ·2026-11-13 ·Yael Fassbind, Valentin N. Hartmann, Huang Su, Yijiang Huang, Stelian Coros
similarity 0.55
Abstract · 8 pages, 5 figures. Videos and code: https://ariael21.github.io/polimop.html

Reaching a goal state in a complex environment often requires a robot to overcome challenging terrain and obstacles. Which routes are accessible depends on the robot's physical design, the control policy it uses, and how it modifies its surroundings. We present a kinodynamic rapidly-exploring random tree (RRT) planner that uses physics simulation to exploit skills encoded in the control policy, which allows it to find a path in the scene with respect to the robot's capabilities. The planner samples states from a reduced state space in 3D around the scene and expands the RRT toward each sample using policy rollouts. We guide sampling with a preplanned path for a simple mass-point model to focus exploration on promising regions leading toward the goal state, reducing planning time by up to 63%. Simulation experiments with quadrupeds, humanoids, and wheeled robots demonstrate that our approach supports drop-in integration of various robots and control policies, exploiting their physical and policy capabilities without modifying the underlying planning algorithm. Predefined environmental modifications, such as placing a plank across a gap to build a bridge, will automatically be picked up by the planner as the robot's reachable space expands.

0.19