Related Experiment Video
Updated: Jul 7, 2026
11:53
The Modular Design and Production of an Intelligent Robot Based on a Closed-Loop Control Strategy
Published on: October 14, 2017
On the moving-obstacle path-planning algorithm of Shih, Lee, and Gruver
Summary
A motion planning algorithm for moving obstacles fails to guarantee collision-free paths. This study provides a counter-example and discusses potential repairs and computational complexity for a corrected algorithm.
Area of Science:
- Robotics
- Artificial Intelligence
- Motion Planning Algorithms
Background:
- The Shih, Lee, and Gruver (1990) algorithm addresses motion planning among moving obstacles.
- The algorithm is purported to consistently find collision-free paths when feasible.
Purpose of the Study:
- To critically evaluate the claimed completeness of the Shih, Lee, and Gruver (1990) motion planning algorithm.
- To identify limitations and propose improvements for motion planning in dynamic environments.
Main Methods:
- Analysis of the Shih, Lee, and Gruver (1990) algorithm.
- Development of a specific counter-example demonstrating algorithm failure.
- Examination of algorithmic repair strategies and computational complexity analysis.
Main Results:
- A concrete counter-example is presented, invalidating the claim of guaranteed collision-free path generation.
- The study investigates potential modifications to enhance the algorithm's robustness.
- The computational complexity of a corrected algorithm is analyzed.
Conclusions:
- The original algorithm is not complete for motion planning among moving obstacles.
- Further research is needed to develop and analyze robust and computationally efficient algorithms for dynamic environments.
Related Concept Videos
01:10Design Example: Measuring Distance Between Two Points with Obstructions
When measuring distances in areas with physical obstructions, such as a lake in a field, surveyors must employ techniques to calculate accurate lengths without direct line measurements. One effective method is the offset technique, which allows for precise distance estimation over inaccessible stretches.In this scenario, a surveyor must measure a side of an area that crosses a lake. Since the measuring tape cannot span the lake, the surveyor begins by establishing a baseline that aligns with...
01:17Rolling Resistance: Problem Solving
Rolling resistance, also known as rolling friction, is the force that resists the motion of a rolling object, such as a wheel, tire, or ball, when it moves over a surface. It is caused by the deformation of the object and the surface in contact with each other, as well as other factors like internal friction, hysteresis, and energy losses within the materials. Rolling resistance opposes the object's motion, requiring additional energy to overcome it and maintain movement. In practical...
01:22Planar Rigid-Body Motion
Understanding the movement of a rigid body in planar motion involves recognizing that every particle within this body is traversing a path that maintains a consistent distance from a specific plane. This concept is fundamental in the study of physics and mechanical engineering, and it allows us to comprehend better how objects move in space.
Planar motion is typically divided into three distinct categories. The first is rectilinear translation, demonstrated by a subway train that moves along...
Planar motion is typically divided into three distinct categories. The first is rectilinear translation, demonstrated by a subway train that moves along...
01:29Relative Motion Analysis using Rotating Axes-Problem Solving
Consider a crane whose telescopic boom rotates with an angular velocity of 0.04 rad/s and angular acceleration of 0.02 rad/s2. Along with the rotation, the boom also extends linearly with a uniform speed of 5 m/s. The extension of the boom is measured at point D, which is measured with respect to the fixed point C on the other end of the boom. For the given instant, the distance between points C and D is 60 meters.
Here, in order to determine the magnitude of velocity and acceleration for point...
Here, in order to determine the magnitude of velocity and acceleration for point...
01:16Hydraulic Jump: Problem Solving
To analyze a hydraulic jump in a rectangular channel with a flow speed of 6 meters per second, follow these steps:Calculate Effective Upstream Velocity:When the downstream gate closes, a hydraulic jump forms, traveling upstream at 2 meters per second. This wave speed combines with the initial channel flow velocity, creating an effective upstream velocity.Identify Flow Velocities Before and After the Hydraulic Jump:Upstream of the hydraulic jump, the effective flow velocity includes both the...
01:30Vector Functions and Motion: Problem Solving
Accurate position tracking is fundamental to the safe and effective operation of unmanned aerial vehicles (UAVs), particularly during precision maneuvers near complex structures. In this scenario, a drone is programmed to perform a high-precision inspection of a vertical structure, starting at position ((x, y, z) = (3, 0, 0)), with an initial velocity oriented in the positive z-direction. The trajectory of the drone is governed by a time-dependent acceleration function a(t), which is predefined...