Voronoi-Diagram-Based Nonconvex NMPC in Multi-Obstacle Environments for Robot Systems With Limited Detection Abilities

This paper studies a Voronoi-diagram-based nonconvex nonlinear model predictive control (NMPC) to deal with a tracking problem for a robot system with a limited detection ability in a multi-obstacle scene. Because of the limited detection ability, an auxiliary goal is introduced as an artificial variable that modifies the cost function by adding an offset component, which substitutes for the desired goal in robot motion guidance, ensures the auxiliary goal remains within the limited detection range, and reduces redundant predictions. However, the presence of obstacles destroys the convexity of the robot’s feasible region, which affects the selection of the auxiliary goal and the stability and recursive feasibility of the NMPC. Therefore, to solve the problem, a compression-extension-inflation (CEI) algorithm is proposed to map the nonconvex set to a convex one. Meanwhile, the formulation of NMPC is modified to enable iteration in the mapped convex space. Furthermore, in complex multi-obstacle environments, solely avoiding the nearest obstacle may lead to oscillatory behavior with frequent switching between obstacles. Therefore, the Voronoi diagram is employed to simplify multi-obstacle scenarios to multiple single-obstacle cases by partitioning the detection regions into different cells. A switching mechanism is proposed to determine the sequence of cells for robot motion during tracking. Finally, experiments are carried out using a four-wheel differential (4WD) drive mobile robot to verify the effectiveness of the proposed algorithm and its superiority compared to several state-of-the-art methods. Note to Practitioners—This paper is motivated by robot tracking challenges in obstacle-rich environments with limited detection capabilities. The proposed approach can be applied broadly beyond mobile robots, including industrial manipulators, autonomous vehicles, and aerial drones with various sensing limitations. In practical applications, the auxiliary goal efficiently guides motion when the target is set outside the detection range, significantly reducing computational requirements. The CEI algorithm transforms the nonconvex obstacle-existence spaces into convex spaces, thus ensuring the convergence of NMPC in complex environments. For further implementation, the Voronoi diagram method effectively eliminates the oscillatory issues common in existing solutions. The experimental testing used a precise positioning system OptiTrack and LiDAR for obstacle detection, with the method being extensible to other sensing technologies, which demonstrates that the approach operates efficiently on standard embedded systems. Engineering teams can achieve superior tracking performance in scenarios with incomplete environmental information, with future research extending to dynamic environments and multi-robot coordination systems.