Optimization and Mathematical Modelling for Path Planning of Co-operative Intra-logistics Automated Vehicles

Small indoor Autonomous Vehicles have revolutionized the operation of pick-pack-and-ship warehouses. The challenges for path planning and co-operation in this domain stem from uncontrolled environments including workspaces shared with humans and human-operated vehicles. Solutions are needed which scale up to the largest existing sites with thousands of vehicles and beyond. These challenges might be familiar to anyone modelling road traffic control with the introduction of Autonomous Vehicles, but key differences in the level of decision autonomy lead to different approaches to conflict-resolution. This thesis proposes a decomposition of site-wide conflict-free motion planning into individual shortest paths though a roadmap representing the free space across the site, zone-based speed optimization to resolve conflicts in the vicinity of one intersection and individual path optimization for local obstacles. In numerical tests the individual path optimization based on clothoid basis functions created paths traversable by different vehicle configurations (steering rate limit, lateral acceleration limit and wheelbase) only by choosing an appropriate maximum longitudinal speed. Using two clothoid segments per convex region was sufficient to reach any goal, and the problem could be solved reliably and quickly with sequential quadratic programming due to the approximate graph method used to determine a good sequence of obstacle-free regions to the local goal. A design for zone-based intersection management, obtained by minimizing a linear objective subject to quadratic constraints was refined by the addition of a messaging interface compatible with the path adaptations based on clothoids. A new approximation of the differential constraints was evaluated in a multi-agent simulation of an elementary intersection layout. The proposed FIFO ordering heuristic converted the problem into a linear program. Interior point methods either found a solution quickly or showed that the problem was infeasible, unlike a quadratic constraint formulation with ordering flexibility. Subsequent tests on more complex multi-lane intersection geometries showed the quadratic constraint formulation converged to significantly better solutions than FIFO at the cost of longer and unpredictable search time. Both effects were magnified as the number of vehicles increased. To properly address site-wide conflict-free motion planning, it is essential that the local solutions are compatible with each other at the zone boundaries. The intersection management design was refined with new boundary constraints to ensure compatibility and smooth transitions without the need for a backup system. In numerical tests it was found that the additional boundary constraints were sufficient to ensure smooth transitions on an idealized map including two intersections.