Motion planning is the field of computer science that aims at developing algorithmic techniques allowing the automatic computation of trajecto- ries for a mechanical system. The nature of such a system vary according to the fields of application. In computer animation it could be a humanoid avatar. In molecular biology it could be a protein. The field of application of this work being aerial robotics, the system is here a four-rotor UAV (Unmanned Aerial Vehicle) called quadrotor. The motion planning problem consists in computing a series of motions that brings the system from a given initial configuration to a desired final configuration without generating collisions with its environment, most of the time known in advance. Usual methods explore the system’s configuration space regardless of its dynamics. By construction the thrust force that allows a quadrotor to fly is tangential to its attitude which implies that not every motion can be performed. Furthermore, the magnitude of this thrust force and hence the linear acceleration of the center of mass are limited by the physical capabilities of the robot. For all these reasons, not only position and orientation must be planned, higher derivatives must be planned also if the motion is to be executed. When this is the case we talk of kinodynamic motion planning. A distinction is made between the local planner and the global planner. The former is in charge of producing a valid trajectory between two states of the system without necessarily taking collisions into account. The later is the overall algorithmic process that is in charge of solving the motion planning problem by exploring the state space of the system. It relies on multiple calls to the local planner. We present a local planner that interpolates two states consisting of an arbitrary number of degrees of freedom (dof) and their first and second derivatives. Given a set of bounds on the dof derivatives up to the fourth order (snap), it quickly produces a near-optimal minimum time trajectory that respects those bounds. In most of modern global motion planning algorithms, the exploration is guided by a distance function (or metric). The best choice is the cost-to-go, i.e. the cost associated to the local method. In the context of kinodynamic motion planning, it is the duration of the minimal-time trajectory. The problem in this case is that computing the cost-to-go is as hard (and thus as costly) as computing the optimal trajectory itself. We present a metric that is a good approximation of the cost-to-go but which computation is far less time consuming. The dominant paradigm nowadays is sampling-based motion planning. This class of algorithms relies on random sampling of the state space in order to quickly explore it. A common strategy is uniform sampling. It however appears that, in our context, it is a rather poor choice. Indeed, a great majority of uniformly sampled states cannot be interpolated. We present an incremental sampling strategy that significantly decreases the probability of this happening.
| Identifer | oai:union.ndltd.org:univ-toulouse.fr/oai:oatao.univ-toulouse.fr:20169 |
| Date | 05 July 2017 |
| Creators | Boeuf, Alexandre |
| Contributors | Institut National Polytechnique de Toulouse - INPT (FRANCE), Laboratoire d'Analyse et d'Architecture des Systèmes - LAAS (Toulouse, France) |
| Source Sets | Université de Toulouse |
| Language | English |
| Detected Language | English |
| Type | PhD Thesis, PeerReviewed, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | http://oatao.univ-toulouse.fr/20169/ |
Page generated in 0.0155 seconds