ARO Robot Motion Planning

1. Motion Planning in Robotics

1.1. Demo Case Study: Navigating an Autonomous Rover on Mars

Super Domain: Motion Planning
Type of Method: Pathfinding in Complex Environments

1.2. Problem Definition and Variables

Objective: Plan collision-free motions for a rover from a start to a goal position among a set of obstacles on a Martian landscape.
Variables:
- Environmental model, including terrain map and obstacle positions.
- Rover’s capabilities, including its movement constraints and geometry.

1.3. Method Specification and Workflow

Motion Planning: Develop a strategy to compute a feasible path that the rover can follow to reach the goal without collisions.
Path Planning Problem: Define a path planning problem with specific start and goal points, considering the rover’s and environment’s properties.
Approaches:
- Local Methods: Reactively adapt the behavior of the rover based on immediate sensor data to avoid obstacles.
- Global Methods: Precompute a path considering the entire map, designed to avoid local minima and ensure reaching the goal.

1.4. Strengths and Limitations

Strengths:
- Allows for the safe navigation of robots in unknown or dynamic environments.
- Can be adapted for different types of robots and objectives.
Limitations:
- The complexity of the environment can make the problem computationally intensive.
- Real-time changes in the environment may require re-planning.

1.5. Common Problems in Application

The rover may encounter unexpected obstacles not present in the initial map.
Varying terrain properties may affect the rover’s ability to follow a planned path.

1.6. Improvement Recommendations

Integrate sensory feedback into planning algorithms for dynamic adaptation.
Employ machine learning techniques to predict and plan for environmental changes.

s17580012162023

s18302112162023
s21471712162023

2. Potential Field in Robotics

Super Domain: Motion Planning
Type of Method: Vector Field Approach

2.2. Problem Definition and Variables

Objective: To navigate an autonomous robot through a dynamic environment to a goal position while avoiding obstacles.
Variables:
- $U$: The potential field in the environment.
- $\nabla U(q)$: The gradient of the potential field, which indicates the direction of the force exerted by the field.

2.3. Method Specification and Workflow

Attractive Component: Pulls the robot towards the goal, modeled by a potential well where the goal is the lowest point.
Repulsive Component: Pushes the robot away from obstacles, modeled by potential peaks around the obstacles.
Principle: Use a potential field that exerts virtual forces on the robot: attractive forces pull it towards the goal, while repulsive forces push it away from obstacles.
Workflow:
1. Define the attractive potential field around the goal position.
2. Define the repulsive potential field around the obstacles.
3. Combine the attractive and repulsive fields to create a composite potential field.
4. Navigate the robot in the direction of the negative gradient of the composite field.

2.4. Strengths and Limitations

Strengths:
- Computationally fast and capable of producing smooth paths.
- Intuitive and easy to implement.
- Produces natural motions if configured correctly.
Limitations:
- Can get trapped in local minima, failing to find a path to the goal.
- May produce unstable oscillations in the presence of obstacles or narrow passages.
- The solution is not guaranteed and may require manual tuning.
- The method is not complete, meaning it does not guarantee that a solution will be found even if one exists, nor is it optimal.

2.5. Common Problems in Application

The robot may oscillate indefinitely in narrow corridors due to equal repulsive forces from the walls.
The robot may not find a path to the goal if the potential field has local minima away from the goal.

2.6. Improvement Recommendations

Incorporate random walks or other exploration strategies to escape local minima.
Use hybrid methods combining potential fields with other planning strategies for robustness.

2.7. Potential Field (PF) Discussion

Advanced techniques like the navigation function approach can mitigate some limitations of potential fields by ensuring convergence to the goal without getting trapped in local minima.
The repulsive potential typically decreases with distance from the obstacle, becoming zero beyond a certain threshold.

s18123412162023

3. Rapidly-exploring Random Trees (RRT)

3.1. Demo Case Study: Autonomous Exploration Rover on Mars

Super Domain: Motion Planning
Type of Method: Sampling-based, Randomized Path Planning

3.2. Problem Definition and Variables

Objective: Efficiently explore uncharted terrain on Mars to collect data, using a path planning approach that can quickly adapt to large, unknown areas.
Variables:
- Configuration space representing the rover’s possible positions and orientations.
- Current known configuration of the rover.

3.3. Method Specification and Workflow

Principle: RRT is a data structure that represents a space-filling tree built from randomly sampled points in the configuration space. The tree rapidly expands towards unexplored areas, providing coverage and a path to the goal.
Workflow:
1. Start with an initial node from the known configuration.
2. Randomly sample a new point in the configuration space.
3. Find the nearest node in the tree to the new sample.
4. Extend the tree towards the new point by a predefined step size.
5. Check if the new extension is within the unexplored space and free of obstacles.
6. Repeat the process until a path from the start to the goal configuration is identified.

3.4. Strengths and Limitations

Strengths:
- Rapidly explores vast areas, making it suitable for large-scale and high-dimensional spaces.
- Doesn’t require a pre-existing map of the environment.
Limitations:
- May not find the most optimal path due to the randomness of point sampling.
- The basic RRT doesn’t handle dynamic environments or changing obstacle configurations well.

3.5. Improvement Recommendations

Implement RRT* or other variants which include a reconnection strategy to improve path optimality.
Integrate with other sensors and algorithms for real-time re-planning in dynamic environments.

3.6. Rapidly-exploring Random Trees (RRT): Discussion

RRTs are particularly useful for single-query searches, where the objective is to find one viable path from a known configuration to a target as quickly as possible. This makes RRTs highly applicable to scenarios like space exploration or search and rescue missions, where time is of the essence and the environment may not be fully known in advance.

While the method is biased towards unexplored spaces, ensuring a comprehensive coverage over time, the random nature of the sampling process means that the quality of the path can vary. In mission-critical applications, this variability requires that the generated path be checked for safety and, if necessary, post-processed for smoothness and feasibility.

The adaptability of RRT to various mission parameters and environmental conditions, along with its relatively simple implementation, makes it a valuable tool in the field of autonomous system navigation. However, in complex environments with numerous obstacles, RRT may require modifications or combinations with other planning strategies to ensure robust performance.

s18185612162023
s18194212162023

4. Probabilistic Roadmaps (PRM)

4.1. Demo Case Study: Path Planning for a Service Robot in a Hospital

Super Domain: Motion Planning
Type of Method: Multi-query, Sampling-based Planning

4.2. Problem Definition and Variables

Objective: To enable a service robot to navigate efficiently through the complex corridors of a hospital, connecting various points of interest such as patient rooms, diagnostic centers, and pharmacies.
Variables:
- Configuration space representing the robot’s possible positions and orientations.
- A set of points of interest that the robot may be required to visit multiple times.

4.3. Method Specification and Workflow

Principle: PRM constructs a network or roadmap of possible paths by sampling the configuration space, adding valid samples as nodes, and connecting these nodes with edges if a direct path between them is possible and collision-free.
Workflow:
1. Randomly sample the configuration space to generate a set of nodes, discarding any that result in collisions with obstacles.
2. For each node, attempt to connect it to nearby nodes using a local planner to generate edges, creating the roadmap.
3. Once the roadmap is constructed, use graph search algorithms to find paths from any given start node to a goal node.
4. The roadmap can be reused for different start and goal configurations, making PRM suitable for multi-query scenarios.

4.4. Strengths and Limitations

Strengths:
- Well-suited for environments where the robot will need to perform multiple planning queries over time.
- The precomputed roadmap allows for rapid path finding once constructed.
Limitations:
- Initial construction of the roadmap can be computationally intensive.
- May not perform well in highly dynamic environments where obstacles frequently change positions.

4.5. Improvement Recommendations

Optimize the sampling strategy to ensure coverage of critical areas while minimizing redundant nodes.
Incorporate dynamic re-planning to update the roadmap in response to changes in the environment.

4.6. Probabilistic Roadmaps (PRM): Discussion

PRMs are a powerful tool for scenarios where a robot must navigate within a defined area and perform various tasks at different locations. By decoupling the roadmap construction from the path-finding phase, PRMs offer a flexible solution to the path planning problem, particularly in static or semi-static environments.

One of the key advantages of PRMs is the ability to handle complex, high-dimensional spaces, which is essential for robots with many degrees of freedom. However, PRMs are not without drawbacks. The quality of the roadmap is highly dependent on the sampling process, and there may be regions of the configuration space that are under-sampled, leading to potential gaps in connectivity.

Furthermore, the reliance on a static roadmap means that PRMs are less suited to environments with dynamic obstacles. In such cases, the roadmap may need frequent updates or a combination with local planning methods to ensure the robot can navigate safely and efficiently. Despite these challenges, PRMs remain one of the foundational techniques in robot motion planning, particularly in known and controlled spaces like hospital corridors, where the environment changes infrequently and predictably.

s18204512162023
s18211812162023
s18212812162023