March 4, 2020
With a speaker and four microphones, drones can echolocate like bats
WEST LAFAYETTE, Ind. — Similarly to how bats use echolocation to orient themselves with their surroundings, mathematicians have found that the same can be done with microphones and a speaker on a drone with the help of algebra and geometry.
This signal processing research has potential applications for people, underwater vehicles and even cars, said Mireille “Mimi” Boutin, a Purdue University associate professor of mathematics and electrical and computer engineering.
Boutin and Gregor Kemper, a professor of algorithmic algebra in the Department of Mathematics at the Technical University of Munich, have worked to reconstruct the wall configuration of rooms by using echoes picked up by microphones on the drone.
When a microphone hears an echo, the time difference between the moment the sound was produced and the time it was heard is recorded. That time difference shows the distance traveled by the sound after bouncing on a wall.
The challenge is to determine which distance corresponds to which wall, a process called echosorting. Sorting the echoes accurately ensures that all walls that are heard are truly there. This way, the algorithm does not produce “ghost” walls.
This research is directly related to two complementary problems in engineering: localization (determining where you are in an environment) and mapping (determining the shape of your environment).
The research done by Boutin and Kemper proves that it’s possible for a minimal setup of four microphones arranged in a non-planar shape, along with just a loudspeaker emitting one signal, to reconstruct a room. Their work is published in the SIAM Journal on Applied Algebra and Geometry.
The next steps will be to consider other scenarios, such as when the movement of the drone is restricted, or when the drone listens to the echoes of consecutive sounds as it is moving.
Practically, this echolocation research could be applied in numerous ways. Such a device could be carried by a person, affixed to a car, or even used underwater. Having more signal input would prevent solely relying on one type of input, like car backup cameras, and improve the chances that objects could be detected more accurately and in a wider variety of conditions.
“Many engineering applications require a lot of math, and sometimes you need to use tools from areas of mathematics that are considered abstract – in this case, methods from commutative algebra,” Boutin said.
“It’s considered a very abstract part of mathematics, but it applies to a very practical engineering problems. This shows just how unclear the boundary between applied and abstract math can be, and that engineering is truly a multidisciplinary discipline.”
About Purdue University
Purdue University is a top public research institution developing practical solutions to today’s toughest challenges. Ranked the No. 6 Most Innovative University in the United States by U.S. News & World Report, Purdue delivers world-changing research and out-of-this-world discovery. Committed to hands-on and online, real-world learning, Purdue offers a transformative education to all. Committed to affordability and accessibility, Purdue has frozen tuition and most fees at 2012-13 levels, enabling more students than ever to graduate debt-free. See how Purdue never stops in the persistent pursuit of the next giant leap at purdue.edu.
Media Contact: Kayla Wiles, 765-494-2432, email@example.com
Writer: Kelsey Schnieders Lefever
Source: Mireille “Mimi” Boutin, firstname.lastname@example.org
Note to Journalists: For a copy of the paper, please contact Kayla Wiles, Purdue News Service, at email@example.com or 765-494-2432. Photos of Mireille Boutin doing calculations for this work are available in a Google Drive folder at https://purdue.university/2TG4EoW.>
A Drone Can Hear the Shape of a Room
Mireille Boutin1, Gregor Kemper2
1Purdue University, West Lafayette, IN, USA
2Technical University of Munich, Garching, Germany
DOI: 10.1137/19M1248534We show that one can reconstruct the shape of a room with planar walls from the first-order echoes received by four nonplanar microphones placed on a drone with generic position and orientation. Both the cases where the source is located in the room and on the drone are considered. If the microphone positions are picked at random, then with probability one, the location of any wall is correctly reconstructed as long as it is heard by four microphones. Our algorithm uses a simple echo sorting criterion to recover the wall assignments for the echoes. We prove that if the position and orientation of the drone on which the microphones are mounted do not lie on a certain set of dimension at most 5 in the six-dimensional space of all drone positions and orientations, then the wall assignment obtained through our echo sorting criterion must be the right one and thus the reconstruction obtained through our algorithm is correct. Our proof uses methods from computational commutative algebra.