Topological path planning for Information Gathering in Alpine Environments

Abstract

This thesis is about implementing a path planner for a drone that has to find and map released avalanches. The drone has a limited range and should return to the starting point at the end of its flight. By data from the SLF, there is knowledge about where avalanches could be, but whether there actually is one is only known when arriving there. Therefore a policy which depends on the observations is wanted. Several approaches are used to create such a policy. Besides a greedy planner and a simple MCTS approach, a new variant of MCTS is proposed, which is given the name double-tree MCTS. In its MCTS simulation step, it does not randomly sample actions, but goes up a branch of the tree, thus leading back to the starting point. The data of the SLF for a typical problem size contains more than 6’000 areas, where avalanches could be. Therefore several measures are tried to reduce the complexity of the problem. Prioritizing adjacent areas in MCTS turned out to give better results and grouping adjacent areas allowed to reduce the number of locations which have to be considered. With realistic parameters, the greedy planner outperformed both MCTS variants in every aspect. If the cost to map an avalanche was set much higher, the simple MCTS earned more average reward than the greedy planner and double-tree MCTS. Double-tree MCTS performed worse than hoped. It needed more computation time than the other approaches and gained less reward on average.