Winning paper describes a revolutionary approach to mapping
Students, researchers and professionals from around the world meet biennially for the Institute of Electrical and Electronics Engineers (IEEE) Symposium Series on Computational Intelligence to showcase and confer over the state of the art in computer logic and artificial intelligence.
At this year’s symposium in Singapore, two University of Missouri researchers were distinguished with the conference’s “Best overall paper” award for their work in scene matching fuzzy descriptions with satellite imagery.
“The idea was that a person walking around in an unknown location could describe their environment using their own sort of spatial reasoning,” said Andrew Buck, illustrating the kind of mapping approach described in his winning paper.
Buck is a doctoral student in electrical and computer engineering. He coauthored and presented the paper at the conference with James Keller, Curators’ Professor and the R.L. Tatum professor of electrical and computer engineering.
“Everybody kind of has their own interpretation of their environment,” Buck said. “It’s a fuzzy map, so you might know that the road is next to the river, or the city that I’m trying to get to is far up in the north and a little to the west, so it’s these vague spatial ideas that we want to see if you can sketch into a mental map to align yourself with the real world.”
Sketching out these fuzzy maps would potentially make navigation easier in two ways: by identifying an unfamiliar location in which you might presently be and also identifying a location of which you can only recall hazy details.
“Somebody could describe their environment and say, ‘I see a building on my right, and there’s a parking lot behind me and to the left,’ or ‘I see a person walking toward the intersection,’” Buck said. “Using their spatial knowledge, they could use this to build a sketch, a kind of mental map of what they envision their environment to be.”
Buck’s research was initiated by a project called Text-to-Sketch started by a former engineering student in 2009 with a grant from the National Geospatial Intelligence Agency. The idea is that a person could describe their environment using common spatial reasoning and generate a digital sketch — a representation of one’s own mental map — to precisely depict perceptions of their environment.
“I kind of picked up on that and asked, once you have a sketch of objects in your mind, could you match that to satellite imagery — real data — to find out where your sketch matches up to an actual map?” Buck said.
The product Buck and Keller are after is called a conflation, an overlaying of two sources of data — two maps combined into one.
Computationally, the task of finding all the different possible interpretations of fuzzy data is difficult. Orientation, distance and exactly what is meant by “over there” or “to the left of” are highly variable. The permutations can become overwhelming in a brute force approach, making reliable results difficult to obtain under reasonable time constraints.
As described in the paper, which will be published in the Proceedings of the IEEE in the coming months, Buck had to first tackle the problem by finding a way to quantify closeness and proximity to get a definite sense of one’s position relative to other objects.
A memetic algorithm — also called an evolutionary algorithm — is rooted in the theory of evolution. Instead of attempting to find one solution, Buck’s algorithm starts by spawning a population of random solutions, which over time, evolve, cooperate and compete to find the best solutions to a given problem, in this case, finding mapped locations that most closely match descriptions provided in human language.
“You have the deterministic search method, and the evolutionary approach. This paper was ultimately the fusion of both,” Keller said. “Using this graph search thing, which could be computationally expensive, but uses it locally as a way to refine the genetic algorithm.”
Buck is applying this strategy to another application as well — mapping human movements for a National Geospatial Intelligence Agency historical survey on human geography.
“We’re trying to understand human movement under various conditions and aggregations and how they move through the environment,” Buck said. “So I’m trying to apply some of the spatial knowledge into that project.”