Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Unified Approach of Unmanned Surface Vehicle Navigation in Presence of Waves

Unified Approach of Unmanned Surface Vehicle Navigation in Presence of Waves Hindawi Publishing Corporation Journal of Robotics Volume 2011, Article ID 703959, 8 pages doi:10.1155/2011/703959 Research Article Unified Approach of Unmanned Surface Vehicle Navigation in Presence of Waves Oren Gal Department of Mechanical Engineering, Technion, Israel Institute of Technology, Haifa 32000, Israel Correspondence should be addressed to Oren Gal, orengal@tx.technion.ac.il Received 1 August 2011; Revised 26 October 2011; Accepted 19 November 2011 Academic Editor: Yangmin Li Copyright © 2011 Oren Gal. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Most of the present work for unmanned surface vehicle (USV) navigation does not take into account environmental disturbances such as ocean waves, winds, and currents. In some scenarios, waves should be treated as special case of dynamic obstacle and can be critical to USV’s safety. For the first time, this paper presents unique concept facing this challenge by combining ocean waves’ formulation with the probabilistic velocity obstacle (PVO) method for autonomous navigation. A simple navigation algorithm is presented in order to apply the method of USV’s navigation in presence of waves. A planner simulation dealing with waves and obstacles avoidance is introduced. 1. Introduction ning such as USV motion planning. One approach of safe planning is to use braking policies [15]; anotheristoensure Most of the work on motion planning over the past twenty local avoidance for a limited time [13]. However, neither one years has been focused on ground and aerial vehicles. considers the dynamic of the USV nor the environmental Recently, the research is also focused on unmanned surface disturbances. A promising approach to safe motion planning and underwater vehicles [1–4]. Motion planning of USV in dynamic environment is the consideration of “regions of usually do not deal with waves, currents, and winds, which inevitable collision,” first introduced in [16]and laterex- can be very critical in order to ensure USV’s safety. Generally, tended in [8, 17–19], but still do not treat under actuated we distinguish between local and global planners. The model and environmental disturbances. local planner generates one or a few steps at every time This paper addresses USV’s safe navigation avoiding step, whereas the global planner uses a global search to the moving obstacles considering waves and under actuated con- goal over a time-spanned tree. Examples of local (reactive) strains. Ocean waves are extremely hard to map or to predict. planners are [5–7], but most do not guarantee safety as they Wave’s disturbance is taken into account by combining them are too slow and hence their ability to look ahead and avoid to occupancy grid using probabilistic velocity obstacle (PVO) inevitable collision states (ICSs) [8] is very limited. Recently, concept. Our planner generates near-time optimal trajecto- iterative planners [9–14] were developed that compute ries by selecting at each time step a safe velocity that mini- several steps at a time, subject to the available computational mizes time to the goal dealing with the most significant phe- time. The trajectory is generated incrementally by exploring nomena in marine environments/waves. Using a cost func- a search tree and choosing the best branch. These planners tion (minimum time or distance to goal, minimum fuel, etc.) also do not address the issue of safety and under actuated The allowed attainable velocities are sorted, and the safe and models and, above all, do not take into account the environ- the optimal one is chosen at each time step, for each time mental disturbances (currents, waves, winds, clutter) in step the possible motion primitives of the USV are computed marine environments that can be crucial to the safety of an taking into account kinematic and dynamic constraints. If unmanned vehicle. the primitive is found to be safe enough, it is chosen to be the Only a few works have addressed the safety issue in dy- namic environments, which is crucial for partial (local) plan- next USV’s control, otherwise, it is discarded. The planner is 2 Journal of Robotics demonstrated for online motion planning dealing with waves If T (v) <T (v), then the velocity is dangerous and coll safe and USV’s dynamic constraints in marine environment. discarded. This paper presents waves formulation in PVO concept Main Contribution. For the first time this research generates and a basic formulation of PVO concept, which is not intu- trajectories of USV in presence of waves. The PVO concept itive. Extended description and mathematical proofs of PVO do not deal with USV’s dynamic model nor waves models. can be found in [20]. We extend the PVO concept to marine environments presen- ting full planner with optimal trajectories, treating unsolved 3. Waves issue of autonomous navigation with waves constraints. The PVO concept deals with static and dynamic obstacles 2. Probabilistic Velocity Obstacle with uncertainties, in this paper this concept is extended for a special terrain, water. As mentioned before, ocean waves The probabilistic velocity obstacle (PVO) [20]concept ex- can cause some unwanted effects such as drifts and track- tends the velocity obstacle (VO) [21–24] method by con- ing control errors, and in some cases should be treated as sidering uncertainty of the obstacles both in velocity and “virtual” obstacles and must be taken into account. For that, position. The PVO concept implemented as discrete occu- a basic knowledge of ocean waves is needed. pancy grid that is based on dividing the space into grid and attending different statistical values in each cell [25]. The 3.1. Theory of Ocean Waves. Ocean waves are usually approx- value of each cell in the grid represents the probability of imated by models of winds generating waves. Common an obstacle to be on a specific location based on the other waves modeling are based on nonlinear models of wave obstacles velocities. Each cell stores probabilistic value: spectrum, using wave response transfer function that can be implemented as low-level control system, such as autopilot (i) a value of probability occupation P(Occ); wave filtering. The waves spectrum depends on a large num- (ii) a probabilistic distribution function on a histogram ber of parameters and in some cases include empirical results of possible velocities P(v ), n = 1,... , N. [26]. All of the spectrum modes only take into account wave’s Thepredictedoccupationofeachcellis: peak as a dangerous part that can cause collision, ignoring wave’s lower parts. In this paper, we will assume that all kinds P (Occ) = P (Occ) · P (v ), c c(n) c(n) n (1) of waves are characterized with constant direction and fre- quency, therefore we do not consider superposition of two where c represents the cell, P (Occ) denotes the probability c(n) waves. In order to predict waves, we have to measure obsta- of occupancy of the cell c, P (v ) denotes the probability c(n) n cles, waves, USV’s velocity, and location. The next section that the cell’s velocity is v .Wedefine T as time to col- n break will focus on practical ways to measure waves, obstacles, and lision between the robot and the obstacle, and T as stop- safe USV’s motion parameters. ping time including delay time of the robot to change current velocity, v , 3.2. Measuring Waves Parameters and USV State. In order to navigate safely, USV’s environmental parameters are needed. T (v) = ε + T (v), safe break (2) Usually, motion planning methods assume accurate and where ε is the time delay of the robot dynamics. Estimating available position and velocity of the vehicle. However, in time to collision T (v) value is related to the highest marine environment, most of the measurement equipment break probability to collision, P , that we can deal with during produce false alarms and inaccuracy caused by clutter and safe robot’s motion. Considering a robot velocity v from present environmental disturbances. time to some specific future time t leads to a collision, First, we have to know the exact position of the USV in if there is a collision in the interval [0, t − 1], denote as real time; for that a standard GPS with one pulse per second P (v ), or if there is a collision at time instant t, P (v ). A (PPS) can be satisfied (higher accuracy estimation can be o···t−1 r t r cumulative probability of collision from time 0 to time step t achieved by using Kalman filter). Moreover, USV’s and ob- is recursively computed, P : stacle’s location and velocity also need to be measured. o···t The obstacles’ parameters can be measured by yacht sailing P (v ) = P (v ) + (1 − P (v )) · P (v ), (3) o···t r o···t−1 r o···t−1 r t r radar, nevertheless, such radars have several limitations such as: identifying objects that located close to radar’s antenna, where limited number of targets that can be tracked, and so forth. USV’s close range obstacles identification can be handled P = 0, (4) coll,o by vision methods. These methods are based on cameras where P represents the probability to collision, Time to that located around the USV and can deal with short-range coll collision T is the minimum between t and T , which re- obstacles detection combining image process concept known coll pred presents the time period of a constant motion models relia- as automatic target detection (ATD) algorithms. bility: Height and the direction waves measured by standard equipment (such as ADCP Waves Array sensor of Teledyne T (v ) = min T , t | P (v ) >P . (5) company that can be used for such application). These coll r pred coll,o···t r safe Journal of Robotics 3 1/3 10 20 30 40 Figure 1: Waves height over time. X (m) Figure 2: Wave simulation and occupancy grid. measurements can be integrated with off-line measurements and estimated parameters for a specific day from hydroanal- wave’s frequency and height as cycled disturbance with a ysis based on winds measurements. Sensors inaccuracy and constant frequency, wave characters on a grid can be defined. noises are not included in this model. In Figure 2, several waves moving from the top left corner 3.3. Wave Probability. A common statistical variable used in to the bottom right. The probability for each squared cell is calculated based on sinusoidal equations of the wave’s hydrology is H (also known as H , the significant wave 1/3 s height). This variable represents the average of the third shape. Integrating this information with measured values highest waves measured for a long period of time. H (wave’s shape and frequency), the grid in Figure 2 can be 1/3 represented. In the right side of Figure 2, we can see the grid assumed to be known at each time step in real time, based on measured technique detailed in Section 3.2.In Figure 1, for classic wave movement. The darker cells represent higher probability for wave’s spectrum. On the left side of Figure 2, we can see an example for wave heights over time. Be- the grid represents wave’s shape. The probability on each cell tween the two broken lines, the bold line is the average of the third highest lines H . After many measurements and in the grid is 1/3 observations (which can be done off-line), a statistical con- 2 2 −8A /H 1/3 P = e · cos ωx + φ ,(7) nection between H and height of a single wave with A wave i,j 1/3 1 i,j amplitude can be determined. From empirical model [26], where ω is the wave’s frequency and φ is the phase at cell i,j the well-accepted assumption of wave’s probability with am- c[i, j]. The phase at each cell c[i, j]is plitude A>A is 2πx 2 2 −8A /H 1 1/3 (8) (6) φ = , P(A>A ) = e , i,j where A is the constant amplitude, the wave height is ap- 1 where x is the distance to the next wave peak and λ is the wave proximately twice the amplitude. According to that we can length. calculate at any given time for the current wave’s parameters As we mentioned before, the low part of the wave does the collision probabilities which risks the USV, P ,and coll,t not oppose as much danger as the peaks of the waves, decide whether it is safe to ignore the waves (which means therefore, only the peaks are taken into account. As can see that a special maneuver is needed to avoid the virtual obsta- in Figure 2, the probability of the low part of waves is ap- cle). proximately zero (white cells). USV’s location is updated from the GPS at every time step (averagely 1 second), for that, 4. Marine Probabilistic Velocity Obstacles moderated waves influence is minor. The occupancy grid representing waves is combined with PVO method for mov- In this section we present new formulation of the PVO con- ing obstacles and implemented as detailed in Section 5.The cept that can be used for USV motion planning in presence of occupancy grid is updated at each wave cycle, 1/w. waves using occupancy grid. Unlike the classic PVO concept, the MPVO defines the values over the probability grid and 4.2. Danger Time. One of the most significant parameters in time limitation regarding waves in marine environment. PVO concept is the time danger, but unlike other terrains stopping in front of the wave is not practice. As well known, 4.1. Waves Occupancy Grid. Probabilistic occupancy grids the best way of big vessels to deal with high wave is to are well-known structures used for environmental repre- move vertically (normally) to the wave’s direction (neglecting sentation [25]. The space is divided in finite number of stability analysis and ratio of the USV to wave height). We cells, each cell stores a probabilistic estimation that combines define T (v ) as the time it takes to change USV’s current safe r waves and obstacles. Just like any other obstacles, we would course to a vertical course regarding wave’s direction. We like to include wave’s properties: size (height, direction) and define T (v ) as the first time when P >P so the danger r coll safe speed. By measuring and estimating wave’s shape frequency USV enters unsafe state: and direction, we can calculate the occupancy grid of T (v ) = t, probabilities for different waves by using (6). By measuring (9) danger r h (m) Y (m) 4 Journal of Robotics where north point, etc. [26]), ν = (u, v, r) ∈ R is the veloci- ty vector, τ = (u, r) ∈ R represents the USV’s controls, P (v ) >P . coll,o···t r safe (10) where u is the propulsion force along surge DOF and r re- presents the propulsion moment along yaw DOF. J(ψ) is the In a case of T <T , USV cannot change his current danger safe transformation matrix between velocities. USV’s velocities course moving vertically to the wave’s direction, therefore the and rotation standard definition can be seen in [26]. velocity v is unsafe. The planner is based on explicit form for kinematic model: 4.3. Obstacles’ Properties. Obstacle’s location (latitude, longi- tude, course) and velocity in marine environment are usually r = 0: measured by Radar sensor at each time step (1 sec) and iden- tical to nonlinear velocity obstacles (NLVO) assumptions [23, 24]. We assume nonlinear velocity of the obstacles with (u sin(rΔt) + v(cos(rΔt) − 1)) x(t + Δt) = x(t) + , general trajectory without wave’s dynamic effect regarding obstacle’s location. We model the obstacles as convex shape. (u(1 − cos(rΔt)) + v(sin(rΔt))) However, since the Radar measure the obstacle’s state at each y(t + Δt) = y(t) + , time step, wave’s effect and obstacle velocity are taken into account. Δψ = rt, (12) 5. The Planner In this section we describe planner’s principles. The planner r = 0: based on third highest waves value H that can be measured 1/3 online using drift actuators or offline before mission, which x(t + Δt) = x(t) + uΔt, enable to compute P for each cell (i, j). We seek for single wave velocity that will be safe from obstacles and waves, that is, y(t + Δt) = y(t) + vΔt, (13) allows the USV to avoid the obstacles and if needed to move Δψ = 0. vertically to the waves. The algorithm sorts out the possible velocities for the next time step by the cost function, and then checks each velocity from the best available velocity to 5.2. Motion Primitives. We use trims and primitive libraries the worst. If the velocity causes to collision with any obstacle as discrete point in control space and motion primitives in the near future it’s discarded immediately. If the velocity connect those points similar to Maneuver Automaton [27, was not discarded due to risk of collision, then it is checked 28]. The vehicle model is under actuated with two control from the wave’s aspect. If waves do not oppose any danger, inputs, therefor we control only the propulsion force at surge this velocity will be chosen for the next time step of the DOF and propulsion moment at yaw DOF. We use a simple USV, otherwise, other velocities are also being checked. If no set of speed controller in 3 × 3 grid points in (u, r)asset velocity is found to satisfy completely the waves’ conditions, controllers from U and R,respectively, denotedas τ (i): mp then the velocity that holds the least risk to the USV (and of course does not have risk of collision) will be chosen for the (U, R)(U,0)(U,−R) next time step of the USV, in that way we maintain minimum (0, R)(0, 0)(0,−R) (14) risk from waves. The planner search based on one step ahead greedy algorithm by exploring the best node at each time ( )( )( ) −U, R −U,0 −U,−R . step using local planning. Algorithm pseudocode is detailed in Section 5.4. A motion primitive moves from one speed controller set point to another. At each time step we compute the cost as 5.1. System Dynamics. We consider 3 DOF horizontal model detailed in Section 5.3, w(τ (t + Δt)), for the updated USV r,i neglecting heave, pitch and roll. The dynamic model of the controller τ (t + Δt): r,i USV is under actuated and suitable for small marine vehicles similar to the common USV’s scale [26] in the industry. USV ( ) ( ) ( ) τ t + Δt = τ t + τ i , (15) r,i r,i mp actuators dynamic’s and delays are neglected in this model. We introduce the basic marine model and later on we detail kinematic explicit form for our planner: the safe controller with the lower cost is explored in the next time step, until the USV gets to the target. η˙ = J ψ ν, (11) 5.3. Cost Function. Our search is guided by a minimum Mν + C(ν)ν + D(ν)ν = τ, time cost function to produce near-time optimal trajectories where M is system inertia matrix, C-Coriolis-centripetal to the goal satisfying HJB equation. The cost function for matrix, D-damping matrix, η = (x, y, ψ) ∈ R represents each primitive is the minimum time to the goal from the the USV’s position and orientation in NED system (North- current USV’s state to the target point. It is determined by East-Down coordinate system, x-axis points toward true first computing the minimum time to the goal w(x, x˙, x , x˙ ) f f Journal of Robotics 5 from the current state (x, x˙), where (x, x˙) = (u, r) to the tar- 8000 get point (x , x˙ )for each axis [29, 30]: f f ˙ ˙ w x, x, x , x f f ⎪ 2 x˙ ⎪ x˙ −x˙ − x˙ +2 −x + x + + ,if x ∈ S, 2000 f f 2 2 ⎪ 2 0 x˙ ⎪ x˙ ˙ ˙ x + x +2 x − x + + , otherwise, f f 2 2 −2000 (16) −4000 where S is the region below and above the switching curve in the state space (analytic solution from Bang-Bang optimal −6000 control problem): ⎧ ⎛ ⎞ −8000 x˙ ⎝ ⎠ −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 S(x, x˙) = x˙ − 2 x − x + > 0, (17) Figure 3: Planner simulation environment. ⎛ ⎞ ⎫ x˙ ⎝ ⎠ x˙ +2 x − x − < 0 , Set Target Point X where x and x are the USV’s controller τ (t + Δt)from r,i Measure USV’s location X U and R respectively, and x and x˙ are the target point, Measure USV’s velocity v f f r X , and the velocity at the target which is zero in our case. Set T , P safe safe for t = 0to t do final Considering both axes, the minimum time to the goal used Measure H 1/3 in the cost function is the largest of the times computed for if X = X then r t both axes [29]. This cost function produces sub time-optimal Get a New Waypoint X trajectories to the goal. else for i = 1to n do 5.4. Pseudocode. See Algorithm 1. for j = 1to n do Calculate P wave i,j 5.5. Planner Convergence. Planning in dynamic environ- end for ments is a well-known NP-hard problem, and convergence end for for each node i = 1··· n do can not be proofed for general dynamic environment. On Calculate P coll,t the other hand, grid-based planning methods are known to if P <P then coll,t safe be resolution complete based on the fact that the grid can be τ (t + Δt) = τ (t)+ τ (i) r,i r,i mp very dense and completeness can be achieved. MPVO algo- else rithm is a grid-based concept and for that convergence is the τ (t + Δt) = τ (t)+ τ (max(T )) r,i r,i mp danger same as resolution completeness. The convergence is a theo- end if retical one, so a very dense grid leads to very long computa- Calculate w (τ (t + Δt)) i r,i tion time, which is not applicable in dynamic environments. end for Find Min w (τ (t + Δt)) i = 1··· n i r,i 6. Simulation Results Set τ (t + Δt) r,i min Update X We implemented the algorithm in Matlab application and end if tested it in various simulated environments. The online end for planner was implemented and tested for obstacle-free, and crowded static and dynamic marine environments. The Algorithm 1: Planner pseudocode. marine environment was simulated for random values of H , and with several values of P . Figure 3 shows the com- 1/3 safe plete simulation environment: USV’s current position X represented by a blue point, target point X marked by a yel- [Hz]. Figure 4 shows planner simulation in crowded low triangle, initial USV’s location marked by a blue triangle dynamic environment with P = 0.6. The USV avoid from safe and the obstacles marked by red circles. Wave’s values based the first obstacle ahead and traveling to the goal avoiding on maneuver capabilities of small USV (10 meters length) other obstacles considering wave’s parameter as mentioned was simulated as: A = 3[m], P = 0.5 ± 0.1, T = 5 above, in this case for all t: P <P .In Figure 5 the 1 safe safe coll,t safe [sec], Δt = 0.1 [sec], H = 3 + rand(0, 1) [m], w = 0.06 USV deals with the same scenario but P was set to lower 1/3 safe 6 Journal of Robotics 8000 8000 6000 6000 4000 4000 2000 2000 0 0 −2000 −2000 −4000 −4000 −6000 −6000 −8000 −8000 −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 (a) (b) −2000 −4000 −6000 −8000 −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 (c) Figure 4: Simulation in crowded dynamic environment P = 0.6. safe 8000 8000 6000 6000 4000 4000 2000 2000 0 0 −2000 −2000 −4000 −4000 −6000 −6000 −8000 −8000 −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 (a) (b) Figure 5: Simulation in crowded dynamic environment P = 0.4. safe Journal of Robotics 7 350 in harbour fields,” in Proceedings of the 8th International Con- ference on Computer Applications and Information Technology in the Maritime Industries (COMPIT ’09), 2009. [3] G. Casalino, A. Turetta, and E. Simetti, “A three-layered archi- tecture for real time path planning and obstacle avoidance for surveillance USVs operating in harbour fields,” in Proceedings of the IEEE Bremen: Balancing Technology with Future Needs (OCEANS ’09), May 2009. [4] Y. Li and K. M. Lo, “Dynamic and kinematics of novel underwater vehicle-manipulator for cleaning water pool,” in Proceedings of the IEEE International Conference on Mechatron- ics and Automation (ICMA ’09), pp. 1196–1201, 2009. [5] L. Ulrich and J. Borenstien, “Vfh+: reliable obstacle avoidance for fast mobile robots,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1572–1577, 1999. [6] N. Y. Ko and R. Simmons, “The lane-curvature method for local obstacle avoidance,” in Proceedings of the International 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 Conference on Intelligence Robots and Systems, pp. 1615–1621, Δt (s) 1998. [7] J. Minguez and L. Montano, “Nearest diagram navigation. a Figure 6: Running time versus Δt. new realtime collision avoidance approach,” in Proceedings of the International Conference on Intelligence Robots and Systems, pp. 2094–2100, 2000. [8] T. Fraichard, “A short paper about motion safety,” in Pro- value (0.4), the vehicle react earlier to the obstacle ahead ceedings of the IEEE International Conference on Robotics and Automation (ICRA ’07), pp. 1140–1145, April 2007. thats because in a specific time P >P ,soUSV chose coll,t safe [9] T. Fraichard, “Trajectory planning in a dynamic workspace: a conservative trajectory to avoid collision. In Figure 6 global state-time space approach,” Advanced Robotics, vol. 13, no. 1, running time algorithms versus Δt introduced. Time step pp. 75–94, 1999. was set to 0.1 [sec] from practical sensors abilities measuring [10] D. Hsu, R. Kindel, J.-C. Latombe, and S. Rock, “Random- wave parameters. The algorithm overall running time for ized kinodynamic motion planning with moving obstacles,” 0.1 [sec] time step measured to be 10 [sec] for approximate Algorithmics and Computational Robotics, vol. 4, pp. 247–264, time mission of 6000 [sec], which indicates planner online planning abilities. [11] O. Brock and O. Khatib, “Real-time replanning in high- dimensional configuration spaces using sets of homotopic paths,” in Proceedings of the IEEE International Conference on 7. Conclusions Robotics and Automation (ICRA ’00), pp. 550–555, April 2000. [12] N. Simeon, J. Minguez, L. Montano, and R. Alami, “Global In this paper, a new concept dealing with ocean waves and nearest diagram navigation,” in Proceedings of the IEEE planning safe trajectory of USV was introduced. In order International Conference on Robotics and Automation, pp. 33– to deal with the waves disturbances, we used a grid of pro- 39, 2001. babilities and rephrased the PVO concept dealing with waves. [13] E. Feron, M. A. Daleh, and E. Frazzoli, “Real time motion A practical aspect to measure obstacles and waves in marine planning for agile autonomous vehicles,” AIAA Journal of environments was also introduced. A planner simulations Guidance Control and Dynamics, vol. 25, pp. 116–129, 2002. navigating through waves and avoiding obstacles considering [14] D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” IEEE Robotics and Automa- USV’s dynamic model constrains was developed. Future tion Magazine, vol. 4, no. 1, pp. 23–33, 1997. work will focus on considering smaller waves as well as their [15] T. S. Wikman, W. S. Newman, and M. S. Branicky, “Reflexive long-term effect over the USV’s platform. collision avoidance: a generalized approach,” in Proceedings of the IEEE International Conference on Robotics and Automation, Acknowledgment pp. 31–36, 1993. [16] S. M. LaValle and J. J. Kuffner, “Randomized kinodynamic The author would like to thank Yair Steren for his help during planning,” International Journal of Robotics Research, vol. 20, the research. no. 5, pp. 378–400, 2001. [17] S. Petti and T. Fraichard, “Safe motion planning in dynamic environment,” in Proceedings of the International Conference on Intelligence Robots and Systems, pp. 885–897, 2005. References [18] T. Fraichard and H. Asama, “Inevitable collision states-a step [1] M. R. Benjamin, J. A. Curcio, J. J. Leonard, and P. M. Newman, towards safer robots,” Advanced Robotics, vol. 18, no. 10, pp. “Navigation of unmanned marine vehicles in accordance with 1001–1024, 2004. the rules of the road,” in Proceedings of the IEEE International [19] N. Chan,M.Zucker, andJ.Kuffner, “Improved motion planning speed and safety using region of inevitable collision,” Conference on Robotics and Automation (ICRA ’06), pp. 3581– 3587, Orlando, Fla, USA, May 2006. in Proceedings of the 17th CISM-IFToMM Symposium on Robot Design, Dynamics, and Control (ROMANSY ’08), pp. 103–114, [2] G. Casalino, A. Turetta, and E. Simetti, “Real time path plan- ning and obstacle avoidance for security related usvs operating July 2008. −1 Running time (10 s) 8 Journal of Robotics [20] B. Kluge and E. Prassler, “Recursive probabilistic velocity obstacles for reflective navigation,” in Proceedings of the FSR, pp. 71–79, 2003. [21] P. Fiorini and Z. Shiller, “Motion planning in dynamic en- vironments using velocity obstacles,” International Journal of Robotics Research, vol. 17, no. 7, pp. 760–772, 1998. [22] Z. Shiller, F. Large, and S. Sekhavat, “Motion planning in dynamic environments: obstacles moving along arbitrary tra- jectories,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA ’01), pp. 3716–3721, May [23] O. Gal,Z.Shiller, andE.Rimon,“Efficient and safe on-line motion planning in dynamic environment,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 88–93, 2009. [24] Z. Shiller, O. Gal, and T. Fraichard, “The nonlinear velocity obstacle revisited: the optimal time horizon,” in Proceedings of the Workshop of Safety Motion Planning, 2010. [25] C. Fulgenzi, A. Spalanzani, and C. Laugier, “Dynamic obstacle avoidance in uncertain environment combining pvos and occupancy grid,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1610–1616, 2007. [26] T. I. Fossen, Marine Control Systems. Marine Cybernetics, 2002. [27] E. Frazzoli, M. A. Dahleh, and E. Feron, “Maneuver-based mo- tion planning for nonlinear systems with symmetries,” IEEE Transactions on Robotics, vol. 21, no. 6, pp. 1077–1091, 2005. [28] E. Frazzoli, “Explicit solutions for optimal maneuver-based motion planning,” in Proceedings of the 42nd IEEE Conference on Decision and Control, pp. 3372–3377, December 2003. [29] S. Sundar and Z. Shiller, “Time optimal obstacle avoidance,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 3075–3080, 1995. [30] S. Sundar, Near-Time optimal feedback control of robotic ma- nipulators, Ph.D. thesis, University of California, Los Angeles, Calif, USA, 1995. International Journal of Rotating Machinery International Journal of Journal of The Scientific Journal of Distributed Engineering World Journal Sensors Sensor Networks Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation http://www.hindawi.com http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 Volume 2014 Journal of Control Science and Engineering Advances in Civil Engineering Hindawi Publishing Corporation Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 Submit your manuscripts at http://www.hindawi.com Journal of Journal of Electrical and Computer Robotics Engineering Hindawi Publishing Corporation Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 VLSI Design Advances in OptoElectronics International Journal of Modelling & Aerospace International Journal of Simulation Navigation and in Engineering Engineering Observation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2010 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 http://www.hindawi.com http://www.hindawi.com Volume 2014 International Journal of Active and Passive International Journal of Antennas and Advances in Chemical Engineering Propagation Electronic Components Shock and Vibration Acoustics and Vibration Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Robotics Hindawi Publishing Corporation

Unified Approach of Unmanned Surface Vehicle Navigation in Presence of Waves

Gal, Oren
Journal of Robotics , Volume 2011 – Dec 19, 2011
Download PDF
9 pages

Loading next page...
 
/lp/hindawi-publishing-corporation/unified-approach-of-unmanned-surface-vehicle-navigation-in-presence-of-ZyxPgVM6ry

References (35)

Publisher
Hindawi Publishing Corporation
Copyright
Copyright © 2011 Oren Gal. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
ISSN
1687-9600
eISSN
1687-9619
DOI
10.1155/2011/703959
Publisher site
See Article on Publisher Site

Abstract

Hindawi Publishing Corporation Journal of Robotics Volume 2011, Article ID 703959, 8 pages doi:10.1155/2011/703959 Research Article Unified Approach of Unmanned Surface Vehicle Navigation in Presence of Waves Oren Gal Department of Mechanical Engineering, Technion, Israel Institute of Technology, Haifa 32000, Israel Correspondence should be addressed to Oren Gal, orengal@tx.technion.ac.il Received 1 August 2011; Revised 26 October 2011; Accepted 19 November 2011 Academic Editor: Yangmin Li Copyright © 2011 Oren Gal. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Most of the present work for unmanned surface vehicle (USV) navigation does not take into account environmental disturbances such as ocean waves, winds, and currents. In some scenarios, waves should be treated as special case of dynamic obstacle and can be critical to USV’s safety. For the first time, this paper presents unique concept facing this challenge by combining ocean waves’ formulation with the probabilistic velocity obstacle (PVO) method for autonomous navigation. A simple navigation algorithm is presented in order to apply the method of USV’s navigation in presence of waves. A planner simulation dealing with waves and obstacles avoidance is introduced. 1. Introduction ning such as USV motion planning. One approach of safe planning is to use braking policies [15]; anotheristoensure Most of the work on motion planning over the past twenty local avoidance for a limited time [13]. However, neither one years has been focused on ground and aerial vehicles. considers the dynamic of the USV nor the environmental Recently, the research is also focused on unmanned surface disturbances. A promising approach to safe motion planning and underwater vehicles [1–4]. Motion planning of USV in dynamic environment is the consideration of “regions of usually do not deal with waves, currents, and winds, which inevitable collision,” first introduced in [16]and laterex- can be very critical in order to ensure USV’s safety. Generally, tended in [8, 17–19], but still do not treat under actuated we distinguish between local and global planners. The model and environmental disturbances. local planner generates one or a few steps at every time This paper addresses USV’s safe navigation avoiding step, whereas the global planner uses a global search to the moving obstacles considering waves and under actuated con- goal over a time-spanned tree. Examples of local (reactive) strains. Ocean waves are extremely hard to map or to predict. planners are [5–7], but most do not guarantee safety as they Wave’s disturbance is taken into account by combining them are too slow and hence their ability to look ahead and avoid to occupancy grid using probabilistic velocity obstacle (PVO) inevitable collision states (ICSs) [8] is very limited. Recently, concept. Our planner generates near-time optimal trajecto- iterative planners [9–14] were developed that compute ries by selecting at each time step a safe velocity that mini- several steps at a time, subject to the available computational mizes time to the goal dealing with the most significant phe- time. The trajectory is generated incrementally by exploring nomena in marine environments/waves. Using a cost func- a search tree and choosing the best branch. These planners tion (minimum time or distance to goal, minimum fuel, etc.) also do not address the issue of safety and under actuated The allowed attainable velocities are sorted, and the safe and models and, above all, do not take into account the environ- the optimal one is chosen at each time step, for each time mental disturbances (currents, waves, winds, clutter) in step the possible motion primitives of the USV are computed marine environments that can be crucial to the safety of an taking into account kinematic and dynamic constraints. If unmanned vehicle. the primitive is found to be safe enough, it is chosen to be the Only a few works have addressed the safety issue in dy- namic environments, which is crucial for partial (local) plan- next USV’s control, otherwise, it is discarded. The planner is 2 Journal of Robotics demonstrated for online motion planning dealing with waves If T (v) <T (v), then the velocity is dangerous and coll safe and USV’s dynamic constraints in marine environment. discarded. This paper presents waves formulation in PVO concept Main Contribution. For the first time this research generates and a basic formulation of PVO concept, which is not intu- trajectories of USV in presence of waves. The PVO concept itive. Extended description and mathematical proofs of PVO do not deal with USV’s dynamic model nor waves models. can be found in [20]. We extend the PVO concept to marine environments presen- ting full planner with optimal trajectories, treating unsolved 3. Waves issue of autonomous navigation with waves constraints. The PVO concept deals with static and dynamic obstacles 2. Probabilistic Velocity Obstacle with uncertainties, in this paper this concept is extended for a special terrain, water. As mentioned before, ocean waves The probabilistic velocity obstacle (PVO) [20]concept ex- can cause some unwanted effects such as drifts and track- tends the velocity obstacle (VO) [21–24] method by con- ing control errors, and in some cases should be treated as sidering uncertainty of the obstacles both in velocity and “virtual” obstacles and must be taken into account. For that, position. The PVO concept implemented as discrete occu- a basic knowledge of ocean waves is needed. pancy grid that is based on dividing the space into grid and attending different statistical values in each cell [25]. The 3.1. Theory of Ocean Waves. Ocean waves are usually approx- value of each cell in the grid represents the probability of imated by models of winds generating waves. Common an obstacle to be on a specific location based on the other waves modeling are based on nonlinear models of wave obstacles velocities. Each cell stores probabilistic value: spectrum, using wave response transfer function that can be implemented as low-level control system, such as autopilot (i) a value of probability occupation P(Occ); wave filtering. The waves spectrum depends on a large num- (ii) a probabilistic distribution function on a histogram ber of parameters and in some cases include empirical results of possible velocities P(v ), n = 1,... , N. [26]. All of the spectrum modes only take into account wave’s Thepredictedoccupationofeachcellis: peak as a dangerous part that can cause collision, ignoring wave’s lower parts. In this paper, we will assume that all kinds P (Occ) = P (Occ) · P (v ), c c(n) c(n) n (1) of waves are characterized with constant direction and fre- quency, therefore we do not consider superposition of two where c represents the cell, P (Occ) denotes the probability c(n) waves. In order to predict waves, we have to measure obsta- of occupancy of the cell c, P (v ) denotes the probability c(n) n cles, waves, USV’s velocity, and location. The next section that the cell’s velocity is v .Wedefine T as time to col- n break will focus on practical ways to measure waves, obstacles, and lision between the robot and the obstacle, and T as stop- safe USV’s motion parameters. ping time including delay time of the robot to change current velocity, v , 3.2. Measuring Waves Parameters and USV State. In order to navigate safely, USV’s environmental parameters are needed. T (v) = ε + T (v), safe break (2) Usually, motion planning methods assume accurate and where ε is the time delay of the robot dynamics. Estimating available position and velocity of the vehicle. However, in time to collision T (v) value is related to the highest marine environment, most of the measurement equipment break probability to collision, P , that we can deal with during produce false alarms and inaccuracy caused by clutter and safe robot’s motion. Considering a robot velocity v from present environmental disturbances. time to some specific future time t leads to a collision, First, we have to know the exact position of the USV in if there is a collision in the interval [0, t − 1], denote as real time; for that a standard GPS with one pulse per second P (v ), or if there is a collision at time instant t, P (v ). A (PPS) can be satisfied (higher accuracy estimation can be o···t−1 r t r cumulative probability of collision from time 0 to time step t achieved by using Kalman filter). Moreover, USV’s and ob- is recursively computed, P : stacle’s location and velocity also need to be measured. o···t The obstacles’ parameters can be measured by yacht sailing P (v ) = P (v ) + (1 − P (v )) · P (v ), (3) o···t r o···t−1 r o···t−1 r t r radar, nevertheless, such radars have several limitations such as: identifying objects that located close to radar’s antenna, where limited number of targets that can be tracked, and so forth. USV’s close range obstacles identification can be handled P = 0, (4) coll,o by vision methods. These methods are based on cameras where P represents the probability to collision, Time to that located around the USV and can deal with short-range coll collision T is the minimum between t and T , which re- obstacles detection combining image process concept known coll pred presents the time period of a constant motion models relia- as automatic target detection (ATD) algorithms. bility: Height and the direction waves measured by standard equipment (such as ADCP Waves Array sensor of Teledyne T (v ) = min T , t | P (v ) >P . (5) company that can be used for such application). These coll r pred coll,o···t r safe Journal of Robotics 3 1/3 10 20 30 40 Figure 1: Waves height over time. X (m) Figure 2: Wave simulation and occupancy grid. measurements can be integrated with off-line measurements and estimated parameters for a specific day from hydroanal- wave’s frequency and height as cycled disturbance with a ysis based on winds measurements. Sensors inaccuracy and constant frequency, wave characters on a grid can be defined. noises are not included in this model. In Figure 2, several waves moving from the top left corner 3.3. Wave Probability. A common statistical variable used in to the bottom right. The probability for each squared cell is calculated based on sinusoidal equations of the wave’s hydrology is H (also known as H , the significant wave 1/3 s height). This variable represents the average of the third shape. Integrating this information with measured values highest waves measured for a long period of time. H (wave’s shape and frequency), the grid in Figure 2 can be 1/3 represented. In the right side of Figure 2, we can see the grid assumed to be known at each time step in real time, based on measured technique detailed in Section 3.2.In Figure 1, for classic wave movement. The darker cells represent higher probability for wave’s spectrum. On the left side of Figure 2, we can see an example for wave heights over time. Be- the grid represents wave’s shape. The probability on each cell tween the two broken lines, the bold line is the average of the third highest lines H . After many measurements and in the grid is 1/3 observations (which can be done off-line), a statistical con- 2 2 −8A /H 1/3 P = e · cos ωx + φ ,(7) nection between H and height of a single wave with A wave i,j 1/3 1 i,j amplitude can be determined. From empirical model [26], where ω is the wave’s frequency and φ is the phase at cell i,j the well-accepted assumption of wave’s probability with am- c[i, j]. The phase at each cell c[i, j]is plitude A>A is 2πx 2 2 −8A /H 1 1/3 (8) (6) φ = , P(A>A ) = e , i,j where A is the constant amplitude, the wave height is ap- 1 where x is the distance to the next wave peak and λ is the wave proximately twice the amplitude. According to that we can length. calculate at any given time for the current wave’s parameters As we mentioned before, the low part of the wave does the collision probabilities which risks the USV, P ,and coll,t not oppose as much danger as the peaks of the waves, decide whether it is safe to ignore the waves (which means therefore, only the peaks are taken into account. As can see that a special maneuver is needed to avoid the virtual obsta- in Figure 2, the probability of the low part of waves is ap- cle). proximately zero (white cells). USV’s location is updated from the GPS at every time step (averagely 1 second), for that, 4. Marine Probabilistic Velocity Obstacles moderated waves influence is minor. The occupancy grid representing waves is combined with PVO method for mov- In this section we present new formulation of the PVO con- ing obstacles and implemented as detailed in Section 5.The cept that can be used for USV motion planning in presence of occupancy grid is updated at each wave cycle, 1/w. waves using occupancy grid. Unlike the classic PVO concept, the MPVO defines the values over the probability grid and 4.2. Danger Time. One of the most significant parameters in time limitation regarding waves in marine environment. PVO concept is the time danger, but unlike other terrains stopping in front of the wave is not practice. As well known, 4.1. Waves Occupancy Grid. Probabilistic occupancy grids the best way of big vessels to deal with high wave is to are well-known structures used for environmental repre- move vertically (normally) to the wave’s direction (neglecting sentation [25]. The space is divided in finite number of stability analysis and ratio of the USV to wave height). We cells, each cell stores a probabilistic estimation that combines define T (v ) as the time it takes to change USV’s current safe r waves and obstacles. Just like any other obstacles, we would course to a vertical course regarding wave’s direction. We like to include wave’s properties: size (height, direction) and define T (v ) as the first time when P >P so the danger r coll safe speed. By measuring and estimating wave’s shape frequency USV enters unsafe state: and direction, we can calculate the occupancy grid of T (v ) = t, probabilities for different waves by using (6). By measuring (9) danger r h (m) Y (m) 4 Journal of Robotics where north point, etc. [26]), ν = (u, v, r) ∈ R is the veloci- ty vector, τ = (u, r) ∈ R represents the USV’s controls, P (v ) >P . coll,o···t r safe (10) where u is the propulsion force along surge DOF and r re- presents the propulsion moment along yaw DOF. J(ψ) is the In a case of T <T , USV cannot change his current danger safe transformation matrix between velocities. USV’s velocities course moving vertically to the wave’s direction, therefore the and rotation standard definition can be seen in [26]. velocity v is unsafe. The planner is based on explicit form for kinematic model: 4.3. Obstacles’ Properties. Obstacle’s location (latitude, longi- tude, course) and velocity in marine environment are usually r = 0: measured by Radar sensor at each time step (1 sec) and iden- tical to nonlinear velocity obstacles (NLVO) assumptions [23, 24]. We assume nonlinear velocity of the obstacles with (u sin(rΔt) + v(cos(rΔt) − 1)) x(t + Δt) = x(t) + , general trajectory without wave’s dynamic effect regarding obstacle’s location. We model the obstacles as convex shape. (u(1 − cos(rΔt)) + v(sin(rΔt))) However, since the Radar measure the obstacle’s state at each y(t + Δt) = y(t) + , time step, wave’s effect and obstacle velocity are taken into account. Δψ = rt, (12) 5. The Planner In this section we describe planner’s principles. The planner r = 0: based on third highest waves value H that can be measured 1/3 online using drift actuators or offline before mission, which x(t + Δt) = x(t) + uΔt, enable to compute P for each cell (i, j). We seek for single wave velocity that will be safe from obstacles and waves, that is, y(t + Δt) = y(t) + vΔt, (13) allows the USV to avoid the obstacles and if needed to move Δψ = 0. vertically to the waves. The algorithm sorts out the possible velocities for the next time step by the cost function, and then checks each velocity from the best available velocity to 5.2. Motion Primitives. We use trims and primitive libraries the worst. If the velocity causes to collision with any obstacle as discrete point in control space and motion primitives in the near future it’s discarded immediately. If the velocity connect those points similar to Maneuver Automaton [27, was not discarded due to risk of collision, then it is checked 28]. The vehicle model is under actuated with two control from the wave’s aspect. If waves do not oppose any danger, inputs, therefor we control only the propulsion force at surge this velocity will be chosen for the next time step of the DOF and propulsion moment at yaw DOF. We use a simple USV, otherwise, other velocities are also being checked. If no set of speed controller in 3 × 3 grid points in (u, r)asset velocity is found to satisfy completely the waves’ conditions, controllers from U and R,respectively, denotedas τ (i): mp then the velocity that holds the least risk to the USV (and of course does not have risk of collision) will be chosen for the (U, R)(U,0)(U,−R) next time step of the USV, in that way we maintain minimum (0, R)(0, 0)(0,−R) (14) risk from waves. The planner search based on one step ahead greedy algorithm by exploring the best node at each time ( )( )( ) −U, R −U,0 −U,−R . step using local planning. Algorithm pseudocode is detailed in Section 5.4. A motion primitive moves from one speed controller set point to another. At each time step we compute the cost as 5.1. System Dynamics. We consider 3 DOF horizontal model detailed in Section 5.3, w(τ (t + Δt)), for the updated USV r,i neglecting heave, pitch and roll. The dynamic model of the controller τ (t + Δt): r,i USV is under actuated and suitable for small marine vehicles similar to the common USV’s scale [26] in the industry. USV ( ) ( ) ( ) τ t + Δt = τ t + τ i , (15) r,i r,i mp actuators dynamic’s and delays are neglected in this model. We introduce the basic marine model and later on we detail kinematic explicit form for our planner: the safe controller with the lower cost is explored in the next time step, until the USV gets to the target. η˙ = J ψ ν, (11) 5.3. Cost Function. Our search is guided by a minimum Mν + C(ν)ν + D(ν)ν = τ, time cost function to produce near-time optimal trajectories where M is system inertia matrix, C-Coriolis-centripetal to the goal satisfying HJB equation. The cost function for matrix, D-damping matrix, η = (x, y, ψ) ∈ R represents each primitive is the minimum time to the goal from the the USV’s position and orientation in NED system (North- current USV’s state to the target point. It is determined by East-Down coordinate system, x-axis points toward true first computing the minimum time to the goal w(x, x˙, x , x˙ ) f f Journal of Robotics 5 from the current state (x, x˙), where (x, x˙) = (u, r) to the tar- 8000 get point (x , x˙ )for each axis [29, 30]: f f ˙ ˙ w x, x, x , x f f ⎪ 2 x˙ ⎪ x˙ −x˙ − x˙ +2 −x + x + + ,if x ∈ S, 2000 f f 2 2 ⎪ 2 0 x˙ ⎪ x˙ ˙ ˙ x + x +2 x − x + + , otherwise, f f 2 2 −2000 (16) −4000 where S is the region below and above the switching curve in the state space (analytic solution from Bang-Bang optimal −6000 control problem): ⎧ ⎛ ⎞ −8000 x˙ ⎝ ⎠ −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 S(x, x˙) = x˙ − 2 x − x + > 0, (17) Figure 3: Planner simulation environment. ⎛ ⎞ ⎫ x˙ ⎝ ⎠ x˙ +2 x − x − < 0 , Set Target Point X where x and x are the USV’s controller τ (t + Δt)from r,i Measure USV’s location X U and R respectively, and x and x˙ are the target point, Measure USV’s velocity v f f r X , and the velocity at the target which is zero in our case. Set T , P safe safe for t = 0to t do final Considering both axes, the minimum time to the goal used Measure H 1/3 in the cost function is the largest of the times computed for if X = X then r t both axes [29]. This cost function produces sub time-optimal Get a New Waypoint X trajectories to the goal. else for i = 1to n do 5.4. Pseudocode. See Algorithm 1. for j = 1to n do Calculate P wave i,j 5.5. Planner Convergence. Planning in dynamic environ- end for ments is a well-known NP-hard problem, and convergence end for for each node i = 1··· n do can not be proofed for general dynamic environment. On Calculate P coll,t the other hand, grid-based planning methods are known to if P <P then coll,t safe be resolution complete based on the fact that the grid can be τ (t + Δt) = τ (t)+ τ (i) r,i r,i mp very dense and completeness can be achieved. MPVO algo- else rithm is a grid-based concept and for that convergence is the τ (t + Δt) = τ (t)+ τ (max(T )) r,i r,i mp danger same as resolution completeness. The convergence is a theo- end if retical one, so a very dense grid leads to very long computa- Calculate w (τ (t + Δt)) i r,i tion time, which is not applicable in dynamic environments. end for Find Min w (τ (t + Δt)) i = 1··· n i r,i 6. Simulation Results Set τ (t + Δt) r,i min Update X We implemented the algorithm in Matlab application and end if tested it in various simulated environments. The online end for planner was implemented and tested for obstacle-free, and crowded static and dynamic marine environments. The Algorithm 1: Planner pseudocode. marine environment was simulated for random values of H , and with several values of P . Figure 3 shows the com- 1/3 safe plete simulation environment: USV’s current position X represented by a blue point, target point X marked by a yel- [Hz]. Figure 4 shows planner simulation in crowded low triangle, initial USV’s location marked by a blue triangle dynamic environment with P = 0.6. The USV avoid from safe and the obstacles marked by red circles. Wave’s values based the first obstacle ahead and traveling to the goal avoiding on maneuver capabilities of small USV (10 meters length) other obstacles considering wave’s parameter as mentioned was simulated as: A = 3[m], P = 0.5 ± 0.1, T = 5 above, in this case for all t: P <P .In Figure 5 the 1 safe safe coll,t safe [sec], Δt = 0.1 [sec], H = 3 + rand(0, 1) [m], w = 0.06 USV deals with the same scenario but P was set to lower 1/3 safe 6 Journal of Robotics 8000 8000 6000 6000 4000 4000 2000 2000 0 0 −2000 −2000 −4000 −4000 −6000 −6000 −8000 −8000 −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 (a) (b) −2000 −4000 −6000 −8000 −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 (c) Figure 4: Simulation in crowded dynamic environment P = 0.6. safe 8000 8000 6000 6000 4000 4000 2000 2000 0 0 −2000 −2000 −4000 −4000 −6000 −6000 −8000 −8000 −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 −8000 −6000 −4000 −2000 0 2000 4000 6000 8000 (a) (b) Figure 5: Simulation in crowded dynamic environment P = 0.4. safe Journal of Robotics 7 350 in harbour fields,” in Proceedings of the 8th International Con- ference on Computer Applications and Information Technology in the Maritime Industries (COMPIT ’09), 2009. [3] G. Casalino, A. Turetta, and E. Simetti, “A three-layered archi- tecture for real time path planning and obstacle avoidance for surveillance USVs operating in harbour fields,” in Proceedings of the IEEE Bremen: Balancing Technology with Future Needs (OCEANS ’09), May 2009. [4] Y. Li and K. M. Lo, “Dynamic and kinematics of novel underwater vehicle-manipulator for cleaning water pool,” in Proceedings of the IEEE International Conference on Mechatron- ics and Automation (ICMA ’09), pp. 1196–1201, 2009. [5] L. Ulrich and J. Borenstien, “Vfh+: reliable obstacle avoidance for fast mobile robots,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1572–1577, 1999. [6] N. Y. Ko and R. Simmons, “The lane-curvature method for local obstacle avoidance,” in Proceedings of the International 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 Conference on Intelligence Robots and Systems, pp. 1615–1621, Δt (s) 1998. [7] J. Minguez and L. Montano, “Nearest diagram navigation. a Figure 6: Running time versus Δt. new realtime collision avoidance approach,” in Proceedings of the International Conference on Intelligence Robots and Systems, pp. 2094–2100, 2000. [8] T. Fraichard, “A short paper about motion safety,” in Pro- value (0.4), the vehicle react earlier to the obstacle ahead ceedings of the IEEE International Conference on Robotics and Automation (ICRA ’07), pp. 1140–1145, April 2007. thats because in a specific time P >P ,soUSV chose coll,t safe [9] T. Fraichard, “Trajectory planning in a dynamic workspace: a conservative trajectory to avoid collision. In Figure 6 global state-time space approach,” Advanced Robotics, vol. 13, no. 1, running time algorithms versus Δt introduced. Time step pp. 75–94, 1999. was set to 0.1 [sec] from practical sensors abilities measuring [10] D. Hsu, R. Kindel, J.-C. Latombe, and S. Rock, “Random- wave parameters. The algorithm overall running time for ized kinodynamic motion planning with moving obstacles,” 0.1 [sec] time step measured to be 10 [sec] for approximate Algorithmics and Computational Robotics, vol. 4, pp. 247–264, time mission of 6000 [sec], which indicates planner online planning abilities. [11] O. Brock and O. Khatib, “Real-time replanning in high- dimensional configuration spaces using sets of homotopic paths,” in Proceedings of the IEEE International Conference on 7. Conclusions Robotics and Automation (ICRA ’00), pp. 550–555, April 2000. [12] N. Simeon, J. Minguez, L. Montano, and R. Alami, “Global In this paper, a new concept dealing with ocean waves and nearest diagram navigation,” in Proceedings of the IEEE planning safe trajectory of USV was introduced. In order International Conference on Robotics and Automation, pp. 33– to deal with the waves disturbances, we used a grid of pro- 39, 2001. babilities and rephrased the PVO concept dealing with waves. [13] E. Feron, M. A. Daleh, and E. Frazzoli, “Real time motion A practical aspect to measure obstacles and waves in marine planning for agile autonomous vehicles,” AIAA Journal of environments was also introduced. A planner simulations Guidance Control and Dynamics, vol. 25, pp. 116–129, 2002. navigating through waves and avoiding obstacles considering [14] D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” IEEE Robotics and Automa- USV’s dynamic model constrains was developed. Future tion Magazine, vol. 4, no. 1, pp. 23–33, 1997. work will focus on considering smaller waves as well as their [15] T. S. Wikman, W. S. Newman, and M. S. Branicky, “Reflexive long-term effect over the USV’s platform. collision avoidance: a generalized approach,” in Proceedings of the IEEE International Conference on Robotics and Automation, Acknowledgment pp. 31–36, 1993. [16] S. M. LaValle and J. J. Kuffner, “Randomized kinodynamic The author would like to thank Yair Steren for his help during planning,” International Journal of Robotics Research, vol. 20, the research. no. 5, pp. 378–400, 2001. [17] S. Petti and T. Fraichard, “Safe motion planning in dynamic environment,” in Proceedings of the International Conference on Intelligence Robots and Systems, pp. 885–897, 2005. References [18] T. Fraichard and H. Asama, “Inevitable collision states-a step [1] M. R. Benjamin, J. A. Curcio, J. J. Leonard, and P. M. Newman, towards safer robots,” Advanced Robotics, vol. 18, no. 10, pp. “Navigation of unmanned marine vehicles in accordance with 1001–1024, 2004. the rules of the road,” in Proceedings of the IEEE International [19] N. Chan,M.Zucker, andJ.Kuffner, “Improved motion planning speed and safety using region of inevitable collision,” Conference on Robotics and Automation (ICRA ’06), pp. 3581– 3587, Orlando, Fla, USA, May 2006. in Proceedings of the 17th CISM-IFToMM Symposium on Robot Design, Dynamics, and Control (ROMANSY ’08), pp. 103–114, [2] G. Casalino, A. Turetta, and E. Simetti, “Real time path plan- ning and obstacle avoidance for security related usvs operating July 2008. −1 Running time (10 s) 8 Journal of Robotics [20] B. Kluge and E. Prassler, “Recursive probabilistic velocity obstacles for reflective navigation,” in Proceedings of the FSR, pp. 71–79, 2003. [21] P. Fiorini and Z. Shiller, “Motion planning in dynamic en- vironments using velocity obstacles,” International Journal of Robotics Research, vol. 17, no. 7, pp. 760–772, 1998. [22] Z. Shiller, F. Large, and S. Sekhavat, “Motion planning in dynamic environments: obstacles moving along arbitrary tra- jectories,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA ’01), pp. 3716–3721, May [23] O. Gal,Z.Shiller, andE.Rimon,“Efficient and safe on-line motion planning in dynamic environment,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 88–93, 2009. [24] Z. Shiller, O. Gal, and T. Fraichard, “The nonlinear velocity obstacle revisited: the optimal time horizon,” in Proceedings of the Workshop of Safety Motion Planning, 2010. [25] C. Fulgenzi, A. Spalanzani, and C. Laugier, “Dynamic obstacle avoidance in uncertain environment combining pvos and occupancy grid,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1610–1616, 2007. [26] T. I. Fossen, Marine Control Systems. Marine Cybernetics, 2002. [27] E. Frazzoli, M. A. Dahleh, and E. Feron, “Maneuver-based mo- tion planning for nonlinear systems with symmetries,” IEEE Transactions on Robotics, vol. 21, no. 6, pp. 1077–1091, 2005. [28] E. Frazzoli, “Explicit solutions for optimal maneuver-based motion planning,” in Proceedings of the 42nd IEEE Conference on Decision and Control, pp. 3372–3377, December 2003. [29] S. Sundar and Z. Shiller, “Time optimal obstacle avoidance,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 3075–3080, 1995. [30] S. Sundar, Near-Time optimal feedback control of robotic ma- nipulators, Ph.D. thesis, University of California, Los Angeles, Calif, USA, 1995. International Journal of Rotating Machinery International Journal of Journal of The Scientific Journal of Distributed Engineering World Journal Sensors Sensor Networks Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation http://www.hindawi.com http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 Volume 2014 Journal of Control Science and Engineering Advances in Civil Engineering Hindawi Publishing Corporation Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 Submit your manuscripts at http://www.hindawi.com Journal of Journal of Electrical and Computer Robotics Engineering Hindawi Publishing Corporation Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 VLSI Design Advances in OptoElectronics International Journal of Modelling & Aerospace International Journal of Simulation Navigation and in Engineering Engineering Observation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2010 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 http://www.hindawi.com http://www.hindawi.com Volume 2014 International Journal of Active and Passive International Journal of Antennas and Advances in Chemical Engineering Propagation Electronic Components Shock and Vibration Acoustics and Vibration Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014 http://www.hindawi.com Volume 2014

Journal

Journal of Robotics – Hindawi Publishing Corporation

Published: Dec 19, 2011

There are no references for this article.