In recent years, unmanned surface vehicles (USVs) have been increasingly used in many marine applications including ocean sampling, maritime search and rescue, hydrologic surveys, harbor surveillance, and defense. USVs have been also used in assisting autonomous underwater vehicles (AUVs) to explore behaviors of marine species, observe coral reefs, search for natural resources. The growing variety and complexity of research and application oriented tasks require unmanned systems to operate fully autonomously over long time horizons, even in environments with significant moving obstacle traffic, for example, manned, commercial, and recreational vehicles (referred to herein as “civilian vehicles” or “CVs”). The complexity of the environments creates significant challenges for autonomous avoidance of CVs by the USVs. For example, the vessels as well as the unmanned systems have different dynamic characteristics depending on their types and dimensions which in turn affects their braking distance and minimum turning radius.
The International Maritime Organization (IMO) has developed a standardized set of rules called the International Regulations for the Prevention of Collisions at Sea (COLREGS), which serves as a guide for selecting avoidance maneuvers. In order to ensure increased operational safety, it is mandatory for all vessels to comply with these rules throughout their missions. The development of long-term autonomy for USVs requires incorporating COLREGS directly into their behavior-based architectures. While attempts have been made to integrate COLREGS into a path planning algorithm for USVs, these approaches can only operate safely in relatively simple scenarios with less civilian traffic. The approaches also assume that each vessel has the same amount of information about the current COLREGS situation and thus it perceives and reacts in the same way, which may not apply in real-world scenarios where each vessel operator may interpret the COLREGS differently, depending upon perception and estimates of the surrounding vessels among other things.
Referring to FIG. 1, an example harbor scenario is illustrated, where a USV 102 enters the harbor from the south channel 106c with the objective of reaching the west channel 106d. Under ideal conditions, each vessel 104a-104d is assumed to follow COLREGS while avoiding its fellow vessels. As per the scenario described in FIG. 1, CV1 104a is crossing from the right side and the COLREGS “Rule 15” applies (details on specific COLREGS rules can be found on the U.S. Department of Homeland Security, U.S. Coast Guard, Navigation Center website). In this situation, the USV 102 can either yield to CV1 104a (since the vessel 104a has the right of way) by slowing down to a steady state or passing it to the right. Alternatively, the USV 102 can breach the COLREGS by not yielding to CV1 104a and CV3 104c while moving to the west channel 106d. 
If the USV 102 chooses the first option, i.e., to slow down and wait for CV1 104a to pass, then it will block the entire south east channel 106c for some time and thus obstruct the way of CV2 104b. Thus, both USV 102 and CV2 104b will have to wait and try to maintain their existing position, all the while trying to avoid collisions with each other and the surrounding land masses. This may not only be inefficient but also risky, since in a dynamic marine environment it may be a challenge to maintain a position of a vessel because of forces due to winds, ocean waves, and wakes generated by other moving vessels.
On the other hand, if the USV 102 breaches the COLREGS with respect to CV1 104a and CV3 104c, the intersection of the south 106c and south east 106b channels becomes free for CV2 104b to pass. The USV 102 will, however, need to evaluate the collision risk with the vessels (e.g., CV4 104d) from the west 106d and north east 106a channels. Although the USV 102 may have the right of way with respect to the vessels 104d from the west channel 106d, the land mass separating the west 106d and south 106c channels may limit visibility so that vessel 104d might not see the USV 102.
As this example illustrates, safe navigation in a highly dense and dynamic environment is a challenging problem. Existing local trajectory planners, which have a limited number of “look-ahead” steps, have been unable to adequately address this problem. While traditional, lattice-based, deliberative planners employ multi-step look-ahead search capability, they require a significant amount of computation to find a global trajectory that optimizes a given performance metric and are thus computationally expensive. As a result, they are unable to achieve the high re-planning rates necessary for safely operating a USV in a congested environment.
Embodiments of the disclosed subject matter may address the above-mentioned problems and limitations, among other things.