Flying robots are being used for a variety of tasks. For example, after the 2011 earthquake in Sendai, researchers used a Kinect-equipped quadrotor to autonomously carry out search and rescue missions in collapsed buildings.
The environments in which these robots operate share several important characteristics. First, they are dynamic, because they contain moving obstacles that can pose a threat to robots. They are also unstructured, because they are complex and unpredictable. Finally, they are unknown, because their layout and contents is not known a priori. Thus, it is particularly challenging but equally important to quickly evade moving obstacles (threats). In fact, while applications like autonomous search and rescue and emergency response have the potential to save millions of lives, a significant obstacle to true autonomy and scalability is the lack of robust and practical methods of threat evasion.
Noting the limitations of approaches presented by previous work, I aimed to create a simpler, faster, and more practical method of onboard threat evasion, inspired by the way fruit flies detect and respond to threats. After reviewing relevant work in the fields of biology and robotics, I designed a computationally and physically lightweight sensor module, modeled after the fruit fly's rudimentary but fast visual system. I also created novel algorithms to model the trajectory of and escape from approaching threats by mimicking fruit fly escape behaviors, and verified the effectiveness of these algorithms both experimentally and through a still image comparison to fruit fly escape.
I am a freshman at Fox Chapel Area High School in Pittsburgh, Pennsylvania. I have been fascinated with computer science and robotics for as long as I can remember, and can often be found at my desk, surrounded by microcontrollers, wires, sensors, and servo motors. My passion for using my interests and creativity to solve real problems has driven me to create many tools for students, including iDMS, Classroom and CiteIt.
I have been participating in science fairs since sixth grade, and have been fortunate to have won a first place each year. Last year, I was selected as one of thirty national finalists in the Broadcom MASTERS science fair for my project on digitally recreating smells, and ultimately won the first place award in engineering. I also had the incredible opportunity to meet President Obama, and MIT's Lincoln Laboratory named a minor planet after each finalist.
My idols include Alan Turing, whose fundamental work continues to shape the field of computer science, and Elon Musk, who applies his knowledge and vision to solving large-scale problems.
In the future, I would like to become a researcher or entrepreneur, helping to use technology to solve pressing world problems, from cancer and hunger to the global energy crisis. Winning the Google Science Fair would bring me one step closer to this goal, as it would give me the opportunity to meet and learn from some of the most brilliant innovators in the world.
Question / Proposal
Given the dynamic, unstructured, and unknown nature of the environments in which both flying robots and flying organisms must operate, can a novel biologically-inspired approach be used to create a simpler, faster, and more practical method of onboard threat evasion in a flying robot?
Fruit flies, in particular, are ideal models for lightweight threat evasion. First, they are really good at quickly evading moving threats, such as swatters. In fact, the typical fruit fly escape sequence, depicted below, takes only 288 milliseconds, which is less than the duration of a human eye blink. Moreover, fruit flies accomplish this escape despite their rudimentary visual system, which is equivalent to a 26 by 26 pixel camera, and simple brain, which consists of only 100,000 neurons (giving it one-millionth of the complexity of the human brain). Thus, I hypothesize that a computationally and physically lightweight sensor module inspired by the fruit fly's rudimentary visual system, combined with algorithms to escape from approaching threats by mimicking fruit fly escape behaviors, can be used to demonstrate a simpler, faster, and more practical method of onboard threat evasion in a quadrotor.
Figure 1: A typical fruit fly escape sequence. The images, captured with a high-speed video camera, are from Card and Dickinson (2008).
Quadrotors are agile flying robots that are extremely popular in robotics research. They consist of four rotors controlling six degrees of freedom (x, y, and z position, along with roll, pitch, and yaw rotation). As shown below, they move vertically by increasing rotor speed and laterally by rotating about one or more axes.
Figure 1: Basic quadrotor controls. This image is from Bawek (2012).
Previous work presents two approaches to the general problem of obstacle avoidance in flying robots:
- Using complex onboard sensors, often depth cameras and laser scanners, map and avoid obstacles. While this approach has been successfully demonstrated in unstructured and unknown environments with stationary obstacles like tables and walls, it is particularly ineffective in dynamic environments because the computationally-intensive algorithms on which it relies create considerable latency.
- Using an array of sophisticated external sensors, often a motion capture system, precisely track the position of obstacles. While this approach has been used to demonstrate impressive results even in dynamic environments, it requires each sensor to be statically mounted (e.g., on the ceiling of a large laboratory space), and each obstacle to be identified with an optical marker. Thus, it is infeasible in unstructured and unknown environments.
Michael et al. (2012) describe a search and rescue mission carried out by a flying robot after the 2011 earthquake in Sendai, Japan. The quadrotor used to explore the collapsed building in which the mission took place used both a Microsoft Kinect, which includes a depth camera, and a laser scanner (i.e., the first approach described above) to avoid stationary obstacles. However, the authors note at the end of their study that "the environment was modified prior to our entry in that... structural reinforcements were put into place to prevent further building collapse... [L]oose wall and ceiling materials were of concern for both the ground and aerial robots due to the possibility that such material could damage the vehicles," emphasizing that, while applications like autonomous search and rescue and emergency response have the potential to save millions of lives, robust and practical methods of onboard threat evasion are needed for true autonomy and scalability.
Card and Dickinson (2008) have studied fruit fly escape behavior extensively. They found that fruit flies start planning an escape after noticing an approaching threat, even in situations in which they ultimately choose not to jump. They also showed that fruit flies escape at an angle roughly halfway between directly away from a threat and directly forward, suggesting that their escape is naturally forward-biased. Moreover, they noted that fruit flies perform calculations and postural adjustments after noticing an approaching threat, and can complete their escape by jumping forward and using their wings to manipulate their escape direction when pre-flight movements alone aren't sufficient.
A final area of research was focused on choosing a development platform on which to implement my sensing solution and escape algorithms. In the end, I chose the Crazyflie quadrotor, an extremely small flying robot with a hardware expansion header and open-source, modular firmware.
Method / Testing and Redesign
1. Hardware Design
Drawing inspiration from the fruit fly's visual system, I designed a lightweight sensor module to estimate the position and orientation of an approaching threat.
The sensor module was designed around two constraints. First, the fruit fly's visual system is so effective because it's rudimentary and thus requires minimal computational overhead. In contrast, I found that even the most rudimentary cameras available today create too much data to process in real-time. Second, because of the limited payload capacity of the quadrotor that I used, the sensor module needed to be lightweight.
To satisfy these constraints, I decided to use two infrared distance sensors, directly interfaced with the quadrotor's microcontroller. They’re extremely light (4 grams each), draw little current, and have a simple analog output that maps to distance. Although using more sensors would have been ideal (indeed, an initial design included four sensors connected to a separate microcontroller with the hope of avoiding direct modification to the quadrotor), lift measurements indicated that this was impossible. The completed sensor module, by itself and attached to the quadrotor, is shown below.
Managing power consumption was also challenging. I mapped the analog output of the distance sensors to vertical distance across three different input voltages. Based on the results of this calibration experiment, I decided to use the 5 volt step-up regulator labeled above.
2. Algorithm Implementation
Next, I created novel algorithms, described below, to model the trajectory of and escape from approaching threats by mimicking fruit fly escape behaviors. I initially implemented these algorithms in Python on a computer that could wirelessly command the quadrotor, but later added them directly to the quadrotor's firmware to minimize latency.
Identify threats. When the distance at either sensor drops below the maximum sensor range, assume that there's a threat.
(Initial algorithms escaped immediately after identifying threats, but reacted identically to quickly-moving threats and objects overhead that eventually moved away. Thus, it became necessary to use a model of a threat's trajectory to decide when to escape. I evaluated several algorithms using Matlab and previously-collected sensor data, and ultimately chose the one described here.)
Model threats. Incorporating new measurements at 25 Hz, recursively model the threat's trajectory. Assume that the acceleration at any given point on the threat is constant, and thus model distances at each sensor with a second-order polynomial of the form
where d is the distance at time t. Find coefficients a, b, and c with
Determine when to escape. After each update, determine whether to escape. Predict the time at which the threat will reach each sensor by finding the relevant root of each polynomial (the smallest root that's greater than the current time). Begin to escape when the difference between either prediction and the current time is less than or equal to the time required to safely escape (determined experimentally).
Escape. Using the segmented algorithm described below, escape from the threat. Experimental validation and a more detailed comparison to fruit fly escape are presented in Results.
To test the effectiveness of the escape algorithm that I had developed, I simulated many different scenarios, using a 15 by 30 centimeter plywood sheet approaching from different directions and at different speeds as a threat. Starting from a stationary position, the quadrotor escaped with a success rate of 100% across twenty formal attempts. A slow motion video of one of these escape attempts is shown below.
Video 1: An escape attempt (one-fourth of original speed).
I also collected and analyzed extensive telemetry data from each escape attempt. Annotated graphs of this data for one attempt are shown below.
Figure 1: Threat distance above each sensor. The angle of escape (α) is extrapolated from these distances. In this case, if the threat continues the trajectory depicted, it will not reach the right sensor (a second-order polynomial representing distances above the right sensor would not have any real roots) but will reach the left sensor (conversely, a second-order polynomial representing distances above the right sensor would have a real, relevant root). Thus, the quadrotor escapes in the right direction, away from the threat.
Figure 2: Altitude measurements throughout escape.
Figure 3: Target (top) and actual (bottom) roll and pitch values throughout escape.
Also, because the escape algorithm was closely based on fruit fly behaviors, I extracted frames from a video of an escape attempt and performed a still image comparison to a fruit fly's escape, shown below.
Figure 4: A still image comparison between a fruit fly's escape (top) and an escape attempt (bottom). The images of fruit fly escape are from Card and Dickinson (2008). Both the fruit fly and the quadrotor begin in a stationary position (1), start to make calculations and adjustments (2), begin to move laterally away from the threat (3), and finish the final segment of their escape by moving vertically (4 and 5).
Conclusion / Report
In this project, I demonstrated a biologically-inspired solution to the problem of threat evasion in flying robots. I created a simpler, faster, and more practical method of threat evasion in a quadrotor, inspired by the way fruit flies detect and respond to threats. The key contributions of my work are the lightweight sensing solution that I designed to estimate the position of an approaching threat, and the threat modeling and escape algorithms that I created. These algorithms were highly effective, even with limited knowledge of the threat and little processing power. The quadrotor escaped from threats approaching from different directions and at different speeds with a success rate of 100% across twenty different attempts. Thus, these results, along with a still image comparison between an escape attempt and a fruit fly’s escape, support my hypothesis.
Although I succeeded in meeting the goal of this project, the development platform on which I implemented my proof-of-concept did impose a few limitations that are worth mentioning. Several factors made the Crazyflie an attractive choice: it was based on open-source and extensible hardware and software, and was also small and agile, robust, safe to test at home, and relatively inexpensive. However, the downside was a limited payload capacity. This limited the number of sensors that I could use, and, by extension, the precision of my sensor module.
I envision several areas of future work for this project. First, the sensor module could be modified to more precisely detect threats. As mentioned previously, additional sensors would give the escape algorithm a more precise understanding of the orientation of an approaching threat. Moreover, these sensors could be angled to more effectively detect threats approaching from the side. Second, escape could be optimized with an artificial neural network. For example, the escape algorithm could recognize and learn from failed escape attempts, as is done by fruit flies, to be more effective in similar situations in the future. Finally, on a larger scale, my escape algorithm could be integrated into existing pathfinding and navigation algorithms to build a truly autonomous and scalable method of mapping and exploring complex environments. In general, the growing use of flying robots in search and rescue, emergency response, and military applications make my project particularly relevant. I plan to pursue this direction during this summer as part of an internship at the Field Robotics Center at Carnegie Mellon University.
Bibliography, References and Acknowledgements
Arizona Department of Health Services. Quadratic Least Square Regression. (http://www.azdhs.gov/lab/documents/license/resources/calibration-training/12-quadratic-least-squares-regression-calib.pdf)
Daniel Mellinger, Nathan Michael, Michael Shomin, and Vijay Kumar. Recent advances in quadrotor capabilities. In Proc. of the International Conference on Robotics and Automation, Shanghai, China, 2011. IEEE. (http://www.deepdyve.com/lp/institute-of-electrical-and-electronics-engineers/recent-advances-in-quadrotor-capabilities-SfzvjFpXLu)
Dean Bawek. Design and implementation of a control system for a quadrotor MAV. Master's thesis, University of Maryland, 2012. (http://drum.lib.umd.edu/bitstream/1903/12814/1/Bawek_umd_0117N_13233.pdf)
Gwyneth Card and Michael Dickinson. Visually mediated motor planning in the escape response of Drosophila. Current Biology, 18(17):1300 – 1307, 2008. (http://www.cell.com/current-biology/pdf/S0960-9822(08)01048-8.pdf)
Joseph Ayers, Joel Davis, and Alan Rudolph. Neurotechnology for biomimetic robots. MIT Press, 2002. (http://books.google.com/books?id=evhEjXkjgVkC)
Michael Dickinson. How a fly flies. TEDxCaltech, 2013. (http://www.ted.com/talks/michael_dickinson_how_a_fly_flies)
Nathan Michael, Daniel Mellinger, Quentin Lindsey, and Vijay Kumar. The GRASP multiple micro-UAV testbed. Robotics & Automation Magazine, IEEE, 17(3):56 – 65, 2010. (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.169.1687&rep=rep1&type=pdf)
Nathan Michael, Shaojie Shen, Kartik Mohta, Yash Mulgaonkar, Vijay Kumar, et al. Collaborative mapping of an earthquake-damaged building via ground and aerial robots. Journal of Field Robotics, 29(5):832 – 841, 2012. (https://fling.seas.upenn.edu/~yashm/website/files/JFR2012.pdf)
Shaojie Shen, Nathan Michael, and Vijay Kumar. Autonomous multi-floor indoor navigation with a computationally constrained MAV. In Proc. of the International Conference on Robotics and Automation, Shanghai, China, 2011. IEEE. (http://www.icrobotics.co.uk/wiki/images/f/f1/Autonomous_Multi-Floor_Indoor_Navigation_with_a_Computationally_Constrained_MAV.pdf)
Shaojie Shen, Yash Mulgaonkar, Nathan Michael, and Vijay Kumar. Vision-based state estimation and trajectory control towards high-speed flight with a quadrotor. In Robotics: Science and Systems, 2013. (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7992&rep=rep1&type=pdf)
Tekla Perry. Matternet's package delivery drones. IEEE Spectrum, 2013. (http://spectrum.ieee.org/podcast/aerospace/aviation/matternets-package-delivery-drones)
I am grateful to Mr. Howard Havlicsek, a local electrical engineer who gave me advice and allowed me to use his soldering equipment in the construction of my sensor module. I would also like to thank my family for their help, support, and encouragement, and for allowing me to fly my quadrotor around the house while testing often buggy escape algorithms :)