Calculating Horizons with Perspective Projection

Overview

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 (1)

• Society of Exploration Geophysicists: First Award of $500 $500

Competition history

• ISEF 2015 Category not listed · Entry SOFT056T

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.