呂1絲氏4

1 (課程博士(英文))Date of sublnission

Department ofStudentlD Number

D179107

Mecha11ical Engineering
Pplicanfs name(monthday, year)

SupeTvis01

01.06.2021

Uchiyama Naoki

S

Mashimo Tomoaki

Schaeae Tobias Rainer

Abstract Φod吐)T北le ofThesis

Optimal coverage and probabilistic Robust path planning for Nonh010nomic Mobile Robots

Approx.80o words

In recent yeω'S, n〕uch attention is given to autonolnous vel〕1Cles and lnobile robots.1n lndustry
and households,1nobile robots are deployed for a variety of tasks. A σro、Ninσ il〕terest is innlobile robots in households, wha'e it is used for la圦7n mowing and vacuuln cleaning. Mobilerobots are also colnlnonly used for space exploration, specificaⅡy on Nlars, Nlars rova's likeCunosity are used to explore the envlronlnent, and for cleaning traln stations and il〕dustrial
facilities. The above n〕entioned n〕obile robots are using path planning algorithlns to fulfiⅡ
their tasks.1n gen斂'al, these path planning tasks are divided into cova'age path plannil〕g (CPP)and point・to・point (PIP) path planning.1he fonner gena'ates paths ＼Nith an objective ofInoving everywha'e in a preassigned 雛'ea and the latter generates paths from a starting
Position to a goal position while avoiding obstades. cha11enges in these m'eas differ, cpp is il〕
general used in known bounded environments,圦lhile plp is often used in unkno＼Nn, uncertain,
dynalnic environments

GeneraⅡy,1nobile robots have a lilnit power supply due to the facttl〕atthey have to can'y their
Own batteries. Thus, cpp is a power demanding problem for mobile robols. Therefm'e, one ofthe
Objectives of this dissertation is al〕 algorit1Ⅱn th飢 gena'ates optimal cpp paths in known boundedenvirolm)ents, where tl〕e objective of the cost function is either travelinσ time, repetitive visits orenergy c01〕S山nption.1he second objective of this dissertation is a probabilistic robust plp pathPlal]ner that generates probabilistic safe paths in real・time under state and envir0111nent uncertainties
Pattl of this dissertation presents new optimal ofaine approaches to solve u〕e cpp probleln. A
novel hybrid genetic algorid)m (HGA), which uses the turn・away st砥'ting point (TASP) andbacktracking spiral algorithms (BSA) for performing local searches, is proposed for grid・based
envh'onmental representati01〕S.1hree different variations of the HGA are proposed based on
the underlyinσ 10calsearch algorithm: HGA/BSA using the BSA for localsearch, HGA/1ASP
Using the TAsp algorithln and HGA/Both which uses both algorithms for the local se飢'ch
Procedure,1he HGA algorithms are validated usinσ tl〕e f0Ⅱ0、入7ing three different fitness
functions: the number of ce11 Visits, tTaveling time, and a new energy fitness function based
One experimenta11y acquired energy values of fundalnental n〕otions. colnputational results
Show that colnpared to conventional methods, HGA improves paths up t0 38 %; moreover,
HGAs have a consistent fitness for diffa'ent startinσ Positions in an environment. Furthennore,experimental results prove t11e validity of the fitness function.1t lNas sho、Nn, that theHGA/BSA finds good solutions for the nulnber of visited ceⅡS, whereas the HGA/1ASP
Provides better solutions for the traveling time. Botl) variations sl〕0、Ned good results using
energy consumption as fitness function. Furthermore, HGA/TAsp has the fastest computation
time among the HGASPart 110fthe dissertation focuses on control approaches for parking and generating paths
to a specific goal pose, where the focus is in particular on probabilistic robust pathPlanning

A hybrid systems approach to garage parking of a differential drive mobile robot is proposedil〕 this dissertation.1he proposed systeln consists of three systen〕 states, il〕 which each systelnState conva'ges to its deslred control value and u〕en slNitches to the next state.1Wo system
States use input・output linearization for multiple input multiple output (MIMO) systems toConduct exact Hnearization of the plant,、vhich can then be contr0Ⅱed by a Hnear contr011er
S11nulation and experimental results show that the robot converges to its desired states andSafely P砥'ks at the final position in a reasonable ti11〕e10 guaral〕tee safe n)otion plannlng, tl〕e unda'1yil〕σ Pad) planning algorithln n〕ust considern〕otlon uncertalnues and uncertain state information related to static, and dynalnic obstacles

TI〕is dissertation proposes novel hybrid A*(HA*) algorithlns that consider the unC飢'tail〕ty il〕
11〕e n〕otion of a mobile rob01, position uncertainty of static obstades, and position and velocity
UnC磁'tainty of dynamic obslacles. A varial〕t of the HA* algorid〕.m is proposed in tl〕is
dissertation that uses a sofl constrail〕t in the cost function il〕stead of chance constraints for

PI'obability guarantees, this algorithm offers a trade・off between t11e traveling distance andSafety of the path without pruning any addiuonal nodes, Furthennore, this dissa'tation

introduces a method for considering the shape of a mobile robot for probabilistic safe pathPlanning.1he performance of the algorithn〕s was evaluated usino the NI01〕te carlo silnulation
Ihe results showed that safety can be ilnproved without significantly increasing travel
distance.1he lesults also showed tl〕at dynamic obstacles 、入7a'e safely avoided, INhich is inContrast to the conventional HA* algorid〕1n u〕at has a l〕igh probability of c011ision

Furtha'n〕ore, considering d〕e shape of u〕e robot in the proposed probabilistic approach led toSafa' paths overa11. Addi(iona11y, t11e HA* a1σori11)1n that used the chance constraints lNas va'y
ConS釘'vatlve as such, exhibited a V田'y l0圦I probability of c011ision. However, with an
In磁'easlng nun〕ber of obslacles, d〕e algonlhl〕〕 n〕ay fai1 10 find a solulion due to pruning a11theexpanded nodes.1n addition, a probabilistic robuS1 1)1anner 11〕al avoidS 11]e use of tl〕e Gaussian
a1力r function or inva'se Gaussian alor function is proposed. The l'esU11inσ Planner generates
a confidence e11ipse of tl)e curl'en{ slale and coV磁's the resultil〕σ eⅡipse with two circles ofequal radius.1he radius of lhe CⅡ'cles is used lo ina飢e the obstacles and c011ision ＼Nith

Obstacles can be delected wilh detenninistic approaches.1he planner 、Nas able to find
Probabilistic robust paths ＼Nith a slna11el colnputation tilne than existing probabilistic robust
Path planners. Lasdy, a planner is proposed that receives measurelnent feedback from theenvironment and selects the Hnear velocity at each node according to the curTent probability of
COIHsion.1he resulting paths successfU11y avoid static and dynamic obstades and had a shorter
U'ave111ng time than existing planners