As we have specified the path planning problem at the beginning of the chapter, we have assumed that the information about environmental obstacles is complete and correct. However, this is rarely the case, and this can be problematic. If some obstacles are unobserved or imperfectly sensed, then the robot may happily start to execute its solution path (which is feasible according to the robot's model), but in reality the robot might end up colliding ! Although it is possible to devise planning algorithms that are able to cope with these types of unknowns, these are relatively complex and typically beyond the scope of an introductory robotics course. Instead, we shall see how we might handle these issues in practice by modifying how a planner is invoked during its sense-plan-act loop.
To handle missing data, one straightforward and effective approach is to ensure that the robot senses around it as it moves, and then replans when the previous plan becomes invalidated by a newly-sensed obstacle. With an optimistic replanning strategy, the robot assumes that any areas that have not been observed are obstacle-free. Then, its first path will navigate around local obstacles and then proceed straight to the goal. As it starts to execute the path, it will update its map representation using sensor data, and then a plan execution module will repeatedly verify whether the current plan is still valid. If an obstacle is observed in the previously unseen location, then the robot will replan and find an alternate route. Another variant of this approach would simply replan at regular intervals. This would work best with a fast planner, so that new obstacles can be reacted to quickly, as well as an optimizing planner, to ensure that the paths do not vary too wildly as more sensor data is incorporated.
One question that must be addressed is whether the local map is properly updated to handle obstacles. For example, if a human were to walk through a building backwards it would be very likely to bump into something or to trip! If the robot's sensor were omnidirectional or always oriented in its direction of motion, then as it approaches an unobserved part of the world, then yes, the new sensor data will fill in the map. This is also an effective strategy to handle slowly moving obstacles.
To handle noisy observations, are a simple and often effective approach. The idea is simply is to fatten the obstacles (or the robot geometry) used by the planner by some margin of error $\epsilon$. Hence, path produced by the planner will never pass within $\epsilon$ distance of the sensed obstacles. If the threshold $\epsilon$ is chosen appropriately to encapsulate all of the errors of the sensor at hand, the robot will not collide while executing. However, if the threshold is made too large, the planner may fail to find a path through a narrow passage.
There are a few solutions in the latter case: either use sensors with higher accuracy, use probabilistic obstacle maps that penalize paths that are likely to collide, or use sensor-based motion planning techniques that predict and reason about how future sensor measurements may change the robot's map, and how robots can use sensor feedback during low-level motions rather than just following a path. Sensor-based planning techniques reason in an information space to predict how future measurements could lead to narrow passages opening up in the map in the future. However, these methods are generally more computationally complex because the space of maps may be enormous.
In many robotics applications, such as obstacle avoidance, it is necessary for the robot to integrate new information into its model of the world and to respond with a new plan in real time. By "real-time" we mean that the planner must produce an answer within a fixed time budget. This budget is usually relatively small, say, one second or a fraction of a second. For low-dimensional robots, this is not usually much of a problem, since geometric planners are usually quite fast. However, for industrial manipulators, legged robots, or multi-robot coordination this may pose a much more challenging computational issue.
We have already mentioned potential fields as one obstacle avoidance technique that is quite computationally light. However, its drawbacks that TODO: describe time shifting, dynamic windowing, any-time planning.
See Control...
Kinodynamic planning
Configuration-Time space
Computational complexity (NP hard on graph)
Deadlock
Coordination graph
Duality between manipulation and locomotion
Planning on closed chain manifolds
Grasp planning.
Multi-modal planning. Transitions
AI planning and scheduling
Semantics
Knowledge base