Drones can determine the shape of a room by listening to echos from the walls, according to mathematicians from Purdue University and Technische Universitat Munchen.
Mireille Boutin (Perdue) and Gregor Kemper (Munich), with few exceptions, can theoretically get the shape of a room providing the drone is carrying four microphones that all hear echos from a loudspeaker either on the drone or sitting somewhere in the room. While the walls need to be flat, the room does not have to be rectangular, and the walls can be angled.
The loudspeaker emits an impulse, and the timings of the first-order echos are analysed – those that bounce on one wall only between speaker and microphone.
Traditional scanning sonar is not involved, as the microphones and speaker are omnidirectional and there only needs to be one impulse.
Assuming first order echos an be separated by those that have bounced of more than one wall, and according to the team there are ways of doing this not covered by this research, then sorting through all the recorded time delays to find which bounce came from which wall is the first mathematical hurdle.
For any give wall, this step relies on a reflection from that wall to four microphones providing a similar set of timings to a situation where a speaker was placed outside the room behind that wall, and the wall was taken away.
For each wall there will be (usually) only one virtual speaker position that meets all of the timings, and from the geometry of the microphones and virtual speaker, the position of four points on the wall can be found. Providing the microphones are not mounted in a single plane, and some other caveats, the four points will not be in a straight line and will therefore identify the plane of the wall.
The criterion used so sort out all the echos “is a vanishing Cayley-Menger determinant involving the pairwise distances between the five-point configuration formed by the four microphones and the mirror image of the source through one wall”, according to ‘A drone can hear the shape of a room’, a paper on the work due to be published in the Society for Industrial and Applied Mathematics (SIAM) journal ‘Applied algebra and geometry’.
“The echo sorting technique uses a polynomial as a screening test and discovers whether the four distances lie on the zero set of a certain polynomial in four variables,” According to the researchers. “A non-zero value reveals that the distances cannot bounce from the same wall. Alternatively, if the polynomial is equal to zero, the distances could possibly come from the same wall.”
And it works, as according to the paper: “The algorithm is guaranteed to detect every wall from which a first-order echo is heard by all microphones.”
Unleashed on certain combinations of real walls, this technique can identify what have been dubbed ‘ghost walls’ – walls that would meet the timing criteria if they did exist. However, moving the drone a little can mitigate this. “Our work indicates that these six degrees of freedom are sufficient to almost always detect the walls,” said Munich’s Kemper.
Having show that the maths works with theoretic clean signals, the next step is to cope with noisy measurement. “This task is by no means straightforward” according to the researchers.
Source: electronicsweekly
