5.2.3. Probabilistic Roadmaps (PRM)

PRMs are suited for multi-query applications (e.g., factory floors, surgical environments):

Probabilistic Roadmaps (PRM) are a type of motion planning algorithm designed to effectively handle problems where there are multiple queries for navigation within an environment. These applications often require the ability to quickly find paths through complex and variable environments, making PRMs suitable for settings such as factory floors, where robots may need to move around equipment, and surgical environments, where precision in navigation is critical.

Imagine a busy factory where multiple robots need to transport materials to different workstations efficiently. Each time a robot is tasked with moving, it doesn't want to start from scratch planning its route. Instead, a PRM serves as a pre-existing map of possible paths, allowing the robot to quickly find a safe route without having to plan from the beginning every time.

● Preprocessing: Sample valid configurations and build a roadmap by connecting neighboring samples via local planners.

During the preprocessing phase of PRMs, the algorithm samples valid configurations or points within the robot's workspace. After obtaining these points, it connects them to create a roadmap. This is done by using local planners that check if there is an unobstructed path between two sampled points. By establishing these connections across the sampled points, the PRM effectively maps out a network of potential paths available for the robot to navigate.

Think of this phase like creating a treasure map. First, you walk around the area (sampling valid configurations) to mark the spots where you can dig for treasures (valid configurations). Then, you draw lines between these spots (connecting neighboring samples) to show the paths you can take to get from one treasure to another without hitting obstacles like rocks or trees.

● Querying: Run a shortest path algorithm (like A*) over the roadmap.

Once the roadmap is built during the preprocessing phase, the querying phase allows the robot to find the best path between any two points (or configurations) on the map. This is typically accomplished using a shortest path algorithm, like A*, which efficiently finds the least-cost route considering factors like distance and potential obstacles. By leveraging the precomputed roadmap, the robot speeds up the pathfinding process significantly compared to recalculating paths from scratch during each query.

Imagine you have a city map with all the streets marked (the roadmap) and now you need to get from your house to a new cafe. Instead of driving around aimlessly trying to find the best route (which would typically be like recalculating paths), you simply look at the map and use your quick math skills to find the shortest direction based on your map (the shortest path algorithm).

Used in semi-static environments, PRMs separate computation into offline (learning) and online (execution) stages.

A key advantage of PRMs is their ability to separate the computation into two distinct phases: offline and online. In the offline phase, extensive calculations are performed to sample configurations and compute the roadmap. Then, during the online phase, the robot can swiftly navigate the environment using this roadmap, which saves considerable processing time during actual execution. This separation is particularly useful in semi-static environments where the layout may change slightly over time but is not completely dynamic.

Think of how a chef prepares a meal in a restaurant. In the first phase (offline), the chef does all the prep work like chopping vegetables and marinating meat, which takes a lot of time. Then, when it's time to cook (online), they can quickly assemble and finish the meal with what they prepared earlier, allowing for faster service without needing to start fresh each time.

--