Abstract Search

ISEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

Calculating Horizons with Perspective Projection

Booth Id:
SOFT056T

Category:
Systems Software

Year:
2015

Finalist Names:
Hamilton, Justin
Schade, Ben

Abstract:
Building off the past few years of research in robotic search and rescue, this year, we write an algorithm that calculates the visible horizon and peaks of hills from any location and direction on a height map of any size. The direct border between sky and land is denoted as the fundamental horizon, while the peaks of visible hills are defined as secondary horizons. In robotic navigation, there are many obstacles to avoid, ranging from a tree or rock, to a mountain or ravine. Large obstacles require much more computational planning to avoid than small ones. In order to solve this issue efficiently, we create an algorithm to portray the horizon the robot observes based on a massive data set, which allows the robot to ignore data-points that are irrelevant to that horizon. Disregarding irrelevant data is useful, since there is less information to process when making decisions concerning navigation. This method is a significant improvement in efficiency compared to others that include image processing or analyzing sensor input, and the algorithm will consistently return a mathematically rigorous result. In order to analyze a height map, with upwards of hundreds of thousands of data-points, the computational power required can become overly intensive, especially when the robot is moving. Yet, the two portions of our algorithm are capable of rendering horizons in real time, with the fundamental horizon generator having an average complexity of O(n) and the secondary horizon generator having an average case of O(n^2). We have designed an efficient algorithm that allows robots to see the world as humans do without utilizing a single sensor or immense computational power.

Awards Won:
Society of Exploration Geophysicists: First Award of $500