| Abstract: |  This thesis deals with route planning in the areas affected by maritime piracy. The goal of this thesis is to create a route planner that minimizes both the route length and the pirates attack risk. The work builds on previous work, the AgentC project, which uses A* to plan on a static risk grid. First, I extend this risk model in temporal dimension, i.e., I consider the time of the day when constructing the risk model. Second, I design a route planner is based on RRT*, an algorithm for optimal motion planning in continuous spaces. This algorithm cannot be applied of the shelf due to inherent problems with natural choke points, such as straits and bays. I solve this issue by discretizing the space using a Quad tree and utilize A* to plan on a graph represented by the leaves of the Quad tree. This suboptimal plan serves as an input into the RRT* algorithm, which further refines the plan. The result is a anytime, asymptotically optimal, continuous space planner. Using proposed risk map, the planner is able to find optimal shipping routes through the piracy affected waters.
|
|---|