NTNU Norwegian University of Science and Technology Faculty of Engineering Department of Marine Technology
Mas ter’ s thesis
Yuhan Chen
Temporally Deconflicted Path
Planning for Multiple Marine Vehicles
Master’s thesis in Marine Technology Supervisor: Vahid Hassani
June 2019
Yuhan Chen
Temporally Deconflicted Path Planning for Multiple Marine Vehicles
Master’s thesis in Marine Technology Supervisor: Vahid Hassani
June 2019
Norwegian University of Science and Technology Faculty of Engineering
Department of Marine Technology
Summary
Over the past few years, growing interests and demands have been witnessed in the de- velopment of Automatic Surface Vehicle(ASV) operation, especially in controlling fleet of vehicles to perform complex missions. Basing on the path planning algorithm which generates single path between two points, guiding multiple vehicles to their own ends while avoiding possible inter-vehicle collisions brings more challenges and thus requires more versatility. These kind of algorithms need to first consider goal related influencing factors like environmental constraints and vehicle dynamics. In multiple vessels scenario there would also be some specific requirements like path deconfliction in time or space, final arrival synchronizing or avoiding inter-vehicle communication constraints. Further, measurements and optimized solutions will also be needed, such as energy and length min- imized path.
The multiple path planning algorithm is developed basing on single path generation opti- mization algorithm using B´ezier curves. For arbitrary number of vehicles, path planning algorithm capable of leading each vehicle to its assigned target is proposed. For vehicle motion at the intersection points, temporal deconfliction is an important issue to be taken care of. To avoid inter-vehicle collisions, first the motion along the whole path and its cor- responding speed need to be defined. After assigning the speed, time profile of each point could be obtained, as well as the distance between two vehicles at a certain time instant.
Further, for the crossing point which would be shown geometrically on the path, tempo- ral deconfliction are formulated as constraints in the framework of optimization problem, as well as vehicle dynamic like velocity and acceleration restrictions, in order to satisfy the physical limitations and avoid problems in path following. Cost function is chosen to penalize the exceeding operation time, thus a feasible solution with shortest time and smooth speeding process could be obtained. And despite of the different length of path, they would finally arrive simultaneously.
Finally, a series of simulation results are presented in the last chapter, showing the feasi- bility and efficiency of the algorithm in multiple path planning. By presenting simulation scenarios with different conditions like path number, random obstacles and velocity lim- itations, the versatility of the proposed algorithm could be shown as well. By this end, the conclusion could be made that paths for arbitrary number of vessels are temporally deconflicted with simultaneous arriving time. Some challenges so far still existing would be revealed through discussion, and indicate some crucial points for the future work.
Preface
This thesis was carried out during the spring semester of 2019, at the Norwegian Univer- sity of Science and Technology(NTNU) as a conclusion for my study in the Department of Marine Technology.
My years at NTNU have been an unforgettable experience, and would be tough if without the support from my family and friends. Marine cybernetic is a new field for me, and it truly brings me challenges and joy. It is never easy to start from somewhere new, but the sense of achievement would make every hard and frustrating time worth it.
Thanks to my supervisor Vahid Hassani, for all the profitable discussions and encour- agement throughout the year. And specially thanks to my parents, who would always be there for me with selflessly support. I would never be where I am if it were not their un- derstanding. Also thanks to my friends who always invite me to dinner, since they know how bad I am at cooking. I have learnt a lot during these two years, and hopefully this final work would be useful for someone who works with similar problems.
Yuhan Chen
Trondheim, June 10, 2019
Table of Contents
Summary i
Preface ii
Table of Contents iv
List of Tables v
List of Figures viii
1 Introduction 1
1.1 Motivation . . . 1
1.2 Previous work . . . 3
1.3 Objective . . . 3
1.4 Contribution . . . 4
1.5 Structure and Limitations . . . 4
1.5.1 Outline . . . 4
1.5.2 Limitation . . . 5
1.6 Preliminaries . . . 6
1.6.1 List of Abbreviations . . . 6
2 Theoretical Background 7 2.1 Path planning . . . 7
2.1.1 Motion control system . . . 7
2.1.2 Path planning algorithm . . . 8
2.1.3 Formulation and Parameterization . . . 9
2.1.4 Global and Local Methods . . . 11
2.2 B´ezier Curve . . . 12
2.2.1 Background . . . 12
2.2.2 History . . . 12
2.2.3 General Formulations . . . 13
2.2.4 Matrix Form . . . 15
2.2.5 De Casteljau’s algorithm . . . 16
2.2.6 Lowering and elevating curve order . . . 16
2.2.7 Derivatives . . . 17
2.3 Trajectory optimization . . . 18
2.4 Vehicle Modeling . . . 20
2.4.1 Kinematics . . . 20
2.4.2 Variable Notations . . . 20
2.4.3 Transformation between BODY and NED . . . 21
3 Multiple Path Planning and Deconfliction 23 3.1 Multiple path planning algorithm . . . 23
3.2 Temporal deconfliction . . . 25
3.3 Spatial deconfliction . . . 27
3.4 Related work . . . 29
3.4.1 Path generation algorithm . . . 29
3.4.2 Multiple path planning . . . 29
3.4.3 Optimization method . . . 31
4 Deconfliction and optimization 33 4.1 Preliminary description . . . 33
4.1.1 Method . . . 33
4.1.2 Objectives . . . 34
4.2 Optimization formulations . . . 36
4.2.1 Optimization variables . . . 37
4.2.2 Objective function . . . 37
4.2.3 Constraints . . . 38
4.3 Implementation . . . 42
4.3.1 Implementation environment . . . 42
4.3.2 Parameters . . . 42
4.3.3 Motion representation . . . 43
5 Numerical simulation 45 5.1 Preliminary comments . . . 45
5.2 First scenario . . . 46
5.3 Second scenario . . . 49
5.4 Third scenario . . . 52
5.5 Fourth scenario . . . 56
6 Discussion 61 7 Conclusion and future work 65 7.1 Conclusion . . . 65
7.2 Future work . . . 67
Bibliography 69
List of Tables
2.1 The notation of SNAME (1950) for marine vessels . . . 21
4.1 Parameters for path planning . . . 42
4.2 Parameters for temporal deconfliction path planning . . . 43
5.1 Parameters for path planning in first scenario . . . 46
5.2 Parameters for temporal deconfliction path planning in the first scenario . 48 5.3 Time intervals for each vehicle passing danger zone in the first scenario . 48 5.4 Parameters for path planning in second scenario . . . 49
5.5 Parameters for temporal deconfliction path planning in the second scenario 50 5.6 Time intervals for each vehicle passing danger zone in the second scenario 51 5.7 Parameters for path planning in third scenario . . . 52
5.8 Parameters for temporal deconfliction path planning in the third scenario . 53 5.9 Time intervals for each vehicle passing danger zone in the third scenario . 55 5.10 Parameters for path planning in fourth scenario . . . 56 5.11 Parameters for temporal deconfliction path planning in the fourth scenario 57 5.12 Time intervals for each vehicle passing danger zone in the fourth scenario 60
List of Figures
1.1 GNC signal flow from Fossen (2011) . . . 2
2.1 Robot with obstacles and in a joint space from Carbone and Gomez-Bravo (2015) . . . 8
2.2 Two example methods in path planning techniques in Roald (2015) . . . . 9
2.3 Bezier Curves in Novin (2016) . . . 14
2.4 Example B´ezier Curve . . . 15
2.5 Body-fixed reference for marine craft from Fossen (2011) . . . 21
3.1 Multiple path planning system from H¨ausler et al. (2009) . . . 24
3.2 Temporal deconfliction for multiple path planning . . . 26
3.3 Spatial deconfliction for multiple path planning in H¨ausler et al. (2009) . 27 4.1 Searching for the boundaries of the danger zone . . . 39
4.2 Time deconfliction for two vehicles . . . 40
4.3 Example velocity figure . . . 42
5.1 Generated paths and obstacles in the first scenario . . . 46
5.2 Corresponding velocity for each path in the first scenario . . . 47
5.3 Generated temporal deconfilicted paths for the first scenario . . . 47
5.4 Generated paths and obstacles in the second scenario . . . 49
5.5 Corresponding velocity for each path in the second scenario . . . 50
5.6 Generated temporal deconfilicted paths for the second scenario . . . 51
5.7 Generated paths and obstacles in the third scenario . . . 52
5.8 Corresponding velocity for each path in the third scenario . . . 53
5.9 Generated temporal deconfilicted paths for the third scenario . . . 54
5.10 Generated temporal deconfilicted paths for Area 1 . . . 54
5.11 Generated temporal deconfilicted paths for Area 2 . . . 55
5.12 Generated paths and obstacles in the fourth scenario . . . 56
5.13 Corresponding velocity for each path in the fourth scenario . . . 57
5.14 Generated temporal deconfilicted paths for the fourth scenario . . . 58
5.15 Generated temporal deconfilicted paths for Area 1 . . . 58 5.16 Generated temporal deconfilicted paths for Area 2 . . . 59 5.17 Generated temporal deconfilicted paths for Area 3 . . . 59
Chapter 1
Introduction
1.1 Motivation
While we are paying much attention to the outer space, there is an enormous part of the world which is still hiding in the ocean. The ocean covers 71% of the planet surface and contains the 99% live space. Most of it is unreachable and dangerous to explore, requiring the development of the Autonomous Surface Vehicles(ASV). The information from ocean exploration is vital for nearly all the fields: biology, chemistry, physic, geology, and even archaeology, etc, and its great potential commercial benefits attracts many companies and governments as well. Moreover, ocean is playing a crucial and significant part in military.
These all make ocean becoming a focus of researchers and scientists, promoting the de- velopment of automatic technology.
Path planning and trajectory generation has long been a crucial problem for automation, and has been studied for years, especially in the field of Unmanned Surface Vehicle(USV).
The current trend for developing USV is to perform tasks without human intervention, achieving higher level of autonomy while being able to deal with unpredictable accidents.
This gives big challenges on the motion control system of the USVs, of which path gener- ation and planning algorithm is only a part.
The motion control system is usually constructed as guidance, navigation and control(GNC) systems, which usually constitutes by three interconnected subsystems respectively, ac- cording to the definition of Fossen (2011) theory. These systems corporate with each other by exchanging data and signals like flows, and their main structure could be illustrated as follows in Figure 1.1. The main tasks for the three subsystem is: Guidancecontinu- ously collects data from external sensors or computers to perform calculation about model dynamics like velocity, acceleration or heading, etc, and then transmits these data to the human operator. Navigation refers to the action that determines the reference position, course and distance to lead the vehicle. Sometimes even the acceleration and velocity are determined at the same time. To do this, a global navigation satellite system combined
Figure 1.1:GNC signal flow from Fossen (2011)
with motion sensors like accelerometers and gyros is basically needed. Control, to be more specific, should be called motion control. This is to determine the desired forces and moments needed by the craft to achieve control objectives, such as minimum energy, path following, trajectory tracking and maneuvering control. These objectives are usually seen in conjunction with the guidance system.
In the path planning algorithm, most of the time plenty of feasible solutions that satisfy all the constraints could be proposed in the end. In order to make the final choice a criteria should be set for the optimization purpose. Usually the whole operating duration of the craft is expected to be as much short as possible, to save energy or increase the efficiency, which however may lead the robots to operating under high speed and steep path follow- ing. This would expose the craft to the risk of damaging, such as vibration of machine structures, wear and tear of actuators, and inaccuracy and unstable of the system as well.
Such a trade-off process leads to the need of proper path planning and trajectory genera- tion algorithm, paving a smooth path avoiding excessive accelerations and sharp curvature, while minimize the duration cost. For such reasons, path planning algorithm has been pro- posed, generating a geometric path from the initial point to the destination, and bypassing all the obstacles along the way. The crucial tasks further asks for the cooperation between multiple robots operating in the same scenario and avoid collisions between each other.
To deal with this kind of problem from the aspect of temporal deconfliction, time profile for the whole process is required additionally, compared to path planning algorithms. And because of this time coordinate augment, the path could then be related to motion dynam- ics like velocity, therefore could be analyzed numerically. Besides, it could be resolved in another different way, that all the vehicles need to keep a fixed minimum safe distance between each other, and their routes would never cross or get close in the two dimensional space, despite of the operating time. This method is called spatially deconflicted path planning algorithm. These two ideas for deconfliction would be further introduced in later chapter.
Although lots of attention have been paid in developing more autonomous unmanned ma-
rine vehicles, there are still many significant problems remain unsolved. Some of them lie in the accuracy of a good local and global planners, some may be the computational limitations during the process of planning, where more intelligent and efficient planning or better structured algorithm are needed. Greater effort should be kept making to achieve higher level automation for the future development in Unmanned Surface marine vehicles.
1.2 Previous work
In Lande (2018), a new path planning algorithm for marine vehicles using B´ezier curves is proposed. It explores the capability of high order B´ezier curves in generating smooth and continuous curves in two dimensional space, and take the advantages of its properties and relationships between control points and points on the curves. This algorithm is capable of leading a path that could avoid randomly generated static obstacles, with other vessels nearby and system dynamic limitations taken into considerations as well, in a local 2D space within certain boundaries. It specifically generates a feasible path between two fixed points which isG2andC2 continuous, while constraining the curvature along the path to ensure the result would never exceed the physical limits. Also it includes the vessel dynamic capabilities by using properties of differential flatness, to define a cost to the path.
And further, different scenarios of simulations for developed algorithm are implemented in MATLAB, and results and existing challenges are presented and discussed by the end of this thesis work. His work for single path generation algorithm provides a basis for this thesis in path generation part.
1.3 Objective
The overall objective of this thesis is aiming at proposing a multiple vehicles path plan- ning algorithm which avoids inter-vehicle collision and performs simultaneous arrival, for underactuated USVs and ASVs. To achieve this goal, a set of sub-objectives has been set as following to guarantee the main success:
• Perform background literature survey on multiple path planning algorithms, B´ezier curves formulations and optimization algorithms.
• Research on the general framework of temporally and spatial deconfliction for mul- tiple vehicle scenario, and its formulation and methods.
• Develop an arbitrary number of path planning algorithm, and mark the intersection points which would geometrically presented in the route map.
• Assign the speed for the whole path, and formulate temporal deconfliction con- straints and cost functions within the framework of optimization problems.
• Include the vehicle dynamics like acceleration and velocity, to constrain the velocity and ensure the continuity of the motion.
• Simulate in Matlab and improve the functions basing on the result. Discuss the final result and analyze.
1.4 Contribution
This thesis is mainly contributing a method in multiple marine vehicle path planning with temporal deconfliction. Firstly, related background theories is introduced, including the topic of Bezier curve, vehicle mathematical modeling, temporal and spatial deconfliction.
Basing on the path planning algorithm for one path, arbitrary number of paths are gener- ated and speed assignment is proposed to obtain time profile along the path. The crossing points which consequently presented would be taken special care of. Specifically, con- straints are formulated within the vicinity of every intersection point in the frame of opti- mization problem, to get staggered time of passing crossing point and avoid inter-vehicle collisions. Further, final target arriving time for each vessel is constrained, as well as ve- hicle dynamics like velocity and acceleration allowed in a certain range, in order to obtain smooth speeding process. The total operating time is minimized as well, at the final stage.
Thus the proposed multi-path planning algorithm could lead arbitrary number of vehi- cles to arrive at assigned destinations respectively, with inter-vehicle collisions avoidance.
It would provide solutions in time to form smooth and continuous velocity profiles, with reasonable velocity and acceleration constraints taken into account. Finally, despite the different length of every path, each vehicle would arrive at target simultaneously with same shortest operation time. The behavior is discussed at last by presenting sets of nu- merical simulation results, and to present the efficiency of the algorithm.
1.5 Structure and Limitations
1.5.1 Outline
Main outline of this thesis is constructed as followings:
Chapter 2: This chapter mainly presents introductions to some background theories and concepts, such as path planning algorithm, B´ezier curves and trajectory optimization, along with some mathematical definitions and properties being used, serving as the the- oretical support for this thesis. It also provides a mathematical model for an surface vessel.
Chapter 3: This chapter presents some important algorithms related to the topic of mul- tiple vehicle path planning and deconfliction methods, as the main reference literature. It also introduces a range of related work as the result of the literature survey.
Chapter 4: The main concern is to develop the mathematical formulations of the pro- posed algorithm, basing on the theories introduced in the preceding chapters, and further describe the implementation in the numerical simulation environment MATLAB within the framework of optimization problems.
Chapter 5: This chapter presents the simulation results for four different scenarios, to show the efficiency of the proposed algorithm in arbitrary number of path temporal decon- fliction planning problem.
Chapter 6: This chapter discusses the existing problems and challenges basing on the simulation result shown in Chapter 5 and during the process of simulation.
Chapter 7: This chapter presents the conclusions for the overall problem, and discusses some possible improving directions for the future work basing on what this thesis obtained so far.
1.5.2 Limitation
The main limitation in this thesis should be the optimization formulation and a good op- timizer. The resulting velocity curves obtained so far still exist oscillation and could not be smoothed perfectly, although the speed changing rate meets the requirement. And the current optimization solver shows a dependency on the value of finite different step size, which is an issue in the obtainment of satisfactory result.
Also the computational time and efficiency is another problem to be considered, espe- cially when dealing with a complicated situation with a large number of multiple vehicles.
This would be important when the vehicle needs online modification and path replanning, and thus disallowing the deviation occurs as well.
1.6 Preliminaries
1.6.1 List of Abbreviations
GNC Guidance, Navigation and Control System ASV Autonomous Surface Vehicle
USV Unmaned Surface Vehicle
2D Two dimension
3D Three dimension
GNSS Global Navigation Satellite System GPS Global Positioning System
CAD Computer Aided Design CAM Computer Aided Manufacturing CAGD Computer Aided Geometric Design SQP Sequential Quadratic Programming ECEF Earth-centered Earth fixed
Chapter 2
Theoretical Background
2.1 Path planning
2.1.1 Motion control system
Motion control typically refers to control the motion of moving objects like position, ve- locity or accelerations, by motion controllers and actuators. It is a sub-field of automation, and usually carried out in the following structure:
• Motion controllers, to calculate and output the set points or desired motion as control signals to the next stage.
• Amplifiers who receives the control signals from controllers and transform them into the number of forces or torques that actuators needs to produce, in order to reach the desired set points.
• Actuators or motors are what produce thrusts or forces for vehicles to execute de- sired motion, for example hydraulic pump or engine. For marine vessels, actuators are usually propellers or azimuth thrusters.
Motion control systems could either be in open loops or closed loops. In open loop systems the controller send commends out and never know whether the motion has been carried out successfully in the end, thus is less precise and unguaranteed but easy in implementa- tion. For more precised ones an observing system could be added to measure the output and transform it back to the controller as signal, thus the controller could be aware of the deviation and knows how much should be compensated.
This control theory could further be combined with path planning algorithm, in the co- operation with GNC systems which are introduced in Chapter 1.1 above. The result a path planner outputs is input into the Guidance sub-system, and thus being computed as refer- ence position, velocity and acceleration to guide the vehicle to the destination. Navigation
sub-system locates the position of the vehicles in the coordinates and determines the ve- hicle dynamics by using Global Navigation Satellite System(GNSS) or motion sensors.
And motion control finally collects these data and determines the force or torque needed to achieve control objectives, like following the desired path.
2.1.2 Path planning algorithm
Path planning problems is about how to generate one or more feasible routes from initial to the final point, and basically a geometric problem. In the most simplified situation, it is normally working within a static 2D or 3D plane with fixed coordinate system despite the change of time. Here the whole environment within regional boundaries, and static constraints are all known. In a more complex and autonomous situation, one might need to deal with a dynamic environment where the environment is only partially known, with kinematic and dynamic constraints. In comparison to this, the definition of trajectory plan- ning includes assigning a proper time law to the static path, besides performing feasible path planning. The definition of path planning from Carbone and Gomez-Bravo (2015) is straightforward:
Definition 2.1.1. Path Planning: Find a collision-free motion between an initial (start) and a final configuration (goal) within a specified environment.
Operation Space
Some general definitions about the operating space should be introduced about the path planning problem, as:
• The configuration space,C−space;
• The space of free configurations,C−f ree;
• The obstacle’s representation in configuration space,C−obs;
Figure 2.1:Robot with obstacles and in a joint space from Carbone and Gomez-Bravo (2015) The term configuration refers to the location of the robot or vehicle, and its orientation in the space with respect to the reference frame, which is shown in the left of Figure 2.1,Fw. Thus the configuration space is the set of all possible configurations. For another robot in the right of Figure 2.1, theC−spaceneeds to be presented in a joint space, thus the
C−obscould be described as following, andC−f reecould be represented as{C−space -C−f ree}.
In the process of producing the feasible route, the handling with constraints is a crucial problem. Most of the time the purpose of setting constraints is to ensure the operation safety, or to make sure it is achievable for the vehicle to follow the path. Dynamic and kinematic constraints includes the curvature of the path or turning radius, for example.
And ensuring the safety refers to keep a safe distance with other vehicles and obstacles, to avoid crushing. Once all the dynamic and environment constraints are satisfied, the route would be considered as a feasible one, and most of the time the set of feasible solu- tions could be rich. Under this circumstance, a cost function, based on different objectives would be needed to evaluate each path, such as minimum execution time or length, and minimum energy.
Figure 2.2:Two example methods in path planning techniques in Roald (2015)
Path planning has long been a significant topic when it comes to the field of automation, and has been in development ever since 1970s. Now after such a long period, there are plenty of technology which are capable of generating path and perform path planning.
Some based on the graphical techniques (like Figure2.2), exploring the feasible way in dimensional space, and other might based on artificial potential methods. Some alterna- tive approaches also take advantage of probabilistic algorithms, such as random sampling in building the roadmap, and has done excellent work in complex path planning situa- tion. Every methodology has its own potential and field for implementation, and here in this thesis, mathematical modeling and optimization is utilized, and would be presented in following chapters.
2.1.3 Formulation and Parameterization
General Parameterization
Generally in path planning, a path, or route, could be constituted by one or several seg- ments of parametric curves. In mathematics, parametric curve is a set of equationsx=
f(t)andy =g(t), that trace a curveC when parametertvaries in its domain. In most cases the parametertis used to symbolize ”time” for a curve.
A parametric curve could either be defined separately by using two functionf(t)andg(t), representing x-coordinate and y-coordinate respectively with a third parametert, or could just be described using a scalar parameter$, as following set (Breivik and FossenBreivik and Fossen (2009), 2009):
P :={p∈R2|p=pp($) ∀$∈R} (2.1) Here the path is considered as a planar path, and all the points on the curve is described in one dimension aspp($)=[xp($), yp($)]T ∈R2. The parameter$takes domain in the interval$∈[$0, $1].
In Hausler and Ghabcheloo (2009)H¨ausler et al. (2009), the path is parameterized by using an algebraic polynomial of degreeN, such as,x(τ)is of the form:
x(τ) =
N
X
k=0
axkτk i= 1,2,3, (2.2)
The number of degreeNof the polynomialx(τ),y(τ),z(τ)is determined by the number of boundary conditions needed to be satisfied. The parameterτcould be further be param- eterized by timetasτi(t), which gives the potential for assigning a proper time laws that allocate the nominal speed for vehicles along the path.
Piecewise curves
If the path calculation is quite complicated and requires for more versatility, only one segment of parametric curve might not suffice to meet the requirements. Thus piecewise curves with different length of segments connected together are a good choice to express complex shape. Compared with single curves, this might increase more possibilities in extending in space, but also place extra limitations on the connection points, for example continuity in curvature and turning radius. If the path planner consists of allocating a time law, the velocity and accelerations on transition points should be constrained additionally as well. Apart from this, complex shape could also be represented by high order single curve, which may lead to unstable performance and higher level function complexity and computational loads indeed. According to Lekkas (2014)Lekkas (2014), for path that composed by a number of curve segments, every segment could be described as the set:
P:={pi∈R2|pi=pi,p($) ∀$∈ Ii= [$i,0, $i,1]⊂R} (2.3)
And the path could be expressed as:
Ps=
m
[
i=1
Pi. (2.4)
In this thesis, piecewise curve is also utilized in the path planning algorithm in generat- ing feasible route using B´ezier curve, since high order B´ezier could be easily numerically unstable. For this reason, it is desirable to join low-degree B´ezier curves together in a smooth way, and the least degree of the B´ezier curve that can satisfy this requirement is three (Choi, Ji-wung and Curry, 2008Choi et al. (2008)), which is namely cubic B´ezier curve.
2.1.4 Global and Local Methods
Methodologies for path planning could be divided by the way of generating geometric path, but would also depends on the knowledge about the surrounding environment, thus global and local methods are defined.
Global planning often means that the information about the surrounding environment are all well known and could be utilized directly in planning process. Since it is aware of the whole map during finding the route, the final optimal decision is also determined at once and would not be changed ever since obtained. The goal could either be a fixed given tar- get or series of points with fixed sequence of going through, and the operating space might be assumed static or dynamic, global planner does not need any information from sensors or observations about current state of the vehicles, since everything has already been pre- stored in the memory. But the main drawbacks of global planner is thus caused by such big amount of calculation, compared with local planners, in particular. This would lead to a quite long computation time and heavy computational loads, the efficiency of reacting to the world outside is thus comparatively low, if dealing with a dynamic situation outside.
However, the result are more likely to be a feasible solution, and further to be the optimal one among all possible ones exist.
Local planners, on the other hand, is focusing more on partial place nearby, or only have limited knowledge towards the operating space. Under this circumstances, it could only choose to be sensitive to the changing outside by applying sensors or monitoring devices to collect real-time data. This makes it suitable in executing tasks in dynamic environment, as it emphasizes more on the reacting efficiency in this way, and would not have strict requirements towards the information processing speed. It works mainly dealing with the current state of the vehicle, finding a locally feasible or optimal solution, and proceeding to the next stage. It has no information about the place the sensor not covered, even the place it just went through since the environment is changing and no memory has left. By making progress step by step, it should finally be able to reach the end, but the success could never be guaranteed, and the solution it obtained is less likely to be the globally optimal one, although with much lower cost.
2.2 B´ezier Curve
2.2.1 Background
B´ezier curve is a mathematical parametric curve, which is often utilized in generating two dimensional parametric curve in the field of Computer Aided Design(CAD) and Com- puter Aided Manufacturing(CAM). It could draw precise and smooth line by using vector graphic software, and therefore is very common in the industrial application, especially in designing smooth and curved surface in three dimension. Line segments and control points are the main components of typical B´ezier curves, that coordinates of points could be assigned arbitrarily, and line segments are just like retractable rubber bands. B´ezier curve has been explored and implemented in many mature image processing software as curve drawing tool, and is of great importance and takes a significant place in Computer Graphics.
A pieccewise parametric curve constituted by B´ezier curve is used in this thesis, which is namely B´ezier spline. In the following section, some basic introduction about B´ezier curve including historical background, mathematical formulations, important function properties and applications would be presented.
2.2.2 History
B´ezier Curve
In industrial computer design, there is always a demand in how to represent and produce a smooth curve that must be agreeable to the observer aesthetically and not too mathe- matically. With the development of Computer Graphic, the technology of representation complex curvilinear has developed rapidly, and great progress in software that defining curved free surface has been made during 1950’s to 1960’s in the field of automobile and aircraft industries, by mechanical engineers. In solving this problem, French engineer Pierre B´ezier, working for a automobile company named Renault, has made a major and remarkable contribution.
At that time in 1950’s in industry, producing curves other than basic lines, circles and parabolas was inaccurate and low efficient. Although design engineers could produce great and satisfied drawings in drawing board, transferring it to digital graphics and guide the manufacture in factory were hard and would cause many additional problems like se- vere graph distortion. In a word, they were lacking of an efficient tool for transformation and communication between drawing and pattern manufacturing, not to mention complex surface shape was needed to be in three dimensional space. The development of hard- ware was fast which had already enabled computation and procession for complex sur- face, therefore all was ready except for this software. Pierre B´ezier, at this time, made an impressive progress in curvilinear parameterization. He successfully defined surface with polynomials to expressing spatial properties, which is now considered as the beginning of Computer Aided Geometric Design (CAGD). He represented a curve between two given points by formulations, introducing a new concept named ”control point”. Based on the
control points, the tangency and coordinates of the points on the curve could all be ex- pressed explicitly. Additionally, the shape of the curve could be change freely by moving the control point, while still keep smooth during the process.
Actually, the original polynomial which gives B´ezier’s work solid mathematical basis is Bernstein polynomials, which named after a Russian mathematician Sergei Natanovich Bernstein and became well-known to the world on 1912. Briefly explaining it, Bernstein polynomials could be utilized in proving that every continuous function on a certain in- terval[a, b]could be approximated by polynomials with strong convergence. In another words, that is for any continuous function, there would always exist an alternative expres- sion in the form of summation of several Bernstein polynomials which would converges to the original function along with the degreenapproaching infinity. However, the poor technology in constructing accurate polynomials and slow convergence rate at that time limited the development of Bernstein polynomials and made it to be used after publication for decades.
However, B´ezier’s work is not unique at that time, even not exactly the first that came up with. There was an another excellent automobile engineer working for Citro¨en just finished a similar work at almost the same time, but only published his result later than B´ezier. This engineer’s name is Paul De Casteljau, and his work was kept by his company Citro¨en as internal secret documents for a long time, named as De Casteljau Algorithm.
But B´ezier published his findings extensively and used it in aiding car body industrial de- sign which makes the curves so well-known, thus his name is linked directly to this kind of curve since than, and being used until nowadays.
De Casteljau Algorithm
Paul De Casteljau was a French physicist working for Citro¨en in Paris in 1958. In that same year he finished his work on developing the algorithm, a numerically stable method to deal with B´ezier curve, which made excellent progress in modeling car body surface. His first theoretical result had been sealed as soon as he complete that, later for decades the rest of the world kept knowing nothing about his impressive ideas. On De Casteljau’s mid-sixties, Pierre B´ezier published his own finding at Renault and on De Casteljau’s mid-seventies, his fundamental work was finally be able to became well-known by public. De Casteljau’s central idea was recognized as De Casteljau Algorithm and playing an important role ever since then. As a recursive analysis method, his algorithm is numerically stable in evaluat- ing Bernstein polynomials, as well as in splitting a single B´ezier into piecewise curve at an arbitrary parameter value. Even nowadays his algorithm remains a good tool, although slower than other direct method, but still more stable numerically.
2.2.3 General Formulations
For this section some basic formulations, properties and important math operation of B´ezier curve is presented, and the main reference for this, especially the mathematical part is from Sederberg (2012), Lande (2018) and Kamermans (2011).
Figure 2.3:Bezier Curves in Novin (2016)
As previously introduced above, an important composition of B´ezier curves is control points. Basically, B´ezier curves could be considered as interpolation functions, which means they take a set of control points and generate values between these points. This, in consequences, leads an significant properties that pretty useful, which is calledconvex hull property. It guarantees that no point generated by the control points would escape from the outline for the control points, which means all of them would stay in the small region space with certain boundaries. In fact, not every point are contributing to the curve uniformly: there always exists someone more important, and someone less, and the pa- rameter that evaluates this is conventionally called weight. To change the curve it is also never necessary to change the place of control points, changing the weight could also suf- fice instead. Assume the B´ezier curve is defined by a series of control pointsP0toPn, the general form of B´ezier curve function is:
pp($) =
n
X
i=0
Bin($)pi, $∈[0,1] (2.5)
where the variable$ represents time and the termBni($)is the Bernstein polynomials, defined as Lande (2018):
Bin= n
i
(1−$)n−i$i, i∈0,1, ..., n. (2.6) By adding weight term the B´ezier function is then straight forward as Kamermans (2011):
Bezier(n, t) =
n
X
i=0
n i
| {z }
binomial term
· (1−t)n−i·ti
| {z }
polynomial term
· wi
|{z}
weight
(2.7)
And the binomial term is defined as factorial:
n i
= n!
i! (n−i)! (2.8)
In fact, it is never complicated to decide what the weight value should be for B´ezier curves, because it is just the coordinates one places the control points. Like mentioned above, for a curve withnthorder, the control point isP0 toPn, which the first one is exactly the starting point, and the last one is the end point of the curve.
Example 2.2.1. Assume a cubic B´ezier curve which starts at (100,100), ends at (400,210) and is control by (200,200) and (300,110).
By applying the formula (2.7):
x= 100·(1−t)3+ 200·3·(1−t)2·t+ 300·3·(1−t)·t2+ 400·t3 y= 100·(1−t)3+ 200·3·(1−t)2·t+ 110·3·(1−t)·t2+ 210·t3 The x-coordinates and y-coordinates of all points could be obtained, which further gives the example curve shown in Figure 2.4:
Figure 2.4:Example B´ezier Curve
2.2.4 Matrix Form
B´ezier formula could also be represented in the matrix form, by expressing it as a polyno- mial and coefficent matrices. Assume a cubic B´ezier that:
B(t) =P1·(1−t)3+P2·3·(1−t)2·t+P3·3·(1−t)·t2+P4·t3 (2.9) First considering the part without control points coordinates, it can be expressed in the following form:
[t3 t2 t 1]·
−1 3
−3 1
+ [t3 t2 t 1]·
3
−6 3 0
+ [t3 t2 t 1]·
−3 3 0 0
+ [t3 t2 t 1]·
1 0 0 0
(2.10)
Furthermore, the complete matrix form for cubic B´ezier curve according to Kamermans (2011) would be:
B(t) = [1 t t2 t3]·
1 0 0 0
−3 3 0 0
3 −6 3 0
−1 3 −3 1
·
P1 P2 P3 P4
(2.11)
Similarly, quadratic B´ezier curve matrix form would be:
B(t) = [1t t2]·
1 0 0
−2 2 0
1 −2 1
·
P1
P2
P3
(2.12)
Matrix form representation is usually helpful in discovering properties that hard to find in polynomials, and sometimes the matrix approach can be quite fast.
2.2.5 De Casteljau’s algorithm
De Casteljau’s algorithm is pretty useful in splitting B´ezier curves into several segments, thus it is also named as subdivision algorithm. On the other hand, it also implies that if a complex shape of B´ezier curve is desired, de Casteljau’s algorithm could be utilized to connect sets of B´ezier curve together as one, since modeling complex shape by using single high order curve can be quite computationally expensive and numerically unstable.
This is accomplished by finding all the new control points needed by smaller segments:
pji = (1−τ)pj−1i +τpj−1i+1, j∈ {1, ..., n}, i∈ {0, ..., n−j}. (2.13) Based on this two new control points, new B´ezier curve can be presented by:
pp,1(t) =
n
X
i=0
Bin(t
τ)pji, t∈[0, τ], (2.14)
pp,2(t) =
n
X
i=0
Bin(t−τ
1−τ)p(in−j), t∈[τ,1]. (2.15) This subdivision algorithm is suitable for any degree of curves, especially useful when computing the coordinates and tangent vector of any points.
2.2.6 Lowering and elevating curve order
One interesting property of B´ezier curve is that, anynthdegree curve could be modeled perfectly by using an higher order curve, if giving it specific control points. Denoting as p∗i, the new control points can be obtained by (assuming that the start and the end points do not change):
p∗i =αipi−1+ (1−αi)pi, αi= i
n+ 1 (2.16)
By using it recursively, a B´ezier curve can be raised to any higher degree desired, or on the other hand, lower. If involving the concept of weight mentioned before, this function can be reformulated as:
Bezier(n+ 1, t) =
n+1
X
i=0
n+ 1 i
| {z }
binomial term
·(1−t)n+1−i·ti
| {z }
polynomial term
·((n+ 1−i)·wi+i·wi−1
n+ 1 )
| {z }
new weights
,
wherewi−1 = 0when i = 0. However this one is not as perfect as the former function (2.16), since it cannot generate safely back to lower degree curve fromnth ton−1th degree. There are possibilities that the resulting curve would not be exactly the same, even completely different if worse.
2.2.7 Derivatives
Another interesting observation for B´ezier curve is that, their derivatives are also B´ezier curves, which is one degree lower. The differentiation of a B´ezier curve is kind of straight forward, based on the general formulas (2.6), it can be written as:
Bin0($) =n(Bi−1n−1($)−Bin−1($)). (2.17) Then the derivative becomes:
p0($) =n
n−1
X
i=0
Bn−1i ($)(pi+1−pi), $∈[0,1]. (2.18) Thus it is possible to define thek−thderivative of any B´ezier by using the similar ap- proach. Same for the formula (2.7), to express the derivative including the term weight, it could be reformulated as:
Bezier0(n, t) =
n−1
X
i=0
Bezier(n−1, t)i·n·(wi+1−wi) (2.19)
2.3 Trajectory optimization
Path planning algorithm, as discussed before, is mainly about to lead one or more feasi- ble path from initial to the final position or pose, and therefore is somewhat a geometric problem. Compared with this, for problems which need to take the time change into con- sideration, an extra parametertis required to be augmented in planner, and this kind of problem is named trajectory planning accordingly. Trajectory planning and optimization is the main concern for this thesis, since to achieve time deconfliction the assignment of speed is a vital part and time augment is taken as optimization variable.
Trajectory optimization problem is the crucial problem for the trajectory planning al- gorithm to achieve some certain objectives while satisfying constrains to stay feasible.
Usually these objectives are related to some measurement of performance, for example minimizing total length of path, operation time or energy. It takes the form of general opti- mization control problem framework according to Roald (2015), and could be commonly formulated as following:
M inimize J[x(·),u(·), tf] =E(x(tf), tf) + Z tf
t0
F(x(t),u(t), t)dt Subject to:
˙
x=f(x,u, t)
gi(x,u, t)≤0, i= 1, ..., m hi(x,u, t) = 0, i= 1, ..., m
(2.20)
HereJ[x(·),u(·), tf]is the objective function to be minimized,x˙ is equations of the sys- tem, gi(x,u, t)represents the inequality constraint for the system andhi(x,u, t) = 0 represents the equality constraints.
For a constrained nonlinear quadratic programming problem in this thesis, according to Nocedal and Wright (2006), there are categorized optimization algorithm can be used to solve problems. For example Sequential Quadratic Programming(SQP) methods and certain interior-point methods for nonlinear programming. The general principle for se- quential quadratic programming is to model a quadratic programming subproblem at each iterate subject to a linearization of constraints. If the problem is unconstrained it would reduce to Newton’s method and find a search direction for this subproblem where the gra- dient of the objective vanishes. If the problem is only linear constrained, then it becomes equivalent to apply Newton’s method to the first order optimality conditions. SQP algo- rithm is also utilized in this thesis to solve optimization problem, and would be presented again in later chapter. For interior-point method, it can be considered as extension of the primal-dual interiot-point methods for linear programming.
Also, if combining the objective function and constraint into a penalty function, the con- strained problem can be reformulated as unconstrained problems. The penalty function
can be defined like following:
f(x) +µ 2
X
i∈E
c2i(x), (2.21)
Minimizing this unconstrained function for a series value of µ, whereµ > 0 is called penalty parameter, and the accuracy of the solution is rapidly growing sufficient. This al- gorithm is called penalty and augmented Lagrangian methods.
Actually, although there are lots of optimization techniques besides introduced above available to solve optimizations, none of them could guarantee that problem could finally be solved analytically optimal. Sometimes it can be really difficult in computation for an analytical optimal solution and most of the time the solution found are solved by numerical approximation and try to stay close to optimal one. And how close it is to optimal solution depends on the transformations and approximations being used.
2.4 Vehicle Modeling
This section would introduce some fundamentals in vehicle modeling, mainly about a surface vessel in two-dimensional space, including kinematics and kinetics aspects.
2.4.1 Kinematics
Kinematics only includes description of the position, velocity and acceleration of the ob- ject, while kinetics mainly analysis forces or moments causing the motion.
Reference frames
In kinematic problems there is a basic aspect needed to be demonstrated clearly at the very beginning, the reference frame. There are usually two kinds of frames: global ref- erence frame and local reference frames. Global one is based on the Earth and place its origin on the center of Earth. It is used more in globally navigation such as Earth-centered Earth fixed (ECEF) reference frames, and Earth centered inertial reference frame. The local reference frame is generally placing the origin on some stationary point on vehicle itself. Each category contains several different reference frames, and in this thesis only two kinds of local reference would be used. Short introduction and definition basing on Fossen (2011) about these two frames is given.
NEDframe is the abbreviation of North-East-Down coordination system{n}= (xn, yn, zn), with originonbeing defined in Earth’s reference ellipsoid. It is also a system that we use everyday in our daily life. Basically it is defined on the tangent plane on the Earth surface, with axis pointing differently than body-fixed axis of the vehicle. In this system, as its name indicates, thexaxis is pointing towards the geographical North, theyaxis is point- ing towards geographical East, and thezaxis points directly down, normal to the Earth’s surface. Bodyfixed frame is a moving coordinate frame with reference to the Earth. Its origin is fixed on the vehicle itself with{b}= (xb, yb, zb), and the position and orientation of the vehicle are represented relative to the inertial reference frame, while the linear and angular velocities of the craft is described in the body fixed coordinate system. The origin obis often chosen as a point mid ship in the water line and would be referred asCO. For marine crafts, the three axes xb,yb andzb are usually defined as below, like Figure 2.5 indicated:
• xb- longitudinal axis (directed from aft to fore);
• yb- transversal axis (directed to starboard);
• zb- normal axis (directed from top to bottom)
2.4.2 Variable Notations
For marine crafts moving in six degree of freedoms(DOFs), in order to describe the po- sition and orientation of the craft, six following independent coordinates are often used.
The first three coordinates represent for the position along x,y, andz axes, while their
Figure 2.5:Body-fixed reference for marine craft from Fossen (2011)
derivatives of time correspond to accelerations. The last three coordinates and their time derivatives describe orientation and rotational motion. These six important motion is de- fined as surge, sway, heave, roll, pitch and yaw (see Table 2.1). The linear and angular velocity is defined in the BODY frame, and the position and Euler angles is given in NED frame.
Table 2.1:The notation of SNAME (1950) for marine vessels
Forces Linear and Position and angular and Euler
DOF moments velocities angles
1 motions in thexdirection(surge) X u x
2 motions in theydirection(sway) Y v y
3 motions in thezdirection(heave) Z w z
4 rotation about thexaxis (roll, heel) K p φ
5 rotation about theyaxis (pitch, trim) M q θ
6 rotation about thezaxis (yaw) N r ψ
2.4.3 Transformation between BODY and NED
The transformation work between two frames can be done through rotation matrix R, which is usually denoted asRab, representing transforming from coordinateatob, and it is useful when performing the kinematic equation calculations of the motion. Usually it can be denoted as given below when transforming a vector from one frame to another:
νto=Rtofromνfrom (2.22)
And the rotation matrixRnb is a frequently used rotation matrix in guidance, navigation and control. To deriving the expression ofRnb, first describing the horizontal motion by generalized position and velocity in reduced vectors, η = [x, y, ψ]T andν = [u, v, r]T. The heave, pitch and roll motion in this stage is currently neglected, and rotational motion
is only left with rotating about thezaxis. Kinematic equation is thus can be formulated as:
˙
η=R(ψ)v (2.23)
And the rotational matrixRnb(ψ)indicating the coordinate transformation from{b}to{n}
is derived as below:
Rnb(ψ) =
cos(ψ) −sin(ψ) 0 sin(ψ) cos(ψ) 0
0 0 1
(2.24)
Chapter 3
Multiple Path Planning and Deconfliction
Multiple path planning is an important aspect for multiple vehicle motion control basing on the single path planning, and the key problem for this work is to well organize multiple paths and ensure every vehicle’s operation could reach the goal. In this section, some im- portant concepts and categories of algorithm that commonly used in multiple path planning are introduced, along with some related work from reference literature.
3.1 Multiple path planning algorithm
Consider an important example that usually happens in marine vehicle maneuvering ap- plications: Several autonomous vehicles are launched at one place or scattered at more different positions at the same time, and expected to cooperate and execute a mission to- gether, maneuvering from initial place to prescribed target neighborhood respectively at a same time. Then the further mission like underwater detection or exploration can be performed. Since they might be operating in a restricted area and finally come quite close to each other, this mission probably takes the risk of colliding with support ships, static or moving obstacles (like floating buoy, coastline) or other vehicles, and thus for multiple vehicle path planners, deconfliction task is the main challenge that must be solved to guar- antee the operation safety. It is particularly crucial in multiple vehicle control, requiring the algorithm to not only generate a feasible path leading to the goal point, but also never allow any other objects to come to close vicinity of each other in space. This property is the main focus of the conceptdeconfliction. Furthermore, vehicles might be required to arrive at approximately same time and speed, and this problem can be detailed with more constraints, like dynamic limitations of vehicle velocity and accelerations, total energy restrictions for the whole maneuvering process, and environmental constraints including external disturbances, caused by ocean currents and sea waves. Solving this kind of task in path planning problem also can yield a number of objectives to be optimized in the pro-
cess, such as proposing an energy-related cost function, or minimizing executing time or path length.
Figure 3.1:Multiple path planning system from H¨ausler et al. (2009)
In this section, two kinds of algorithms about multiple vehicle path deconfliction will be introduced, which are based on time and space assignment respectively. In order to differ- entiate vehicles, letV := {Vi; i = 1, ..., n}denotes the set of vehicles involved, where n≥2. A general framework of multiple path planning system is constructed according to H¨ausler et al. (2009), as illustrated in Figure 3.1 above.
3.2 Temporal deconfliction
Recalling the difference in the concept of path and trajectory, spatial deconfliction would not require an extra degree of freedom - time, and thus could still remain in the field of path planning, if further constraints regarding time and speed are not required. Basically, the main difference between these two algorithm is, temporal deconfliction allows for each vehicle to plan path separately, taking only obstacles and constraints into consideration and its route can intersect with others in some places. The main point is assigning proper speed to stagger the time for different vehicles to pass the same point, and guarantee that at no time they come close to the vicinity of each other.
In comparison, for spatial deconfliction, time coordinate is not a main concern in plan- ning and is usually being considered in further constraints regarding arriving speed or later stage like path following. The major focus is therefore to take each vehicle’s running route into account together at the same time, and restrict the closest distance between them to be larger than a prescribed minimum safety distance, sayE. The intersection interval or crossing point would at no time appear spatially in this situation, like illustrated in Fig- ure 3.3. Consequently, time deconfliction algorithm is capable of providing solutions of a larger class of problems than spatial deconfliction algorithms can deal with, due to the augment of time coordinate as an extra freedom. In spatial deconfliction, time coordinate is not a necessary part to be included. However what in common is, spatial coordinates and time parameter are both decoupled and dealt with at different stage in this two algorithms, which gives more potential in further improving and allowing more versatility.
Addressing the problem of temporal deconfliction, since it allows the path to come to close vicinity and intersect spatially, the path planning for different vehicles can be dealt with separately, to its assigned target which can be formulated respectively. The most cru- cial part, in achieving the objective is the speed assignment optimization, which staggers the time in crossing the intersection point and ensures a collision free operation in multiple vehicle motion control. As a result of this, intersection points and its vicinity where col- lision might possibly happen should be detected and marked after finishing path planning process, like the area indicated by a red circle in Figure 3.2. It is the place which would be referred as danger zone in later chapter, and needed to be treated carefully for this prob- lem.
Actually for temporal deconfliction path planning problems, it seems if once the path and velocity has been assigned, it is strictly required that the vehicle should follow the path pre- cisely as planned. This sets a high standard for trajectory tracking execution, and would no doubt meet with considerable problems. In this way, synchronized arriving would also be a tough manner. In fact, this is the main drawback for the time deconflicted path plan- ning, and in real applications, deviation spatially and temporally could always appear due to environment disturbance or mechanical failures. Thus the use of absolute time, which on-board systems on the vehicle are using, is not practical and necessary to be avoided.
Also, it is vital to propose an efficient path following control, replanning from the current position as reaction to the deviation from original plan and controlling the vehicle try to maintain the path. This kind of problem is called Time Coordinated Path Following(TC-
Figure 3.2:Temporal deconfliction for multiple path planning
PF) and is significant in the later stage for temporal deconfliction path planning. Method- ologies relating to this can be referred to Ghabcheloo et al. (2009a), and some relevant introductions would be presented in later chapter as literature survey for related work.
3.3 Spatial deconfliction
Spatial planners focus on the path planning in the operation space, and with no present of time coordinate during the planning process. It requires that each vehicle should follow a feasible route to the target while always keep a minimum prescribed safety distanceEwith other vehicle, in other words, their route at no where would intersect with each other. This could be quite demanding under some certain situations, especially when there are many objects existing around and the operation space is relatively limited. It takes other vehicles as moving obstacles and avoids to pass all the places others will or already passed, and this obviously narrows the set of the feasible solutions, thus the set of problems it could tackle with is of smaller size compared with time deconfliction. But the main superiority it may have over temporal deconfliciton is that, it does not need to worry about the high precision path following problem, both in space and time.
Generally, for an open and wide space it would be easier to choose spatial deconfliction algorithm obtaining a feasible path with collision avoidance, and reduce the computation loads both in planning and replanning. If extra constraints are required in motion speed or arriving time, time coordinate could be further involved, otherwise time could never be necessarily considered in this situation.
Figure 3.3:Spatial deconfliction for multiple path planning in H¨ausler et al. (2009)
In this case, the general form of optimization problem could be used as following, which
would be presented with more detailed method in H¨ausler et al. (2009):
M inimize
n
X
i=1
wiJi
Subject to geometric conditions or dynamic constraints f or any i ∈ [1, n],
M inimize||pj−pk||2 ≥ E2 f or any j, k= 1, ..., n, j6=k.
(3.1)
Spatial deconfliction here in this thesis would only be presented as alternative methods regarding deconfliction task, and only discussed with basic formulation as additional in- formation. In this thesis, temporal deconfliction is the main task and concern.
3.4 Related work
Multiple path planning problem is a crucial topic for automation and has been studied by researchers in various fields during the past ten years. For this topic many different approaches have been already proposed. Some algorithms stem from the robotics field and computer science, some mainly focus on the marine vehicle and being used in marine control systems and vessel maneuvering.
3.4.1 Path generation algorithm
For path generating algorithms, Lande (2018) takes the advantages of B´ezier curve to generate a smooth curve which leads a feasible path starting from the initial point to the goal point, and avoiding all the random generated static obstacles within a bounded 2D space. He limits the curve shape by utilizing characteristics like convex hull property, to ensure that the curve would never exceed the boundary and cross the section where static obstacles lie in. And further, he uses B´ezier derivatives to add constraints on the curvature, and guarantee the path that is smooth and continuous in bothC2andG2. To formulate the objective function he utilizes differential flatness to assign cost, minimizing the energy associated with the path and taking the vehicle dynamic into consideration. Then he takes control points as optimization variables to solve this nonlinear constraint problem and obtain the optimal control points as solution. His work presents the efficiency and potential for B´ezier curves to generate feasible path, capable of avoiding large number of obstacles while stay continuous and curvature constrained.
3.4.2 Multiple path planning
Recalling the concept configuration space introduced in Chapter 2, basing on this some path planning algorithms have developed different approaches in multiple vehicle path planning, such as coordinated path planning for multiple robots proposed by Svestka and Overmars (1996). They utilized a series of identical simple robots and composite them to- gether as one robot with many degree of freedom, and this robot is the so-called composite robot. The path feasible for the composite robot with mutual collision avoided is referred to as coordinated path. By first constructing a simple roadmap for single robot,nof such roadmaps are combined into a roadmap as a super-graph. Then they adopt two structure of super-graph for retrieval of coordinated paths. By doing this rather than adopting usual decoupled planning, they achieve a centralized approach which allows for complete plan- ners that could always find a solution as long as it exists. Further they prove that their proper construction of the simple roadmaps guarantees probabilistic completeness of the resulting planners.
Specifically for multiple marine vehicles path planning, in Hausler et al. (2009), they uti- lized direct optimization methods in path generation, parameterize the path and use an algebraic polynomials inN degree to represent the coordinates of each point on the path.
The degreeN is determined by the number of boundary conditions, and the value ofN could be set a bit larger to allow for additional degree of freedom. However, the main focus and contribution of this paper is the deconfliction work for multiple vehicle path
