Dissertation Defense Candidate: Yang Song Advisor: Dr. Jason O’Kane Date: Friday, November 13, 2015 Time: 1:00pm Location: Swearingen, 3A00 (Dean’s Conference Room) Abstract This dissertation first presents our geometric-­based planning algorithm for robots to describe and reason about uncertainty, termed the `"constrained geometric approximation approach" Previous work delivered computationally expensive methods to represent a robot's knowledge of its states and uncertainty explicitly, using an information state in the information space. In contrast, our approach is computationally inexpensive. Specifically, this approximation method uses simple geometric data structures which are suitable for the robots with extreme limitations in both sensing and computation. We provided simulations of sensor ­based navigation tasks, along with experimental results. We conclude that the robot can achieve similar success rate at a small fraction of the computational cost, by maintaining simple representations of the incomplete information. The dissertation also contributes two decentralized algorithms for the multi-­robot lattice pattern formation problem. Prior work solved such problems by constituting only particular lattice patterns. Our approaches enable robots to form arbitrary lattice patterns without global knowledge of the system. Both of the formation algorithms feature in representing the lattice as a directed graph, in which edges show the desired rigid body transformations between the robot and its neighbors. Another common feature of the two algorithms is that robots organize themselves using tree structures. The first formation algorithm enables each robot to perform distributed task assignment using only local information. The experimental results demonstrate that the algorithm executes efficiently and scales reasonably well as the number of robots increases. Moreover, the algorithm is stateless and is robust to system failures. We analyze the pitfalls of the proposed task-assignment-­based formation algorithm. According to the analysis, we have designed another formation algorithm that has new features including: The bounded execution time, a novel motion strategy that guarantees the network connectivity, and the improved final lattice formation quality. Furthermore, we have proved the correctness of the new algorithm and conducted groups of experiments to compare the timing performance and the formation qualities of both formation algorithms.