💻 computer science

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

This paper presents an efficient algorithm that guarantees globally optimal minimum-pressure growth paths for vine robots navigating polytopic obstacles by deriving a new pressure equation, proving that optimal paths are piecewise-linear, and solving the resulting time-dependent shortest-path problem with a modified Dijkstra's algorithm.

Original authors: Andres C. Torres, Tobia Marcucci, Elliot W. Hawkes

Published 2026-09-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Andres C. Torres, Tobia Marcucci, Elliot W. Hawkes

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a robot made not of metal and gears, but of soft, flexible plastic that grows like a plant. Instead of rolling on wheels or walking on legs, this machine extends from its tip, pushing itself forward by turning its own skin inside out. Scientists call these "vine robots." They are incredibly useful for exploring tight, cluttered spaces where rigid machines cannot go, such as the ruins of ancient buildings, the inside of collapsed structures after a disaster, or even the human body. Because they are soft, they can squeeze through narrow gaps and wrap around obstacles without causing damage. However, there is a catch. To make the robot grow, you must pump air into it. As the robot gets longer or tries to turn a corner, the air pressure inside must increase. If that pressure gets too high, the thin plastic skin can burst, ending the mission. The challenge for engineers is to find a path through a maze of obstacles that gets the robot to its destination without ever exceeding that dangerous pressure limit.

For a long time, computer programs designed to guide these robots focused on finding the shortest distance or the path with the fewest turns. This approach works well for rigid robots, but it fails for vine robots. A path that looks short on a map might require a sharp turn that forces the internal pressure to skyrocket, causing the robot to fail before it even reaches the goal. In a new study, researchers at the University of California, Santa Barbara, have developed a smarter way to plan these journeys. They created an algorithm that specifically looks for the route requiring the least amount of air pressure. Their method guarantees the best possible path in flat, two-dimensional environments and finds nearly the best path in complex three-dimensional spaces.

The core of this new approach is a deeper understanding of how pressure builds up inside the robot. The researchers derived a new equation that accounts for every straight section and every turn the robot makes. They found that friction from the robot's tail sliding through its own body and the friction created when the robot bends around a corner both add up in a specific way. Crucially, they discovered that the pressure does not just add up; it multiplies with every turn. This means that a path with many small bends can be far more dangerous than a longer path with fewer, gentler curves. To solve the problem of finding the safest route, the team realized that the robot only needs to change direction at the sharp corners of the obstacles it is avoiding. This insight allowed them to turn the complex problem of navigating a 3D maze into a simpler math problem: finding the shortest path through a network of points.

Using this strategy, the researchers built a software tool called VinePlanner. They tested it in computer simulations with thousands of obstacles, creating dense mazes that would have taken older methods hours to solve. Their new algorithm found the optimal path in seconds, even in environments with over 15,000 obstacles. In one test, a standard shortest-distance path would have required a pressure of nearly 20,000 kilopascals, which is far beyond what any vine robot can withstand. In contrast, the path found by the new algorithm required only 318 kilopascals, a safe and manageable level. The researchers also built a physical robot using thin plastic tubing and tested it in a real-world obstacle course made of acrylic blocks. They manually guided the robot along different paths predicted by their model and measured the pressure. The results matched their predictions perfectly: the path their computer chose was the only one that stayed safely below the bursting point, while other seemingly reasonable paths caused the pressure to rise dangerously high.

The team also applied their method to three-dimensional environments, where the obstacles are solid blocks rather than flat walls. While finding the perfect path in 3D is mathematically more difficult, their approach breaks the problem down into small, manageable steps. By placing extra points along the edges of the obstacles, they can find a path that is almost as good as the theoretical best. As they make these steps smaller, the solution gets closer and closer to perfect. This work represents a significant step forward for soft robotics. By ensuring that the robot never has to work harder than necessary, the new planning tool allows these machines to travel much further and explore much deeper into dangerous or inaccessible environments than ever before. The researchers have made their software available to the public, hoping that others will use it to guide vine robots on missions ranging from industrial inspections to medical procedures.

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

Problem Statement

Vine robots are soft, pneumatic devices that extend from their tips by everting their bodies. While they excel in navigating cluttered environments, existing growth planning methods often fail to account for the growth pressure required to traverse specific paths. Growth pressure increases with both the length of the robot and the cumulative angle of turns. If this pressure exceeds the robot's burst pressure, the robot ruptures. Consequently, finding a path that minimizes the maximum growth pressure is critical for safe operation, yet this specific optimization problem has not been rigorously addressed. The paper defines the problem as finding a path $\gamma$ between a start and goal point in an environment with polytopic obstacles that minimizes the growth pressure at the robot's endpoint, subject to collision avoidance constraints.

Methodology

1. Generalized Growth Pressure Equation

The authors first derive a generalized equation for growth pressure applicable to vine robots of arbitrary shape, represented as piecewise-smooth paths.

Derivation: Building on previous models for straight segments and single turns, the authors model the tension accumulation through multiple segments and turns. They utilize the Capstan equation to model the multiplicative effect of friction during turns and a linear term for friction along straight segments.
Result: They derive a differential equation for tension $\tau(s)$ along the path, leading to a general pressure equation $P(s)$ (Equation 7). This equation accounts for yield pressure ( $Y$ ), cross-sectional area ( $A$ ), tail tension ( $T$ ), length-dependent friction ( $\lambda$ ), and the accumulated angle $\Theta(s)$ along the path. Crucially, the model shows that pressure depends heavily on the total path angle, not just path length.

2. Structural Properties of Optimal Paths

A key theoretical contribution is Lemma 1, which states that if a feasible solution exists, there is always a globally optimal path that is piecewise-linear with breakpoints occurring exclusively on the ridges (vertices in 2D, edges in 3D) of the obstacles. This observation reduces the infinite search space of continuous curves to a discrete set of geometric candidates.

3. Algorithmic Approach

The authors reduce the growth planning problem to a shortest-path problem on a line graph, solved via a modified Dijkstra's algorithm.

Visibility Graph Construction: A visibility graph $G$ is constructed using obstacle vertices (and start/goal points) as nodes, with edges representing unobstructed line-of-sight segments.
Line Graph Transformation: To capture the non-additive nature of pressure (where the cost of a turn depends on the accumulated tension from previous segments), the authors construct a line graph $L$ . The nodes of $L$ are the edges of $G$ . A transition in $L$ from edge $(u,v)$ to $(v,w)$ represents a physical turn at vertex $v$ .
Cost Function: The cost of traversing an edge in the line graph is defined by the increase in tension. Unlike standard shortest-path problems, these weights are time-dependent (or state-dependent), as the cost of a turn depends on the tension accumulated up to that point.
Solver: The authors employ a generalized version of Dijkstra's algorithm suitable for time-dependent shortest-path problems. They verify that the edge cost function satisfies the consistency and non-negativity conditions required for the algorithm to guarantee an optimal solution.
2D vs. 3D:
- 2D: The algorithm is guaranteed to find the globally optimal minimum-pressure path because the set of obstacle vertices is finite.
- 3D: Since obstacle ridges are edges containing infinite points, the search space is infinite. The authors propose discretizing obstacle edges into a finite set of points. The resulting solution is an approximation, with the error vanishing as the discretization parameter approaches zero.

Key Contributions

Novel Pressure Equation: A generalized growth pressure equation applicable to vine robots with arbitrary piecewise-smooth shapes, accurately modeling the coupling of length and bends.
Optimal Planning Algorithm: An efficient algorithm that finds globally optimal minimum-pressure paths in 2D and high-quality approximations in 3D. This is the first method to explicitly optimize for growth pressure rather than distance or turn count.
Open-Source Implementation: A high-performance Python package, VinePlanner, which includes the algorithm and is optimized using Numba for parallel processing.

Experimental Results

Simulation and Scalability

Scalability: The algorithm was tested on randomly generated 2D obstacle courses ranging from 100 to 200,000 obstacles.
- For courses with hundreds of obstacles, the algorithm runs in tens of milliseconds.
- For a dense course with 15,000 obstacles (54,712 visibility graph vertices), the algorithm solved the problem in 21 seconds.
- Empirical time complexity was observed to be approximately $O(n^2)$ , significantly better than the worst-case $O(n^3 \log n)$ bound, primarily because the visibility graph construction dominates the runtime, and Dijkstra's search terminates early.
Pressure vs. Distance: In the 15,000-obstacle test, the minimum-pressure path required 318 kPa, whereas the minimum-distance path required 19,430 kPa (over 60 times higher) due to a significantly larger total turning angle, despite being only 4% shorter. The minimum-distance path would have caused the robot to burst.

Hardware Experiments

Setup: Experiments were conducted using a custom vine robot (1.5-inch LDPE tubing) and a modular obstacle course.
Validation: The authors tested the model's ability to correctly rank paths by pressure.
- 2D: Six trials were conducted on a 2D course with four distinct paths. The model correctly predicted the pressure ranking (lowest to highest) 100% of the time, despite absolute pressure variations between trials.
- 3D: Similar experiments on a 3D course with discretized edges also resulted in a 100% correct ranking of paths.
Feasibility: In both 2D and 3D hardware tests, only the path identified as "minimum-pressure" by the algorithm remained below the hypothetical burst pressure threshold, while other near-optimal paths (in terms of distance or turns) exceeded it.

Significance and Limitations

The paper claims that this work represents a critical step toward effective navigation for both teleoperated and autonomous vine robots. By minimizing growth pressure, the algorithm enables these robots to navigate significantly more complex environments and reach further distances than previously possible without risking rupture.

The authors modestly acknowledge several limitations:

Static Environment: The algorithm requires full knowledge of the environment beforehand, unlike online planning methods.
3D Suboptimality: The exact suboptimality gap for the 3D discretized approach is not quantified.
Model Accuracy: While the model correctly ranks paths, there is some inaccuracy in predicting absolute pressure values, suggesting a need for more reproducible experimental setups.
Gravity: The current pressure model omits gravity, which may be significant for large robots in 3D.
Actuation: Experiments relied on manual placement of the robot; future work should integrate active steering actuators.

The authors provide the VinePlanner library to facilitate further research and application in this domain.