Access the full text.
Sign up today, get DeepDyve free for 14 days.
M. A. Daleh E. Feron (2002)
Real time motion planning for agile autonomous vehicles,AIAA Journal of Guidance Control and Dynamics, 25
T. Fraichard and H. Asama (2004)
Inevitable collision states-a step towards safer robots,Advanced Robotics, 18
David Hsu, R. Kindel, J. Latombe, S. Rock (2002)
Randomized Kinodynamic Motion Planning with Moving ObstaclesThe International Journal of Robotics Research, 21
Thierry Fraichard (1998)
Trajectory planning in a dynamic workspace: a 'state-time space' approachAdv. Robotics, 13
Thomas Wikman, M. Branicky, W. Newman (1993)
Reflexive collision avoidance: a generalized approach[1993] Proceedings IEEE International Conference on Robotics and Automation
Thierry Fraichard (2007)
A Short Paper about Motion SafetyProceedings 2007 IEEE International Conference on Robotics and Automation
Emilio Frazzoli (2003)
Explicit solutions for optimal Maneuver-based motion planning42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475), 4
O. Brock, O. Khatib (2000)
Real-time re-planning in high-dimensional configuration spaces using sets of homotopic pathsProceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), 1
Z. Shiller, O. Gal, Thierry Fraichard (2010)
The Nonlinear Velocity Obstacle Revisited: the Optimal Time Horizon
N. Y. Ko and R. Simmons (1998)
The lane-curvature method for local obstacle avoidance,Proceedings of the International Conference on Intelligence Robots and Systems
M. Benjamin, J. Curcio, J. Leonard, P. Newman (2006)
Navigation of unmanned marine vehicles in accordance with the rules of the roadProceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006.
A. Turetta G. Casalino
Real time path planning and obstacle avoidance for security related usvs operating in harbour fields,Proceedings of the 8th International Conference on Computer Applications and Information Technology in the Maritime Industries (COMPIT '09)
(2001)
Global nearest diagram navigation
G. Casalino, A. Turetta, E. Simetti (2009)
A three-layered architecture for real time path planning and obstacle avoidance for surveillance USVs operating in harbour fieldsOCEANS 2009-EUROPE
Emilio Frazzoli, M. Dahleh, E. Feron (2000)
Real-time motion planning for agile autonomous vehiclesProceedings of the 2001 American Control Conference. (Cat. No.01CH37148), 1
N. Ko, R. Simmons (1998)
The lane-curvature method for local obstacle avoidanceProceedings. 1998 IEEE/RSJ International Conference on Intelligent Robots and Systems. Innovations in Theory, Practice and Applications (Cat. No.98CH36190), 3
S. LaValle, J. Kuffner (1999)
Randomized Kinodynamic PlanningThe International Journal of Robotics Research, 20
Iwan Ulrich, J. Borenstein (1998)
VFH+: reliable obstacle avoidance for fast mobile robotsProceedings. 1998 IEEE International Conference on Robotics and Automation (Cat. No.98CH36146), 2
Z. Shiller, F. Large, S. Sekhavat (2001)
Motion planning in dynamic environments: obstacles moving along arbitrary trajectoriesProceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164), 4
Y. Li and K. M. Lo (2009)
Dynamic and kinematics of novel underwater vehicle-manipulator for cleaning water pool,Proceedings of the IEEE International Conference on Mechatronics and Automation (ICMA '09)
Emilio Frazzoli, M. Dahleh, E. Feron (2005)
Maneuver-based motion planning for nonlinear systems with symmetriesIEEE Transactions on Robotics, 21
O. Brock and O. Khatib
Real-time replanning in high-dimensional configuration spaces using sets of homotopic paths,Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '00)
P. Fiorini, Z. Shiller (1998)
Motion Planning in Dynamic Environments Using Velocity ObstaclesThe International Journal of Robotics Research, 17
S. Sundar, Z. Shiller (1995)
Time-optimal obstacle avoidanceProceedings of 1995 IEEE International Conference on Robotics and Automation, 3
Chiara Fulgenzi, A. Spalanzani, C. Laugier (2007)
Dynamic Obstacle Avoidance in uncertain environment combining PVOs and Occupancy GridProceedings 2007 IEEE International Conference on Robotics and Automation
Yangmin Li, Ka Lo (2009)
Dynamics and kinematics of novel underwater vehicle-manipulator for cleaning water pool2009 International Conference on Mechatronics and Automation
D. Fox, Wolfram Burgard, S. Thrun (1997)
The dynamic window approach to collision avoidanceIEEE Robotics Autom. Mag., 4
E. Frazzoli
Explicit solutions for optimal maneuver-based motion planning,Proceedings of the 42nd IEEE Conference on Decision and Control
S. Petti, Thierry Fraichard (2005)
Safe motion planning in dynamic environments2005 IEEE/RSJ International Conference on Intelligent Robots and Systems
O. Gal, Z. Shiller, E. Rimon (2009)
Efficient and safe on-line motion planning in dynamic environments2009 IEEE International Conference on Robotics and Automation
B. Kluge, E. Prassler (2003)
Recursive Probabilistic Velocity Obstacles for Reflective Navigation
Thierry Fraichard, H. Asama (2003)
Inevitable collision states. A step towards safer robots?Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003) (Cat. No.03CH37453), 1
J. Minguez, L. Montano (2000)
Nearness diagram navigation (ND): a new real time collision avoidance approachProceedings. 2000 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2000) (Cat. No.00CH37113), 3
R. Kindel D. Hsu (2000)
Randomized kinodynamic motion planning with moving obstacles,Algorithmics and Computational Robotics, 4
Nicholas Chan, J. Kuffner, Matthew Zucker (2008)
Improved Motion Planning Speed and Safety using Regions of Inevitable Collision
Hindawi Publishing Corporation Journal of Robotics Volume 2011, Article ID 703959, 8 pages doi:10.1155/2011/703959 Research Article Uniﬁed 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 ﬁrst 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,” ﬁrst 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 signiﬁcant 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 ﬁrst 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 eﬀects 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 diﬀerent 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 speciﬁc 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 ﬁltering. 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 .Wedeﬁne 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 speciﬁc 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 satisﬁed (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 ﬁlter). 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 identiﬁcation 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 oﬀ-line measurements and estimated parameters for a speciﬁc 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 deﬁned. 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 signiﬁcant 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 oﬀ-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 inﬂuence 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 deﬁnes the values over the probability grid and 4.2. Danger Time. One of the most signiﬁcant 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 ﬁnite number of stability analysis and ratio of the USV to wave height). We cells, each cell stores a probabilistic estimation that combines deﬁne 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 deﬁne T (v ) as the ﬁrst 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 diﬀerent 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 deﬁnition 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 eﬀect 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 eﬀect 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 oﬄine 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 ﬁrst 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 ﬁnal 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 ﬁrst 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 ﬁelds,” 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 ﬁelds,” 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 speciﬁc 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 conﬁguration 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, “Reﬂexive long-term eﬀect 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. Kuﬀner, “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.Kuﬀner, “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 reﬂective 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,“Eﬃcient 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 of Robotics – Hindawi Publishing Corporation
Published: Dec 19, 2011
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.
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.