| description abstract | Motion planning for mobile robots in dynamic and uncertain environments (e.g., in multirobot manufacturing) is challenging due to the stochastic nature of the problem. One common approach is to construct an initial plan to guide the robots, and as information is collected during execution, adjustments are made in real time to account for the impact of uncertainties. This approach, while feasible, leaves the burden of dynamic collision avoidance on controllers, which may not find collision-free and optimal control inputs fast enough. Additionally, the computational burden is exacerbated as the dimensionality of the workspace and the number and geometric complexity of obstacles increase. This article presents a novel probabilistic roadmap (PRM)-based offline motion planner for mobile robots traveling under uncertainty. The planner considers arbitrarily shaped holonomic robots in an environment with multiple static and dynamic obstacles. Since PRM is graph-based, we model the uncertainty by treating edge costs as general probability density functions whose exact profiles are related to the actuation characteristics of a mobile robot. The risk of success (i.e., no collision) per each action in the plan is lower-bounded by a user-defined value, allowing an informed choice between solution safety and quality. Simulations in various scenarios with both static and dynamic obstacles, and configuration spaces of different dimensions, show the effectiveness and flexibility of the planner, including scenarios contemplating prioritized multirobot planning. Finally, we show that, under practical conditions, the proposed planner can provide time-optimal and globally risk-bounded solutions. | |
