OPTEC - K.U.Leuven Center of Excellence: Optimization in Engineering

Abstract

From the times of the industrial revolution enormous efforts have been aimed to the automation and the fulfillment of technological progress. Since then not only production systems, but also the well-being of mankind have undergone a revolution. The invention of electronics allowed giant leaps and opened the doors to new technologies. Nowadays this development is far away from interrupting and automation has reached peaks that only a few years ago nobody would imagine.

In the field of automation, motion planning has gone through years of great advance, allowed by the increasing computational power of modern computers combined with the large quantity of studies related to this problem. From the beginnings of motion planning studies, a large number of methods have been developed, which robustness and precision haven't ceased to increase. Some of these techniques, as potential fields, are rather simple; other methods as optimal control on the other hand, are particularly complex. The complexity itself is the main limiting factor to the application of optimal control, as the majority of the problems are extremely hard to solve.

The great demand for vehicle models to be increasingly accurate in order to guarantee precise trajectory computation does not allow the use of simple kinematic models and the rolling constraints must be replaced by detailed tire models, able to characterize accurately the contact forces. This necessity makes the problem more complicate and makes it impossible to solve real-time optimal control problems.

Two motion planning techniques have become particularly popular: the RRTs and the roadmaps. The first ones, better suited for single-query applications, explore the state space building a trajectory tree until the goal state is reached. The second ones, better suited for multiple-query applications, consist of two phases: the offline construction of a trajectory graph and the online search of the graph for the solution. The possibility to build the graph offline makes the roadmap technique particularly suitable for the combined use of optimal control algorithms with accurate vehicle models for local planning.

This thesis presents the development of a robust, versatile planner operating into semi-structured or even non-structured environments in the framework of the AGILE European project. The aim of the project is to allow a commercial application for an autonomous forklift able to respond to high-level requirements (eg: search and lift a pallet situated in a certain area) by translating them into low-level requirements (motion planning). This ability shall be provided by the use of the best and most advanced planning techniques available today operating with an accurate vehicle model in order to guarantee for the feasibility of planned trajectories.