Spelling suggestions: "subject:"samplingbased path planning"" "subject:"camping.based path planning""
1 |
Robust sampling-based conflict resolution for commercial aircraft in airport environmentsVan den Aardweg, William 03 1900 (has links)
Thesis (MEng)--Stellenbosch University, 2015. / ENGLISH ABSTRACT: This thesis presents a robust, sampling-based path planning algorithm for commercial airliners that simultaneously
performs collision avoidance both with intruder aircraft and terrain. The existing resolution systems
implemented on commercial airliners are fast and reliable; however, they do possess certain limitations. This
thesis aims to propose an algorithm that is capable of rectifying some of these limitations. The development
and research required to derive this conflict resolution system is supplied in the document, including a
detailed literature study explaining the selection of the final algorithm. The proposed algorithm applies an
incremental sampling-based technique to determine a safe path quickly and reliably. The algorithm makes
use of a local planning method to ensure that the paths proposed by the system are indeed flyable. Additional
search optimisation techniques are implemented to reduce the computational complexity of the algorithm.
As the number of samples increases, the algorithm strives towards an optimal solution; thereby deriving a
safe, near-optimal path that avoids the predicted conflict region. The development and justification of the
different methods used to adapt the basic algorithm for the application as a confiict resolution system are
described in depth. The final system is simulated using a simplified aircraft model. The simulation results
show that the proposed algorithm is able to successfully resolve various conflict scenarios, including the generic
two aircraft scenario, terrain only scenario, a two aircraft with terrain scenario and a multiple aircraft
and terrain scenario. The developed algorithm is tested in cluttered dynamic environments to ensure that
it is capable of dealing with airport scenarios. A statistical analysis of the simulation results shows that the
algorithm finds an initial resolution path quickly and reliably, while utilising all additional computation time
to strive towards a near-optimal solution. / AFRIKAANSE OPSOMMING: Hierdie tesis bied 'n robuuste, monster-gebaseerde roetebeplanningsalgoritme vir kommersiële vliegtuie aan,
wat botsingvermyding met indringervliegtuie en met die terrein gelyktydig uitvoer. Die bestaande konflikvermyding-
stelsels wat op kommersiële vliegtuie geïmplementeer word, is vinnig en betroubaar; dit het egter
ook sekere tekortkominge. Hierdie tesis is daarop gemik om 'n algoritme voor te stel wat in staat is om
sommige van hierdie tekortkominge reg te stel. Die ontwikkeling en navorsing wat nodig was om hierdie
konflik-vermyding-algoritme af te lei, word in die dokument voorgelê, insluitende 'n gedetailleerde literatuurstudie
wat die keuse van die finale algoritme verduidelik. Die voorgestelde algoritme pas 'n inkrementele,
monster-gebaseerde tegniek toe om vinnig en betroubaar 'n veilige roete te bepaal. Die algoritme maak
gebruik van 'n lokale beplanningsmetode om te verseker dat die roetes wat die stelsel voorstel inderdaad
uitvoerbaar is. Aanvullende soektog-optimeringstegnieke word geïmplementeer om die berekeningskompleksiteit
van die algoritme te verlaag. Soos die aantal monsters toeneem, streef die algoritme na 'n optimale
oplossing; sodoende herlei dit na 'n veilige, byna-optimale roete wat die voorspelde konflikgebied vermy.
Die ontwikkeling en regverdiging van die verskillende metodes wat gebruik is om die basiese algoritme aan
te pas vir die toepassing daarvan as 'n konflik-vermyding-stelsels word in diepte beskryf. Die finale stelsel
word gesimuleer deur 'n vereenvoudigde vliegtuigmodel te gebruik. Die simulasie resultate dui daarop dat
die voorgestelde algoritme verskeie konflikscenario's suksesvol kan oplos, insluitend die generiese tweevliegtuigscenario,
die slegs-terreinscenario, die tweevliegtuig-met-terreinscenario en die veelvuldige vliegtuig-enterreinscenario.
Die ontwikkelde algoritme is in 'n beisge (cluttered), dinamiese omgewing getoets om te
verseker dat dit 'n besige lughawescenario kan hanteer. 'n Statistiese ontleding van die simulasie resultate
bewys dat die algoritme vinnig en betroubaar 'n aanvanklike oplossingspad kan vind, addisioneel word die
oorblywende berekeningstyd ook gebruik om na 'n byna optimaleoplossing te streef.
|
2 |
Learning and monitoring of spatio-temporal fields with sensing robotsLan, Xiaodong 28 October 2015 (has links)
This thesis proposes new algorithms for a group of sensing robots to learn a para-
metric model for a dynamic spatio-temporal field, then based on the learned model
trajectories are planned for sensing robots to best estimate the field. In this thesis
we call these two parts learning and monitoring, respectively.
For the learning, we first introduce a parametric model for the spatio-temporal
field. We then propose a family of motion strategies that can be used by a group
of mobile sensing robots to collect point measurements about the field. Our motion
strategies are designed to collect enough information from enough locations at enough different times for the robots to learn the dynamics of the field. In conjunction with
these motion strategies, we propose a new learning algorithm based on subspace
identification to learn the parameters of the dynamical model. We prove that as the
number of data collected by the robots goes to infinity, the parameters learned by
our algorithm will converge to the true parameters.
For the monitoring, based on the model learned from the learning part, three
new informative trajectory planning algorithms are proposed for the robots to collect the most informative measurements for estimating the field. Kalman filter is used
to calculate the estimate, and to compute the error covariance of the estimate. The
goal is to find trajectories for sensing robots that minimize a cost metric on the
error covariance matrix. We propose three algorithms to deal with this problem.
First, we propose a new randomized path planning algorithm called Rapidly-exploring
Random Cycles (RRC) and its variant RRC* to find periodic trajectories for the
sensing robots that try to minimize the largest eigenvalue of the error covariance
matrix over an infinite horizon. The algorithm is proven to find the minimum infinite
horizon cost cycle in a graph, which grows by successively adding random points.
Secondly, we apply kinodynamic RRT* to plan continuous trajectories to estimate
the field. We formulate the evolution of the estimation error covariance matrix as a
differential constraint and propose extended state space and task space sampling to
fit this problem into classical RRT* setup. Thirdly, Pontryagin’s Minimum Principle
is used to find a set of necessary conditions that must be satisfied by the optimal
trajectory to estimate the field.
We then consider a real physical spatio-temporal field, the surface water temper-
ature in the Caribbean Sea. We first apply the learning algorithm to learn a linear
dynamical model for the temperature. Then based on the learned model, RRC and
RRC* are used to plan trajectories to estimate the temperature. The estimation
performance of RRC and RRC* trajectories significantly outperform the trajectories
planned by random search, greedy and receding horizon algorithms.
|
Page generated in 0.1166 seconds