More Like this

1. Hardness of Motion Planning with Obstacle Uncertainty in Two Dimensions

   https://doi.org/10.1177/0278364921992787  

   Shimanuki, Luke; Axelrod, Brian (February 2021, The International Journal of Robotics Research)

   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 [Formula: see text]-hard with respect to the number of obstacles, and remains [Formula: see text]-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 [Formula: see text]-SAT that both safe 3D motion planning among PGDF obstacles and the related minimum constraint removal problem remain [Formula: see text]-hard even when restricted to cases where each obstacle overlaps with at most a constant number of other obstacles. 

   more » « less
2. Hybrid locomotion at the insect scale: Combined flying and jumping for enhanced efficiency and versatility

   https://doi.org/10.1126/sciadv.adu4474  

   Hsiao, Yi-Hsuan; Bai, Songnan; Guan, Zhongtao; Kim, Suhan; Ren, Zhijian; Chirarattananon, Pakpong; Chen, Yufeng (April 2025, Science Advances)

   Insect-scale robots face two major locomotive challenges: constrained energetics and large obstacles that far exceed their size. Terrestrial locomotion is efficient yet mostly limited to flat surfaces. In contrast, flight is versatile for overcoming obstacles but requires high power to stay aloft. Here, we present a hopping design that combines a subgram flapping-wing robot with a telescopic leg. Our robot can hop continuously while controlling jump height and frequency in the range of 1.5 to 20 centimeters and 2 to 8.4 hertz. The robot can follow positional set points, overcome tall obstacles, and traverse challenging surfaces. It can also hop on a dynamically rotating plane, recover from strong collisions, and perform somersaults. Compared to flight, this design reduces power consumption by 64 percent and increases payload by 10 times. Although the robot relies on offboard power and control, the substantial payload and efficiency improvement open opportunities for future study on autonomous locomotion. 

   more » « less
3. Hybrid A* path search with resource constraints and dynamic obstacles

   https://doi.org/10.3389/fpace.2022.1076271  

   Cortez, Alán; Ford, Bryce; Nayak, Indranil; Narayanan, Sriram; Kumar, Mrinal (January 2023, Frontiers in Aerospace Engineering)

   This paper considers path planning with resource constraints and dynamic obstacles for an unmanned aerial vehicle (UAV), modeled as a Dubins agent. Incorporating these complex constraints at the guidance stage expands the scope of operations of UAVs in challenging environments containing path-dependent integral constraints and time-varying obstacles. Path-dependent integral constraints, also known as resource constraints, can occur when the UAV is subject to a hazardous environment that exposes it to cumulative damage over its traversed path. The noise penalty function was selected as the resource constraint for this study, which was modeled as a path integral that exerts a path-dependent load on the UAV, stipulated to not exceed an upper bound. Weather phenomena such as storms, turbulence and ice are modeled as dynamic obstacles. In this paper, ice data from the Aviation Weather Service is employed to create training data sets for learning the dynamics of ice phenomena. Dynamic mode decomposition (DMD) is used to learn and forecast the evolution of ice conditions at flight level. This approach is presented as a computationally scalable means of propagating obstacle dynamics. The reduced order DMD representation of time-varying ice obstacles is integrated with a recently developed backtracking hybridA∗ graph search algorithm. The backtracking mechanism allows us to determine a feasible path in a computationally scalable manner in the presence of resource constraints. Illustrative numerical results are presented to demonstrate the effectiveness of the proposed path-planning method. 

   more » « less
4. Multi-Objective Heuristics For Network Construction In An Obstacle-Dense Environment

   https://doi.org/10.1109/CASE59546.2024.10711579  

   Bernardini, Francesco; Becker, Aaron T (August 2024, IEEE)

   We present a heuristic method to construct an optimal communication network in an obstacle-dense environment. A set of immobile terminals must be connected by a network of straight-line edges by adding agents to serve as relays. Obstacles are represented by polygons, unaccessible by the agents of the network or by the edges. The problem with obstacles is reduced to a problem without obstacles by choosing the nodes of the optimal network among the obstacles’ vertices that are in mutual line of sight. A second heuristic method is developed to solve the bicriteria optimization problem with number of agents and length of the network as concurrent costs. 

   more » « less
5. Modeling root system growth around obstacles

   https://doi.org/10.1038/s41598-020-72557-8  

   Jin, Wencheng; Aufrecht, Jayde; Patino-Ramirez, Fernando; Cabral, Heidy; Arson, Chloé; Retterer, Scott T. (December 2020, Scientific Reports)

   null (Ed.)

   Abstract State-of-the-Art models of Root System Architecture (RSA) do not allow simulating root growth around rigid obstacles. Yet, the presence of obstacles can be highly disruptive to the root system. We grew wheat seedlings in sealed petri dishes without obstacle and in custom 3D-printed rhizoboxes containing obstacles. Time-lapse photography was used to reconstruct the wheat root morphology network. We used the reconstructed wheat root network without obstacle to calibrate an RSA model implemented in the R-SWMS software. The root network with obstacles allowed calibrating the parameters of a new function that models the influence of rigid obstacles on wheat root growth. Experimental results show that the presence of a rigid obstacle does not affect the growth rate of the wheat root axes, but that it does influence the root trajectory after the main axis has passed the obstacle. The growth recovery time, i.e. the time for the main root axis to recover its geotropism-driven growth, is proportional to the time during which the main axis grows along the obstacle. Qualitative and quantitative comparisons between experimental and numerical results show that the proposed model successfully simulates wheat RSA growth around obstacles. Our results suggest that wheat roots follow patterns that could inspire the design of adaptive engineering flow networks. 

   more » « less