Path planning for wheeled mobile robots using an optimal control approach
Date
2019-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: The capability and practical use of wheeled mobile robots in real-world applications
have resulted in them being a topic of recent interest. These systems
are most prevalent because of their simple design and ease to control. In many
cases, they also have an ability to move around in an environment without any
human intervention. A main stream of research for wheeled mobile robots is
that of planning motions of the robot under nonholonomic constraints.
A typical motion planning problem is to find a feasible path in the configuration
space of the mobile robot that starts at the given initial state and reaches the
desired goal state while satisfying robot kinematic or dynamic constraints.
A variety of methods have been used to solve various aspects of the motion
planning problem. Depending on the desired quality of the solution, an optimal
path is often sought.
In this dissertation, optimal control is employed to obtain optimal collision-free
paths for two-wheeled mobile robots and manipulators mounted on wheeled
mobile platforms from an initial state to a goal state while avoiding obstacles.
Obstacle avoidance is mathematically modelled using the potential field technique.
The optimal control problem is then solved using an indirect method
approach. This approach employs Pontryagin’s minimum principle where analytical
solutions for optimality conditions are derived. Solving the optimality
condition leads to two sets of differential equations that have to be solved simultaneously
and whose conditions are given at different times. This set of
equations is known as a two-point boundary value problem (TPBVP) and can
be solved using numerical techniques.
An indirect method, namely Leapfrog, is then implemented to solve the TPBVP.
The Leapfrog method begins with a feasible trajectory, which is divided
into smaller subdivisions where the local optimal controls are solved. The
locally optimal trajectories are added and following a certain scheme of updating
the number of subdivisions, the algorithm ends with the generation
of an optimal trajectory along with the corresponding cost. An advantage of
using the Leapfrog method is that it does not depend on the provision of good
initial guesses along a path. In addition, the solution provided by the method
satisfies both boundary conditions at every step. Moreover, in each iteration
the paths generated are feasible and their cost decreases asymptotically. To illustrate the effectiveness of the algorithm numerically, a quadratic cost
with the control objective of steering the mobile robot from an initial state to
a final state while avoiding obstacles is minimized. Simulations and numerical
results are presented for environments with and without obstacles. A comparison
is made between the Leapfrog method and the BVP4C optimization
algorithm, and also the kinodynamic-RRT algorithm.
The Leapfrog method shows value for continued development as a path planning
method since it initializes easily, finds kinematically feasible paths without
the need of post processing and where other techniques may fail. To our knowledge
the work presented here is the first application of the Leapfrog method to
find optimal trajectories for motion planning on a two-wheeled mobile robot
and mobile manipulator.
AFRIKAANSE OPSOMMING: Die bekwaamheid en praktiese gebruik van robotte met wiele in werklike toepassings maak dat dit ’n onderwerp van belang is vir navorsing. Hierdie stelsels is algemeen vanweë hul eenvoudige ontwerp en gemak van beheer. Hulle het ook die vermoë om in ’n omgewing rond te beweeg sonder menslike bemiddeling. ’n Hoofstroom van navorsing vir wiel-mobiele robotte is die bewegingsbeplanning van ’n robot onderhewig aan nie-holonomiese beperkings. ’n Tipiese bewegingsbeplanning probleem is om ’n haalbare pad in die konfigurasie-ruimte te vind, vir ’n mobiele robot wat in ’n gegewe aanvangstoestand begin en uiteindelik ’n bestemde doeltoestand moet bereik terwyl kinematiese of dinamiese beperkings bevredig word. ’n Verskeidenheid metodes is al gebruik om verskeie aspekte van die bewegingsbeplanning probleem op te los. Afhangende van die gewensde kwaliteit van die oplossing, word ’n optimale pad dikwels gesoek. In hierdie proefskrif word die bewegingsbeplanning probleem vir ’n tweewiel mobiele robot en mobiele manipuleerder wat op ’n mobiele platform met wiele monteer is, beskou. Hindernis-vermyding word wiskundig met die potensiaalveld-tegniek modelleer. en bewegingsbeplanning word as ’n indirekte optimale beheerprobleem formuleer. Hierdie benadering gebruik Pontryagin se minimum-beginsel, waar analitiese oplossings vir optimaliteitsvoorwaardes afgelei word. Die oplossing van hierdie optimaliteitsvoorwaardes lei na twee stelle differensiaalvergelykings wat gelyktydig opgelos moet word, en waarvan die voorwaardes op verskillende tye gegee word. Hierdie vergelykings staan bekend as ’n tweepunt-randwaardeprobleem (TPRWP), en kan met numeriese tegnieke opgelos word. ’n Indirekte metode, naamlik Leapfrog, word dan implementeer om die probleem op te los. Die Leapfrog-metode begin met ’n haalbare trajek wat in kleiner onderafdelings verdeel word, waar die lokale optimale beheer opgelos word. Die lokaal-optimale trajekte word bymekaar gevoeg, en volgens ’n sekere skema om die aantal onderafdelings op te dateer, eindig die algoritme met die skep van ’n optimale trajek sowel as die ooreenstemmende koste. ’n Voordeel van die Leapfrog-metode is dat dit nie van die voorsiening van goeie aanvanklike skattings vir ’n pad afhang nie. Die paaie wat op elke iterasie deur die metode verskaf word, bevredig ook albei randvoorwaardes. Verder is die paaie wat op elke iterasie geskep word haalbaar, en hul koste neem asimptoties af. Om die doeltreffendheid van die algoritme numeries te demonstreer word ’n kwadratiese koste minimeer, met die beheer-doel om die mobiele robot van ’n aanvanklike toestand tot by ’n finale toestand te bestuur terwyl hindernisse vermy word. Simulasies en numeriese resultate word vir omgewings met en sonder hindernisse aangebied. ’n Vergelyking met die BVP4Coptimeringsalgoritme word gemaak, asook met die kino-dinamiese RRT*- algoritme. Die Leapfrog-metode toon waarde vir verdere ontwikkeling as ’n optimale padbeplanningsmetode, aangesien dit maklik inisialiseer, ’n haalbare pad op elke iterasie skep, en oplossings kan vind waar ander metodes misluk. Sover ons kennis strek is die werk wat hier aangebied word die eerste aanwending van die Leapfrog-metode om optimale trajekte te vind vir bewegingsbeplanning van ’n twee-wiel mobiele robot en mobiele manipuleerder.
AFRIKAANSE OPSOMMING: Die bekwaamheid en praktiese gebruik van robotte met wiele in werklike toepassings maak dat dit ’n onderwerp van belang is vir navorsing. Hierdie stelsels is algemeen vanweë hul eenvoudige ontwerp en gemak van beheer. Hulle het ook die vermoë om in ’n omgewing rond te beweeg sonder menslike bemiddeling. ’n Hoofstroom van navorsing vir wiel-mobiele robotte is die bewegingsbeplanning van ’n robot onderhewig aan nie-holonomiese beperkings. ’n Tipiese bewegingsbeplanning probleem is om ’n haalbare pad in die konfigurasie-ruimte te vind, vir ’n mobiele robot wat in ’n gegewe aanvangstoestand begin en uiteindelik ’n bestemde doeltoestand moet bereik terwyl kinematiese of dinamiese beperkings bevredig word. ’n Verskeidenheid metodes is al gebruik om verskeie aspekte van die bewegingsbeplanning probleem op te los. Afhangende van die gewensde kwaliteit van die oplossing, word ’n optimale pad dikwels gesoek. In hierdie proefskrif word die bewegingsbeplanning probleem vir ’n tweewiel mobiele robot en mobiele manipuleerder wat op ’n mobiele platform met wiele monteer is, beskou. Hindernis-vermyding word wiskundig met die potensiaalveld-tegniek modelleer. en bewegingsbeplanning word as ’n indirekte optimale beheerprobleem formuleer. Hierdie benadering gebruik Pontryagin se minimum-beginsel, waar analitiese oplossings vir optimaliteitsvoorwaardes afgelei word. Die oplossing van hierdie optimaliteitsvoorwaardes lei na twee stelle differensiaalvergelykings wat gelyktydig opgelos moet word, en waarvan die voorwaardes op verskillende tye gegee word. Hierdie vergelykings staan bekend as ’n tweepunt-randwaardeprobleem (TPRWP), en kan met numeriese tegnieke opgelos word. ’n Indirekte metode, naamlik Leapfrog, word dan implementeer om die probleem op te los. Die Leapfrog-metode begin met ’n haalbare trajek wat in kleiner onderafdelings verdeel word, waar die lokale optimale beheer opgelos word. Die lokaal-optimale trajekte word bymekaar gevoeg, en volgens ’n sekere skema om die aantal onderafdelings op te dateer, eindig die algoritme met die skep van ’n optimale trajek sowel as die ooreenstemmende koste. ’n Voordeel van die Leapfrog-metode is dat dit nie van die voorsiening van goeie aanvanklike skattings vir ’n pad afhang nie. Die paaie wat op elke iterasie deur die metode verskaf word, bevredig ook albei randvoorwaardes. Verder is die paaie wat op elke iterasie geskep word haalbaar, en hul koste neem asimptoties af. Om die doeltreffendheid van die algoritme numeries te demonstreer word ’n kwadratiese koste minimeer, met die beheer-doel om die mobiele robot van ’n aanvanklike toestand tot by ’n finale toestand te bestuur terwyl hindernisse vermy word. Simulasies en numeriese resultate word vir omgewings met en sonder hindernisse aangebied. ’n Vergelyking met die BVP4Coptimeringsalgoritme word gemaak, asook met die kino-dinamiese RRT*- algoritme. Die Leapfrog-metode toon waarde vir verdere ontwikkeling as ’n optimale padbeplanningsmetode, aangesien dit maklik inisialiseer, ’n haalbare pad op elke iterasie skep, en oplossings kan vind waar ander metodes misluk. Sover ons kennis strek is die werk wat hier aangebied word die eerste aanwending van die Leapfrog-metode om optimale trajekte te vind vir bewegingsbeplanning van ’n twee-wiel mobiele robot en mobiele manipuleerder.
Description
Thesis (PhD)--Stellenbosch University, 2019.
Keywords
Path planning -- Mathematical models, Optimal control, Mobile robots -- Control systems, Mobile robots -- Programming, Robots -- Motion -- Planning, Nonholonomic dynamical systems, Mobile robots -- Mathematical models, Leapfrog method, UCTD