Access the full text.

Sign up today, get DeepDyve free for 14 days.

Electrical Engineering and Systems Science
, Volume 2019 (1907) – Jul 10, 2019

/lp/arxiv-cornell-university/short-term-asv-collision-avoidance-with-static-and-moving-obstacles-MJbmBEenAu

- ISSN
- 0332-7353
- eISSN
- ARCH-3348
- DOI
- 10.4173/mic.2019.3.4
- Publisher site
- See Article on Publisher Site

Short-term ASV Collision Avoidance with Static and Moving Obstacles Bjørn-Olav H. Eriksen and Morten Breivik Centre for Autonomous Marine Operations and Systems, Department of Engineering Cybernetics, Norwegian University of Science and Technology (NTNU), NO-7491 Trondheim, Norway. E-mail: {bjorn-olav.h.eriksen, morten.breivik}@ieee.org July 12, 2019 Abstract 1 Introduction All parts of society are currently being automated at a rapid pace. One example is the development of autonomous This article considers collision avoidance (COLAV) for cars, as exempliﬁed by the development eﬀorts made by both static and moving obstacles using the branching- e.g. Tesla, Google and Uber. Such a trend is also ongoing course model predictive control (BC-MPC) algorithm, in the maritime domain, where autonomous technology which is designed for use by autonomous surface vehicles presents opportunities for increased cost eﬃciency, in ad- (ASVs). The BC-MPC algorithm originally only consid- dition to reducing the environmental impact of goods and ered COLAV of moving obstacles, so in order to make passenger transport. One example of this is the Yara Birke- the algorithm also be able to avoid static obstacles, we land project in Norway, where an electrically-powered au- introduce an extra term in the objective function based tonomous cargo ship will replace 40000 diesel-powered on an occupancy grid. In addition, other improvements truckloads of fertilizer each year by 2022 (Paris, 2017). are made to the algorithm resulting in trajectories with less Furthermore, it is reported that in excess of 75% of mar- wobbling. The modiﬁed algorithm is veriﬁed through full- itime accidents are caused by human errors (Chauvin, scale experiments in the Trondheimsfjord in Norway with 2011; Levander, 2017), which also reveals a potential for both virtual static obstacles and a physical moving obsta- increased safety by introducing autonomous technology at cle. A radar-based tracking system is used to detect and sea. Employing ASVs in areas where other vessels are track the moving obstacle, which enables the algorithm present does, however, require a robust COLAV system in to avoid obstacles without depending on vessel-to-vessel order to avoid collisions and operate safely. communication. The experiments show that the algorithm There exists several algorithms for ASV COLAV, e.g. is able to simultaneously avoid both static and moving the velocity obstacle (VO) algorithm (Kuwata et al., 2014), obstacles, while providing clear and readily observable the A* algorithm (Schuster et al., 2014) and algorithms maneuvers. The BC-MPC algorithm is compliant with based on model predictive control (MPC) and optimiza- rules 8, 13 and 17 of the the International Regulations tion (Benjamin et al., 2006; Švec et al., 2013; Abdelaal for Preventing Collisions at Sea (COLREGs), and favors and Hahn, 2016; Hagen et al., 2018). These algorithms maneuvers following rules 14 and 15. are, however, designed with the idea of “one size ﬁts all”, Keywords: Autonomous surface vehicles, collision where the same algorithm is used to solve both situations avoidance, model predictive control requiring proactive and reactive behaviors. A challenge arXiv:1907.04877v1 [eess.SY] 10 Jul 2019 Lameijer, 2004). The short-term COLAV algorithm in- puts the modiﬁed trajectory from the mid-level algorithm, and should have low computational requirements ensur- ing that the COLAV system can react to sudden changes in the environment. This algorithm should also serve as a ﬁnal safety barrier in situations where e.g. the mid-level algorithm fails to ﬁnd a solution (Eriksen and Breivik, 2017b). In addition, the short-term algorithm should have a shorter planning horizon than the mid-level algorithm, making it inherently capable of handling situations where the COLREGs may require ignoring the maneuvering as- pects of rules 14 and 15 when moving obstacles do not comply with the COLREGs. The algorithm should, how- ever, maneuver in accordance with rules 14 and 15 when the situation allows it. The authors have performed a signiﬁcant amount of work on the hybrid architecture in Figure 1, concerning e.g. model-based vessel controllers (Eriksen and Breivik, Figure 1: A hybrid architecture with three layers. The 2017a, 2018), short-term COLAV (Eriksen et al., 2018, support functions provide relevant information for the 2019b), mid-level COLAV (Eriksen and Breivik, 2017b) COLAV algorithms, including prediction of obstacle tra- and a high-level planner interfaced to the mid-level algo- jectories, static obstacles from electronic nautical charts rithm (Bitar et al., 2019). In an upcoming article (Erik- (ENC) and situational awareness in the form of COLREGs sen et al., 2019a), we populate the hybrid architecture situations. with algorithms including the BC-MPC algorithm dis- cussed in this article, and demonstrate COLAV compliant with COLREGs rules 8 and 13–17 in simulations. Work with this approach is that the algorithm must be able to has also been performed on obstacle trajectory prediction solve problems of a wide range suﬃciently well, which (Hexeberg et al., 2017; Dalsnes et al., 2018). For the short- makes the algorithm diﬃcult to design and tune. A diﬀer- term COLAV layer, we initially focused on the dynamic ent approach is to utilize a hybrid architecture (Loe, 2008; window (DW) algorithm, using a radar-based tracking sys- Casalino et al., 2009), where the complementary strengths tem for detecting and tracking obstacles (Wilthil et al., of diﬀerent algorithms can be combined in a layered archi- 2017). The reason for using exteroceptive sensors such as tecture. An example of a hybrid architecture is shown in radars for detecting obstacles is that they do not depend Figure 1, where the COLAV system is divided into three on vessel-to-vessel communication or collaboration with layers, namely a high-level, mid-level and a short-term other vessels, hence enabling avoidance of vessels which COLAV algorithm. The high-level planner performs long- do not have or use automatic identiﬁcation system (AIS) term planning by ﬁnding a path or trajectory from an initial transponders. Another questionable aspect of AIS is that position to a goal position while being able to avoid static other vessels may provide incorrect information (Harati- obstacles, satisfy time constraints and minimize energy Mokhtari et al., 2007), which can be diﬃcult to detect and consumption. The mid-level algorithm attempts to follow handle. However, there is a fair amount of noise on obsta- the planned path or trajectory from the high-level planner, cle estimates originating from systems using exteroceptive while making local modiﬁcations in order to avoid moving sensors, which the DW algorithm was shown not to handle obstacles. This algorithm should be designed to comply suﬃciently well in full-scale experiments (Eriksen et al., with the maneuvering rules of the COLREGs, which dic- 2018). We therefore developed the BC-MPC algorithm for tates how vessels should behave in situations where there short-term COLAV (Eriksen et al., 2019b), which is based exists a risk of collision with other vessels (Cockcroft and on MPC and designed to be robust to obstacle estimate 2 noise. This algorithm is shown to have good performance each contains a sequence of maneuvers. Given this search in full-scale experiments, but originally only accounts for space, an objective function is computed on the trajecto- moving obstacles. ries, and the optimized trajectory is selected and used as In this article, we further develop the BC-MPC algo- the reference to the vessel controllers which control the rithm to also handle avoidance of static obstacles in addi- speed over ground (SOG) and course. The algorithm is tion to moving obstacles, as well as producing trajectories based on MPC, hence only the ﬁrst part of the optimized with less wobbling. The modiﬁed algorithm is veriﬁed trajectory is used before a new solution is computed and in full-scale experiments in Trondheimsfjorden, Norway, implemented. showing good performance. The experiments are per- This section presents an overview of the BC-MPC al- formed with virtual static obstacles, while a moving ob- gorithm. Interested readers are referred to Eriksen et al. stacle is detected and tracked using a radar, not depending (2019b) for more details on the algorithm. In addition, this on vessel-to-vessel communication. section presents modiﬁcations enabling the algorithm to The rest of this article is organized as follows: Section 2 perform static obstacle avoidance and produce trajectories presents the BC-MPC algorithm and the modiﬁcations we with less wobbling than the original algorithm. do to it, Section 3 presents the experimental setup and results, while Section 4 concludes the article and points to 2.1 Trajectory generation possibilities for further work. At each iteration, a new ﬁnite search space of possible tra- jectories is generated. Every trajectory contains a number 2 The BC-MPC algorithm of sub-trajectories, each containing one maneuver. This naturally forms a tree structure, with the nodes represent- The BC-MPC algorithm (Eriksen et al., 2019b) is a ing vessel conﬁgurations and edges representing maneu- COLAV algorithm designed using sample-based MPC, vers. The initial condition is used as the root node, and intended for short-term COLAV for ASVs. Sample-based the depth of the tree is equal to the number of maneuvers MPC algorithms are based on computing an objective in each trajectory. function over a ﬁnite discrete search space and select- The trajectory generation is performed by a repeatable ing the optimized solution, rather than utilizing search maneuver-generation procedure, which when given a ves- algorithms as in gradient-based algorithms. A beneﬁt of sel conﬁguration computes a set of sub-trajectories each sample-based algorithms is that they do not have problems containing one maneuver. Piecewise linear acceleration with solving highly nonlinear and non-convex problems, proﬁles in speed and course serve as a template for the which in general is diﬃcult for gradient-based algorithms. maneuvers. An example of 5 motion primitives based This makes sample-based algorithms well suited for use on the acceleration proﬁles in speed and course is shown in the short-term layer in Figure 1. Furthermore, the in Figure 2. The acceleration proﬁles are dependent on BC-MPC algorithm is designed to be robust with respect the step time length (the maneuver time length) T > 0, to noisy obstacle estimates, which is a signiﬁcant source of disturbance when using exteroceptive sensors such as the ramp time T 2 ¹0; min¹ ; º¼ and the speed and ramp 2 4 radars for detecting and tracking obstacles. course maneuver lengths, T ; T 2 ¹0; T¼, respectively. With respect to the COLREGs, the BC-MPC algorithm Given a current vessel velocity, the maximum and mini- Û Û mum speed and course accelerations U ; U ; rÛ and complies with rules 8, 13 and 17, and favors maneuvers max min max rÛ are computed using a vessel model. following rules 14 and 15. In cases where the algorithm min chooses to ignore the maneuvering aspects of rules 14 and To improve the convergence properties of the algorithm, 15, which can be required when rule 17 revokes a stand-on we employ a guidance function which can modify some of obligation, the maneuvers have an extended clearance to the trajectories in the search space. This is done by moving obstacles. the closest acceleration sample in speed and course to a At each iteration, the algorithm computes a search space desired acceleration generated by the guidance function, consisting of a ﬁnite number of possible trajectories, which if this is inside the feasible acceleration region. 3 _ U 1 U 0 max −1 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Time [s] T T T T T ramp U ramp U U 6 min 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Time [s] (a) Speed acceleration motion primitives r_ Figure 3: Example of 5 speed trajectories with ramp time r_ max T = 1 s, and maneuver and step time lengths T = T = ramp U 5 s. Acceleration is shown in the top plot, while speed is shown in the bottom plot. T 2T T 2T T T T T ramp ramp ramp ramp the trajectory generation, we use an error model of the r_min vessel to generate feedback-corrected speed and course trajectories U ¹tº and ¯ ¹tº, which similarly as in (1) is d d combined in a set U . The feedback-corrected speed and (b) Course acceleration motion primitives. course trajectories are used to generate feedback-corrected Figure 2: Acceleration motion primitives, where T is the predicted pose trajectories: step time, T denotes the ramp time, while T and T ramp U ¯ ¯ ¯ H = ¯¹t; U¹tº; ¯¹tºº¹U¹tº; ¯¹tºº 2 U ; (2) are the SOG and course maneuver time lengths, respec- Û Û tively. The symbols U ; U ; rÛ and rÛ denote the max min max min where ¯¹t; U¹tº; ¯¹tºº denotes a kinematic simulation pro- acceleration limits of the vessel at the initial vessel state. cedure to obtain the vessel pose. A full trajectory search space is created by ﬁrst gen- Desired speed and course trajectories U ¹tº and ¹tº d d erating a set of sub-trajectories by using the maneuver- are generated by analytically integrating the acceleration generation procedure initialized with the initial vehicle motion primitives. Numerical examples of 5 speed and 5 pose. At this stage, the prediction tree has a depth of course trajectories are shown in ﬁgures 3 and 4. It should one with the initial vessel pose as the root node and a set be noted that these trajectories are intended as reference of leaf nodes each reached by one maneuver. Following trajectories for the vessel controllers, hence they are ini- this, we append the trajectories with another maneuver by tiated in an open-loop fashion with the current desired repeating the maneuver-generation procedure, initialized speed and course in order to ensure continuous references on each of the leaf nodes, which increases the depth of for the vessel controllers. The desired speed and course the trajectory prediction tree with one level. This is re- trajectories are joined together in a union set of desired peated until the trajectory prediction tree has the desired velocity trajectories: depth, i.e. each trajectory has the desired number of ma- neuvers. This concept is illustrated in Figure 5. The U = fU ¹tº; U ¹tº; : : :; U ¹tºg acceleration proﬁle parameters and number of speed and d d;1 d;2 d;N course motion primitives can be level-dependent, which f ¹tº; ¹tº; : : :; ¹tºg; (1) d;1 d;2 d;N allows for shaping the maneuvers diﬀerently and avoiding resulting in a total of N N desired velocity trajectories exponential growth with the number of levels. To reduce + + where N 2 Z and N 2 Z are the number of speed the complexity in tuning the algorithm, we use the same and course motion primitives. To include feedback in ramp time T and speed and course maneuver lengths ramp Speed [m/s] Acceleration [m/s ] 20 Level 0 −20 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Level 1 Time [s] Level 2 −20 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Figure 5: Illustration of a trajectory prediction tree with Time [s] two levels. The red node is the root node containing the initial vessel conﬁguration. Other colors group nodes and edges associated with each maneuver-generation proce- −50 dure, which generate three maneuvers each time (given by 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 combinations of N and N satisfying N N = 3). The Time [s] U U tree contains a total of nine trajectories, each consisting of two sub-trajectories. Figure 4: Example of 5 course trajectories with ramp time T = 1 s, and maneuver and step time lengths ramp T = T = 5 s. Acceleration is shown in the top plot, rate The objective function is given as: in the middle plot and course in the bottom plot. G¹ ¯¹tº; u ¹tº; p ¹tºº = w align¹ ¯¹tº; p ¹tºº d al d d + w avoid ¹ ¯¹tºº + w avoid ¹ ¯¹tºº T and T throughout each level. For a desired trajec- av,m m av,s s tory tree depth B (B maneuvers in each trajectory), this + w tran ¹u ¹tºº + w tran ¹u ¹tºº; (4) t;U U d t; d leaves us with deciding the step time lengths of each level T = »T ; T ; : : :; T ¼, and the number of speed and course where w ; w ; w ; w ; w > 0 are tuning parame- 1 2 B al av,m av,s t;U t; maneuvers at each level N = »N ; N ; : : :; N ¼ and ters. U U;1 U;2 U;B N = »N ; N ; : : :; N ¼. The align¹º function assigns a value to following the ;1 ;2 ;B desired trajectory p ¹tº. The avoid ¹º function assigns A set of feedback-corrected predicted pose trajectories d m a cost to traveling close to moving obstacles, which de- for a trajectory generation with B = 3 levels is shown in pends on the distance to an obstacle for each point on Figure 6. The ramp time is T = 1 s, and the speed and ramp the predicted trajectories. The maneuvering rules in the course maneuver lengths are T = T = 5 s. The step time COLREGs, rules 13–15, require the vessel to maneuver lengths are T = »20; 30; 30¼ s, and the number of speed and to starboard in head-on situations, and recommend to pass course maneuvers are N = »1; 1; 1¼ and N = »5; 3; 3¼. behind an obstacle if the obstacle approaches from the starboard side. To motivate the algorithm to follow these rules, while being free to ignore the speciﬁc maneuver- 2.2 Selecting the optimized trajectory ing aspects if required in situations where the other vessel violates the COLREGs, we use the obstacle regions in Given a search space of vessel trajectories and a desired Figure 7 when calculating this cost. The regions can be trajectory p ¹tº 2 R , we solve an optimization problem d interpreted as follows: the margin region is allowable to to ﬁnd the optimized desired velocity trajectory u ¹tº = enter, the safety region is not desirable to enter, while the U ¹tº ¹tº collision region should not be entered. Notice that the al- as: d d gorithm will require a larger clearance in situations where the maneuvering rules in the COLREGs are ignored, e.g. u ¹tº = argmin G¹ ¯ ¹tº; u ¹tº; p ¹tºº: (3) d;k d k ¯ if maneuvering to port in a head-on situation. See Eriksen ¹ ¯ ¹tº;u ¹tºº2¹H;U º d;k d ◦ ◦ ◦ 2 Course [ ] Rate [ /s] Acceleration [ /s ] 400 Ownship Collision Safety Margin region region region −400 −300 −200 −100 0 100 200 300 400 East [m] Figure 6: A set of predicted pose trajectories with three levels. Notice how the guidance function shifts some of the c maneuvers, marked in dark green, to converge towards the desired trajectory, which is a straight-north trajectory from the initial pose (not shown in the ﬁgure). For illustration Figure 7: Avoidance cost regions centered at the mov- purposes, the trajectories only contain course maneuvers. ing obstacle, each constructed by one circular and three elliptical segments. The green, yellow and red regions are named the margin, safety and collision regions, re- et al. (2019b) for more details on the align¹º and avoid ¹º spectively. The avoidance cost increases linearly with terms. diﬀerent gradients inside the green and yellow regions, In this article, we introduce the avoid ¹º, tran ¹º and s U while the cost is constant inside the red region. The vari- tran ¹º terms. The avoid ¹º term assigns a cost to avoid- ables a ; b and c , i 2 f1; 2; 3g denote the region sizes, i i i ing static obstacles, while tran ¹º and tran ¹º are transi- where c = b + d with d controlling the i i COLREGs COLREGs tional cost terms increasing the robustness to noise. These COLREGs expansion. terms will be discussed in detail in the following two sec- tions. 2.4 Speed and course transitional costs 2.3 Static obstacle avoidance In order to improve the robustness to noise on obstacle estimates, transitional cost is included in the objective Static obstacles are modeled using an occupancy grid, function, which penalizes changing the planned trajectory which allows for easy representation of obstacles with ar- from iteration to iteration. In Eriksen et al. (2019b), a bitrary shapes like e.g. land and islands. In addition, single transitional cost term is used, which introduces a static obstacles are padded with a decaying gradient to in- cost if one selects a diﬀerent speed and/or course than the troduce some smoothness to the static obstacle avoidance one closest to the one selected in the previous iteration. function. Given an occupancy grid O¹pº 2 »0; 100¼ where Note that the trajectory prediction is based on sampling O¹pº = 100 and O¹pº = 0 represents an occupied and the possible acceleration of the vessel in the current iter- empty cell, respectively, we deﬁne the static obstacle term ation, which implies that the exact trajectory selected in as: t +T 0 the previous iteration may not exist in the current search avoid ¹ ¯¹tºº = O¹p ¯¹ ººd ; (5) space. Here, it is proposed to split the transitional cost term where t denotes the initial time and ¯¹tº = into separate speed and course terms. This motivates the p ¯¹tº ¹tº . algorithm to not alter the course if the speed is changed North [m] and vice versa, which would not be the case when using a single transitional cost term. The transitional cost terms are deﬁned as: t +T 0 1 1; U ¹ º U ¹ º d > e d U;min tran ¹u ¹tºº = U d 0; else; (6) t +T 0 1 1; ¹ º ¹ º d > e d ;min tran ¹u ¹tºº = 0; else; (7) with u ¹tº = U ¹tº ¹tº . The variables U ¹tº and d d d ¹tº denote the current desired velocity trajectory tracked d Figure 8: The Telemetron ASV, owned and operated by by the vessel controllers, and T is the step time of the ﬁrst Maritime Robotics. Courtesy of Maritime Robotics. trajectory maneuver. The variables e and e de- U;min ;min note the minimum diﬀerence between the current desired velocity trajectory and the candidates: t +T 0 1 e = min U ¹ º U ¹ º d U;min d u ¹tº2U d d (8) t +T 0 1 e = min ¹ º ¹ º d : ;min d u ¹tº2U d d t 3 Experimental results The modiﬁed BC-MPC algorithm was tested in full-scale th experiments in the Trondheimsfjord in Norway on the 27 Figure 9: The Kongsberg Seatex Ocean Space Drone 2, of September 2018. This section describes the experimen- which is identical to the Ocean Space Drone 1 (OSD1). tal setup and presets results from the experiments. Courtesy of Kongsberg Seatex. 3.1 Experimental setup length of 12 m, and was steered at a constant speed of 5 The experimental setup was similar to the setup reported knots during the experiments. The OSD1 played the role in Eriksen et al. (2019b), using the Telemetron ASV from of a moving obstacle in the experiments, and was detected Maritime Robotics as the ownship and the Ocean Space and tracked using a radar-based tracking system, which Drone 1 (OSD1) from Kongsberg Seatex as the moving is discussed in detail in Wilthil et al. (2017) and Wilthil obstacle. In addition, virtual static obstacles, expanded (2019). Both the BC-MPC algorithm and the radar track- with a padding radius, were used to emulate static obsta- ing system was implemented using the Robot Operating cles. The padding radius was selected as 150 m in most of System (ROS), and was run on a processing platform with the experiments. Notice that this padding radius only re- an Intel® i7 3:4 GHz CPU running Ubuntu 16.04 Linux lates to static obstacles and that safety margins for moving onboard the Telemetron ASV. See Table 1 for speciﬁca- obstacles are enforced by the obstacle regions in Figure 7. tions on the Telemetron ASV and the sensor system. The Telemetron ASV, shown in Figure 8, is a 26-foot high- speed ASV capable of speeds up to 18 ms and equipped The BC-MPC algorithm was run at a rate of 0:2 Hz with for both manned and unmanned operations. The OSD1, the parameters in Table 2. At sea, vessels typically maneu- shown in Figure 9, is a modiﬁed oﬀshore lifeboat with a ver with large margins, making it safe to run the BC-MPC 7 Table 1: Telemetron ASV speciﬁcations. Table 2: BC-MPC algorithm parameters. Component Description Parameter Value Description Vessel hull Polarcirkel Sport 845 B 3 Trajectory prediction tree Length 8:45 m depth Width 2:71 m T »20; 30; 30¼ s Step time lengths Weight 1675 kg N »5; 1; 1¼ Number of SOG maneuvers Propulsion system Yamaha 225 HP outboard en- N »5; 3; 3¼ Number of course maneuvers gine T 1 s Ramp time ramp Motor control Electro-mechanical actuation T 5 s SOG maneuver length of throttle valve T 5 s Course maneuver length Rudder control Hydraulic actuation of out- w 1:5 Align weight al board engine angle with w 6000 Moving obstacle avoid weight av,m proportional-derivative (PD) w 30 Static obstacle avoid weight av,s feedback control w 2100 SOG transitional cost weight t;U Navigation system Kongsberg Seatex Seapath w 1050 Course transitional cost t; 330+ weight Radar Simrad Broadband 4G™ Radar a 50 m Collision region major axis Processing platform Intel® i7 3:4 GHz CPU, run- 0 a 150 m Safety region major axis ning Ubuntu 16.04 Linux 1 a 250 m Margin region major axis b 25 m Collision region minor axis b 75 m Safety region minor axis algorithm at this rate. Furthermore, the sample time of b 125 m Margin region minor axis the radar is 2:5 s, which together with the dynamics of d 100 m COLREGs expansion COLREGs the tracking system algorithms results in the closed-loop time delay being dominated by the obstacle detection and tracking system. With the given tuning parameters, the have high performance for high-speed ASVs (Eriksen and BC-MPC algorithm has a runtime of approximately 0:4 s Breivik, 2018). (including interfacing the radar tracking system), allow- During the experiments, we tested four diﬀerent scenar- ing for a higher rate if sensors providing faster updates ios: are available. The tuning parameters are quite similar to 1. A static-only scenario with two static obstacles. the ones used in the original algorithm, with the exception of the ﬁrst step time length, which is selected as 20 s in- 2. A head-on situation with the OSD1 and four static stead of 5 s in Eriksen et al. (2019b). With this tuning, obstacles. the algorithm plans for making one maneuver of 5 s at 3. A crossing situation with the OSD1 and one static the current time and keeping a constant course until 20 s obstacle. have passed, rather than planning to do a new maneuver after only 5 s. This represents a more “maritime” way 4. An overtaking situation with the OSD1 and one static to maneuver compared to performing rapid consecutive obstacle. maneuvers, and the transitional cost terms will motivate the algorithm to keep a constant course rather than se- The desired speed of the Telemetron ASV was 5 ms in lecting a new planned maneuver. Notice, however, that all the scenarios, except the overtaking scenario where the the algorithm is still free to choose a new maneuver ev- desired speed was 8 ms. ery 5 s, but the transitional cost terms will favor keeping constant speed and course. To avoid that the vessel con- 3.2 Scenario 1 troller limited the performance of the COLAV system, we used a model-based speed and course controller shown to Scenario 1 is shown in Figure 10. Here, two static obsta- 8 2600 2000 5 3 3400 16 4 3200 4 6 2 13 2600 12 11 500 1000 1500 2000 1500 2000 2500 3000 3500 East [m] East [m] Figure 10: Scenario 1: Static-only scenario. The desired Figure 11: Scenario 2: Head-on situation. The desired tra- trajectory intersects with two obstacles, which the ownship jectory passes through a narrow channel, which is blocked successfully avoids. The blue circle denotes the initial po- by the OSD1. The circles denote the initial positions, sition, while the text and asterisks mark each 60 s of the while the text and asterisks mark each 60 s of the experi- experiment. The yellow patches show the static obsta- ment. The yellow patches show the static obstacles, while cles, while the dark green contour lines show the padding the dark green contour lines show the padding regions. regions. second obstacle by having a small distance to the desired cles block the desired trajectory, requiring the BC-MPC trajectory, which resides slightly inside the padding region algorithm to circumvent the obstacles. This scenario may of the static obstacle. After passing the second obstacle, seem a bit unrealistic, since the high-level planner and mid- the ownship converges to the desired trajectory, before level COLAV algorithm should plan paths which avoid avoiding the ﬁrst obstacle once again. static obstacles. However, the BC-MPC algorithm must be able to avoid static obstacles in order to stay safe in sit- uations where we deviate from the desired trajectory, e.g. 3.3 Scenario 2 when avoiding moving obstacles or in situations where the mid-level algorithm is unable to produce a solution. The Scenario 2 is a head-on situation where the desired tra- ownship converges to the desired trajectory before avoid- jectory goes through a narrow channel composed by two ing the ﬁrst static obstacle by maneuvering to starboard. It static obstacles, and the channel entry is blocked by the would probably have been better to maneuver to port, since OSD1. In this scenario, the padding distance was selected this would avoid having to pass through the narrow channel as 50 m in order to create the narrow channel between the between the ﬁrst and the second obstacle. The BC-MPC obstacles. As shown in Figure 11, the ownship avoids the algorithm does, however, have a limited planning horizon OSD1 by maneuvering to starboard and hence complying of 80 s with the current tuning parameters, which makes it with the COLREGs. Following this turn, the ﬁrst static unaware of the narrow channel when making the decision obstacle is passed on the east side. The ownship returns of maneuvering to starboard. Subsequently, the ownship to the desired trajectory and travels through the channel converges towards the desired trajectory and passes the composed by the two last static obstacles. North [m] North [m] 800 600 1 2800 4 2600 4 3 1500 2000 2500 3000 3500 4000 −200 4 East [m] −400 6 Figure 13: Scenario 4: Overtaking situation. The ownship −600 overtakes the OSD1 by passing on the starboard side, while avoiding the static obstacle. The circles denote the initial −800 positions, while the text and asterisks mark each 60 s of −1000 −500 0 the experiment. The yellow patch shows the static obsta- East [m] cle, while the dark green contour line shows the padding Figure 12: Scenario 3: Crossing situation. The desired region. trajectory intersects with the OSD1, which approaches from starboard. The static obstacle encloses Munkhol- 3.5 Scenario 4 men, which is a small island located in the Trondheims- fjord. The circles denote the initial positions, while the Scenario 4 is an overtaking situation where the ownship text and asterisks mark each 60 s of the experiment. The approaches the OSD1 from behind. To allow the vessel yellow patch shows the static obstacle, while the dark green being overtaken to maneuver to starboard if it ﬁnds itself contour line shows the padding region. in a separate collision situation, the BC-MPC algorithm is designed to favor a port turn in overtaking situations. However, as shown in Figure 13, a static obstacle is block- ing the port side of the obstacle, which makes the ownship 3.4 Scenario 3 pass the obstacle on its starboard side. As mentioned, the BC-MPC algorithm is designed to pass with a larger clear- ance if passing on the port side rather than the starboard Scenario 3, shown in Figure 12, is a crossing situation side, which can be seen by comparing this scenario with where the OSD1 approaches from the ownship’s starboard Experiment 3 in (Eriksen et al., 2019b). side, requiring the ownship to give way to avoid colli- sion according to the COLREGs. In addition, there is a static obstacle on the starboard side of the ownship, block- 3.6 Experiment summary ing the ownship from maneuvering to starboard early. In compliance with the COLREGs, the ownship performs a The BC-MPC algorithm is able to avoid collisions in all the starboard maneuver in order to pass behind the OSD1, scenarios, while converging to the desired trajectory when while passing close to the boundary of the static obsta- it is not obstructed by obstacles. The resulting ownship tra- cle. When the OSD1 has been passed, the ownship slowly jectories are clear and generally show the intension of the converges towards the desired trajectory. The reason for BC-MPC algorithm. The ownship trajectories are, how- the slow convergence is that the cost that the transitional ever, a bit wobbly when the algorithm traverses alongside cost terms introduces is just too large for the algorithm to static obstacles. The reason for this is that the trajectory change to a trajectory with a faster convergence. This is search space consists of a ﬁnite number of trajectories, sometimes observed, but does not compromise safety and of which none may traverse exactly parallel to the static is a subject of tuning the transitional cost weights w and obstacle. This results in that the algorithm sometimes t;U w . choose to “zig-zag” along static obstacles, as seen in Sce- t; North [m] North [m] and vice versa. In addition, the algorithm tuning has been Table 3: Minimum distance to obstacles. *The padding changed in order to obtain more “maritime” maneuvers distance in Scenario 2 is 50 m. and better utilize the transitional cost terms. The modi- Scenario Minimum distance Minimum distance ﬁed BC-MPC algorithm is tested in full-scale experiments number to static obstacles to moving obstacle in the Trondheimsfjord in Norway. A moving obstacle Scenario 1 130:4 m – is detected and tracked using a radar-based system, while Scenario 2 31:3 m* 167:1 m virtual static obstacles are added in the COLAV system. Scenario 3 148:6 m 76:1 m Four diﬀerent scenarios were tested in experiments, all of Scenario 4 115:9 m 145:3 m which provided good results. In Eriksen et al. (2019a), the authors have used the BC-MPC algorithm described in this article in a hybrid nario 1. In the usual case where the mid-level algorithm architecture, demonstrating COLAV compliant with COL- would recompute a collision-free trajectory circumventing REGs rules 8 and 13–17 in simulations. In the future, we the obstacles, the BC-MPC algorithm would however be would like to perform an extensive simulation study of the able to traverse smoothly along the obstacles by following BC-MPC algorithm, in order to analyze the algorithm’s the desired trajectory. Also, due to algae growth on the performance in greater detail. hull, the vessel dynamics had changed quite a bit since the model-based vessel controller was tuned, which also contributed to wobbling in the form of course overshoots. Acknowledgments As seen in Table 3, the ownship travels inside the padding region of the static obstacles. This is to be ex- This work was supported by the Research Council of Nor- pected, since the objective function is only sensitive to way through project number 244116 and the Centres of the static obstacles when the trajectory resides inside of Excellence funding scheme with project number 223254. the padding region. Hence, the padding region and static The authors would like to express great gratitude to Kongs- avoidance weight w should be selected such that a suf- av,s berg Seatex and Maritime Robotics for providing high- ﬁcient safety margin is achieved. A formulation with mul- grade navigation technology, the Telemetron ASV and the tiple regions with diﬀerent gradients, as for moving obsta- OSD1 at our disposal for the experiments. cles, could make it easier to tune the algorithm to obtain a desired safety margin to static obstacles. The required distance to the moving obstacle is a bit more complex to References discuss, since the obstacle regions sizes depend on the relative bearing. The ownship does, however, stay outside Abdelaal, M. and Hahn, A. NMPC-based trajectory track- of the safety region in the head-on and crossing scenar- ing and collision avoidance of unmanned surface vessels ios (scenarios 2 and 3), while we slightly enter the safety with rule-based COLREGs conﬁnement. In Proc. of the region in the overtaking scenario (Scenario 4). 2016 IEEE Conference on Systems, Process and Con- trol (ICSPC). Melaka, Malaysia, pages 23–28, 2016. doi:10.1109/SPC.2016.7920697. 4 Conclusion and further work Benjamin, M. R., Leonard, J. J., Curcio, J. A., and In this article, we have presented two modiﬁcations to the Newman, P. M. A method for protocol-based col- BC-MPC algorithm for ASV COLAV. The ﬁrst modiﬁca- lision avoidance between autonomous marine surface tion allows the algorithm to avoid static obstacles in the craft. Journal of Field Robotics, 2006. 23(5):333–346. form of an occupancy grid. The second modiﬁcation con- doi:10.1002/rob.20121. cerns improved transitional cost terms by introducing tran- sitional cost in speed and course separately, motivating the Bitar, G., Eriksen, B.-O. H., Lekkas, A. M., and Breivik, algorithm to not change the course if the speed is changed M. Energy-optimized hybrid collision avoidance for 11 ASVs. In Proc. of the 17th IEEE European Control Con- Eriksen, B.-O. H., Breivik, M., Wilthil, E. F., Flåten, A. L., ference (ECC). Naples, Italy, pages 2522–2529, 2019. and Brekke, E. F. The branching-course MPC algorithm for maritime collision avoidance. 2019b. Resubmit- Casalino, G., Turetta, A., and Simetti, E. A three- ted to Journal of Field Robotics, preprint available at layered architecture for real time path planning and https://arxiv.org/abs/1907.00039. obstacle avoidance for surveillance USVs operating in harbour ﬁelds. In Proc. of the 2009 IEEE Eriksen, B.-O. H., Wilthil, E. F., Flåten, A. L., Brekke, OCEANS-EUROPE Conference. Bremen, Germany, E. F., and Breivik, M. Radar-based maritime collision 2009. doi:10.1109/oceanse.2009.5278104. avoidance using dynamic window. In Proc. of the 2018 IEEE Aerospace Conference. Big Sky, Montana, USA, Chauvin, C. Human factors and maritime safety. pages 1–9, 2018. doi:10.1109/AERO.2018.8396666. Journal of Navigation, 2011. 64(4):625–632. doi:10.1017/S0373463311000142. Hagen, I. B., Kufoalor, D. K. M., Brekke, E. F., and Jo- hansen, T. A. MPC-based collision avoidance strategy Cockcroft, A. N. and Lameijer, J. N. F. A Guide to the for existing marine vessel guidance systems. In Proc. of Collision Avoidance Rules. Elsevier, 2004. the 2018 IEEE International Conference on Robotics and Automation (ICRA). Brisbane, Australia, pages Dalsnes, B. R., Hexeberg, S., Flåten, A. L., Eriksen, B.- 7618–7623, 2018. doi:10.1109/ICRA.2018.8463182. O. H., and Brekke, E. F. The neighbor course dis- tribution method with Gaussian mixture models for Harati-Mokhtari, A., Wall, A., Brooks, P., and AIS-based vessel trajectory prediction. In Proc. of the Wang, J. Automatic identiﬁcation system (AIS): 21st IEEE International Conference on Information Fu- Data reliability and human error implications. sion (FUSION). Cambridge, UK, pages 580–587, 2018. Journal of Navigation, 2007. 60(3):373–389. doi:10.23919/ICIF.2018.8455607. doi:10.1017/S0373463307004298. Eriksen, B.-O. H., Bitar, G., Breivik, M., and Lekkas, Hexeberg, S., Flåten, A. L., Eriksen, B.-O. H., and Brekke, A. M. Hybrid collision avoidance for ASVs compliant E. F. AIS-based vessel trajectory prediction. In Proc. with COLREGs rules 8 and 13–17. 2019a. Submitted of the 20th IEEE International Conference on Informa- to Frontiers in Robotics and AI, preprint available at tion Fusion (FUSION). Xi’an, China, pages 1–8, 2017. https://arxiv.org/abs/1907.00198. doi:10.23919/ICIF.2017.8009762. Eriksen, B.-O. H. and Breivik, M. Modeling, Identiﬁcation Kuwata, Y., Wolf, M. T., Zarzhitsky, D., and Hunts- and Control of High-Speed ASVs: Theory and Experi- berger, T. L. Safe maritime autonomous navigation ments, pages 407–431. Springer International Publish- with COLREGS, using velocity obstacles. IEEE Jour- ing, 2017a. doi:10.1007/978-3-319-55372-6_19. nal of Oceanic Engineering, 2014. 39(1):110–119. doi:10.1109/joe.2013.2254214. Eriksen, B.-O. H. and Breivik, M. MPC-based mid- level collision avoidance for ASVs using nonlinear Levander, O. Autonomous ships on the high programming. In Proc. of the 1st IEEE Confer- seas. IEEE Spectrum, 2017. 54(2):26–31. ence on Control Technology and Applications (CCTA). doi:10.1109/MSPEC.2017.7833502. Mauna Lani, Hawai’i, USA, pages 766–772, 2017b. doi:10.1109/CCTA.2017.8062554. Loe, Ø. A. G. Collision Avoidance for Unmanned Sur- face Vehicles. Master’s thesis, Norwegian University of Eriksen, B.-O. H. and Breivik, M. A model-based Science and Technology (NTNU), 2008. speed and course controller for high-speed ASVs. In Proc. of the 11th IFAC Conference on Control Paris, C. Norway takes lead in race to build autonomous Applications in Marine Systems, Robotics and Vehi- cargo ships. https://www.wsj.com/articles/norway- cles (CAMS). Opatija, Croatia, pages 317–322, 2018. takes-lead-in-race-to-build-autonomous-cargo-ships- doi:10.1016/j.ifacol.2018.09.504. 1500721202, 2017. Accessed: 2019-05-22. 12 Schuster, M., Blaich, M., and Reuter, J. Collision avoid- doi:10.1109/IROS.2013.6696910. ance for vessels using a low-cost radar sensor. In Proc. Wilthil, E. F. Maritime Target Tracking with Varying Sen- of the 19th IFAC World Congress. pages 9673–9678, sor Performance. Ph.D. thesis, Norwegian University 2014. doi:10.3182/20140824-6-ZA-1003.01872. of Science and Technology (NTNU), 2019. To be sub- Švec, P., Shah, B. C., Bertaska, I. R., Alvarez, J., Sin- mitted. isterra, A. J., von Ellenrieder, K., Dhanak, M., and Gupta, S. K. Dynamics-aware target following for an Wilthil, E. F., Flåten, A. L., and Brekke, E. F. A Target autonomous surface vehicle operating under COLREGs Tracking System for ASV Collision Avoidance Based on in civilian traﬃc. In Proc. of the 2013 IEEE/RSJ In- the PDAF, pages 269–288. Springer International Pub- ternational Conference on Intelligent Robots and Sys- lishing, Cham, 2017. doi:10.1007/978-3-319-55372- tems (IROS). Tokyo, Japan, pages 3871–3878, 2013. 6_13.

Electrical Engineering and Systems Science – arXiv (Cornell University)

**Published: ** Jul 10, 2019

Loading...

You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!

Read and print from thousands of top scholarly journals.

System error. Please try again!

Already have an account? Log in

Bookmark this article. You can see your Bookmarks on your DeepDyve Library.

To save an article, **log in** first, or **sign up** for a DeepDyve account if you don’t already have one.

Copy and paste the desired citation format or use the link below to download a file formatted for EndNote

Access the full text.

Sign up today, get DeepDyve free for 14 days.

All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.