Toward Dependable Multiple Path Planning for Autonomous Robots with Obstacle Avoidance and Congestion Control

Sammanfattning: Over decades, automatic robots that are pre-programmed to perform repetitive tasks in industrial production has been reaching the cutting edge of technology. There is emerging the next development with autonomous control, where a robot is able to have some levels of its own decision, i.e. self-governing, without direct controls from humans. This brings autonomous robots extensively applicable not only in industry but also in commonly accessible services in our daily life such as self-driving cars, automated health care, or entertainment. Yet, one of the backbone of the robotic system, the navigation and path planning, has to face more and more challenges including unstructured environments, uncertainty of moving objects, coexist with humans, and multiple robotic agents. Aiming toward a dependable, i.e. available, reliable, and safe, path planning system to overcome such challenges, this thesis proposes the development of multiple path planning along with obstacle avoidance and congestion control algorithms. At first, a novel dipole flow field, which is constructed from a flow field to drive robots to their goals and a dipole field to push robots far away from potential collision directions, is proposed. The algorithm is efficient in implementation yet is able to overcome the drawback of conventional field-based approach, which is easily trapped by a local optimisation of energy functions.  Secondly, a congestion control mechanism with Petri net is developed to synchronise the movement of robots when they enter in a cross or narrow area. Different Petri nets are evaluated to find the optimal configuration to reduce the traffic jam through possible conflict regions. In the next contribution, the dead- or live-lock problem of a path planning system is addressed. The solution is based on multiple path planning where each robot has alternative paths to the goal. All robots in the same working space communicate with each other to update their locations and paths so that the appropriate configuration can be chosen to avoid potential deadlocks. The algorithm also takes into account the obstacle avoidance so that the robots are able to avoid mutual collisions as well as collisions with unexpected moving objects like humans. Finally, a distributed multiple path planning algorithm is implemented to help the system to deal with some level of failures, which happens when the central controlling system of robots stops working or a part of communication network between the robots is unexpectedly disconnected. The proposed approaches have been evaluated by extensive experiments to show their effectiveness in addressing collisions, congestion, as well as deadlocks. The implementation of the algorithms has been performed on widely accessible platform, robot operating system (ROS) and transferred into real robots.