In this paper, a novel Voronoi-Visibility (VV) path planning algorithm, which integrates the merits of a Voronoi diagram and a Visibility graph, is proposed for solving the Unmanned Surface Vehicle (USV) path planning problem. The VM (Voronoi shortest path refined by Minimising the number of waypoints) algorithm was applied for performance comparison. The VV and VM algorithms were compared in ten Singapore Strait missions and five Croatian missions. To test the computational time, a high-resolution, large spatial dataset was used. It was demonstrated that the proposed algorithm not only improved the quality of the Voronoi shortest path but also maintained the computational efficiency of the Voronoi diagram in dealing with different geographical scenarios, while also keeping the USV at a configurable clearance distance c from coastlines. Quantitative results were generated by comparing the Voronoi, VM and VV algorithms in 2,000 randomly generated missions using the Singapore dataset.

The problem of incremental terrain acquisition is addressed in this paper. Through a systematic planning of movements in an unknown terrain filled with polygonal obstacles, a sensor-based robot is shown to be able to incrementally build the entire terrain model; the model will be described in terms of visibility graph and visibility window. The terrain model is built area by area without any overlapping between explored areas. As a consequence, the terrain is obtained as a tessellation of disjoint star polygons. And the adjacency relations between star polygons are represented by a star polygon adjacency graph (SPAG graph). The incremental exploration process consists of two basic tasks: local exploration and exploration merging. Useful lemmas are derived for these two tasks and, then, the algorithms for the tasks are given. Examples are used to illustrate the algorithms. Two strategies for planning robot movements in the unknown terrain environment are suggested and compared. They are the depth-first search and the breadth-first search applied to the SPAG graph. Finally, the performance evaluation of the method and comparison with some existing methods are presented.

This paper presents a novel time-optimal motion planning strategy for a mobile robot with kinematic constraints. The method works in environments in presence of obstacles, without needing to generate the configuration space for the robot. Further, it derives a minimum time first derivative smooth path, as opposed to a minimum distance path which is commonly given by various present solution techniques. The problem is solved in three stages: (i) A reduced visibility graph for a point object is obtained. (ii) The reduced visibility graph is converted into a feasible reduced visibility graph accounting for the size and kinematic constraints of the robot. (iii) The A* algorithm is used to search the feasible reduced visibility graph with the cost function being the time of travel, to obtain a safe, time-optimal, smooth path. The algorithm runs in polynomial time. The method has been tested in computer simulations and test results are presented