"Applications and Implementations of Zero Knowledge Algorithms Using Probabilistic Bounds"
Committee Members: Dr. Carrick Detweiler (Advisor), Dr. Brittany Duncan, Dr. Vinod Variyam, and Dr. Carl Nelson
Thursday, January 10, 2019, 11:00 a.m.
112 Schorr Center
Abstract: Many problems require full a priori knowledge before solving them. While collecting some data is costly under certain circumstances, it could be practically impossible in others. The need to still provide solutions to such problems is a challenge in the absence of all the required a priori data. This coupled with the limited computation power of a robot in the field renders some problems infeasible to solve. This also limits the application and scalability of some solutions. In this dissertation, we derive models and probabilistic bounds that we utilize in algorithms to solve problems in the absence of full a priori input data.
In this dissertation, we address two problems and expand one of them further. The first problem is charging a Wireless Rechargeable Sensor Network (WRSN) in the absence of knowing the power levels of its sensor nodes. We later expand this problem to a larger WRSN, in which a single UAV cannot charge, charging it with multi-UAV charging units. We also implement the no knowledge solution on a UAV and test it in the field. Our field experiments demonstrate the solutions ability to overcome practical problems, such as efficiency variation and drops. We apply the approach to both multi-UAV solutions where there is a lack of communication between the units or the existence of communication. The drop in performance due to lack of communication is not significant. Our second application is an underwater temperature gradient-following robot. In this case, a robot with limited power and mobility needs to follow a temperature gradient while collecting the temperature readings. We assess all our solutions against an optimal full knowledge algorithm for the same problem. Our results show that our no knowledge charging solution performs on average at 90% of what an optimal full a priori knowledge solution can deliver. While an efficiency compensating charging solution achieves on average 72% of an optimal full efficiency full knowledge solution. As for multi-UAV solutions, our no knowledge multi-UAV charging with communication performs at 92.3% on average. Our no knowledge no communication multi-UAV solution performs at 87.5% of an optimal full knowledge solution. Finally, the temperature gradient following solution performs on average at 87.3% of its optimal full a priori knowledge counterpart. A single instance evaluation, of the temperature gradient following, over a real-world dataset, resulted in 93.6% near optimal results.