Tag Archives: navigation

Our brains don’t pick the shortest route between two points — they pick ‘the pointiest’ one

Research from (Massachusetts Institute of Technology) seems to suggest that our brains aren’t the most effective navigation tools out there. According to the findings, people navigating cities tend not to follow as straight a trajectory as possible, which would be the shortest path, but tend to take the one that points most towards their destination — even if they end up walking a longer distance.

Image via Pixabay.

The team calls this the “pointiest path” approach. In technical terms, it is known as vector-based navigation. Animals, from the simplest to the most complex, have also shown in various experiments that they employ the same strategy. The authors believe that animal brains evolved to use vector-based navigation because, even though it isn’t the most effective approach, it is much easier to implement computationally — saving time and energy.

A general direction

“There appears to be a tradeoff that allows computational power in our brain to be used for other things—30,000 years ago, to avoid a lion, or now, to avoid a perilous SUV,” says Carlo Ratti, a professor of urban technologies in MIT’s Department of Urban Studies and Planning and director of the Senseable City Laboratory.

“Vector-based navigation does not produce the shortest path, but it’s close enough to the shortest path, and it’s very simple to compute it.”

The findings are based on a dataset comprising the routes of over 14,000 people going about their daily lives in a city environment. These records were anonymized GPS signals from pedestrians in Boston and Cambridge, Massachusetts, and San Francisco, California, over a period of one year. All in all, they include over 550,000 paths.

The overwhelming majority of people didn’t use the shortest routes, judging from where they left and their destination. However, they did pick routes that minimized their angular derivation from the destination — they chose the routes that pointed towards where they were going the most.

“Instead of calculating minimal distances, we found that the most predictive model was not one that found the shortest path, but instead one that tried to minimize angular displacement—pointing directly toward the destination as much as possible, even if traveling at larger angles would actually be more efficient,” says Paolo Santi, a principal research scientist in the Senseable City Lab and at the Italian National Research Council, and a corresponding author of the paper. “We have proposed to call this the pointiest path.”

Pedestrians employed this navigation strategy both in Boston and Cambridge, which have a convoluted street layout, as well as in San Francisco, which has a highly organized, grid-style layout. In both cases, the team notes that pedestrians also tend to follow different routes when making a round trip between two points. Ratti explains that such an outcome would be expected if pedestrians made “decisions based on angle to destination” instead of judging distances only.

“You can’t have a detailed, distance-based map downloaded into the brain, so how else are you going to do it? The more natural thing might be useful information that’s more available to us from our experience,” Tenenbaum says. “Thinking in terms of points of reference, landmarks, and angles is a very natural way to build algorithms for mapping and navigating space based on what you learn from your own experience moving around in the world.”

While definitely fun, such findings may seem a bit inconsequential. The authors however believe that as we come to rely more heavily on computers such as our smartphones for everyday tasks, it is more important than ever to understand the way our own brains compute the world around us. This would allow us to design better software and improve our quality of life by tailoring our devices around the way our minds and brains work.

The paper “Vector-based pedestrian navigation in cities” has been published in the journal Nature Computational Science.

Sea turtles are amazing navigators — but they only use crude maps

: A Green Turtle that was returning to sea, the morning after she laid her eggs on Ascension Island. They lay on average 120 eggs in a clutch and may lay 6 clutches in a season. Credit: Wikimedia Commons.

Sea turtles are migratory species from the moment they are ready to come into this world. After they’ve hatched out of their nesting grounds on the beaches of Florida, Yucatan, or other eastern coasts of the Americas, they immediately embark on a frenzied race towards the sea.

On their journeys, these younglings can end up traveling more than 10,000 miles across the entire North Atlantic, before returning to their original breeding grounds.

Clearly, sea turtles are amazing navigators, likely using the earth’s geomagnetic field to pinpoint their position and orientate. However, don’t imagine that their internal GPS is very accurate.

According to a new study, sea turtles often miss their mark, sometimes by hundreds of miles. This can add thousands of extra miles to their migrations as they take less straightforward paths to their destination. So, instead of Google Maps, think of the sea turtle’s positioning system more like a very crude map — it’s far from perfect, but it gets the job done.

“By satellite tracking turtles travelling to small, isolated oceanic islands, we show that turtles do not arrive at their targets with pinpoint accuracy,” says Graeme Hays of Australia’s Deakin University.

“While their navigation is not perfect, we showed that turtles can make course corrections in the open ocean when they are heading off-route. These findings support the suggestion, from previous laboratory work, that turtles use a crude true navigation system in the open ocean, possibly using the earth’s geomagnetic field.”

Hays and colleagues attached satellite tags to 33 nesting green turtles (Chelonia mydas). Originally, the researchers wanted to find out more about the extent of the animals’ movements in order to identify key areas for conservation efforts.

But as the researchers tracked the turtles, they noticed that they were traveling to isolated islands and submerged banks — and they did so rather awkwardly.

The turtles were tracked from the moment they left their nesting beaches on the island of Diego Garcia in the Indian Ocean, from which they embark on a journey towards their foraging grounds across the western Indian Ocean.

According to the satellite data, 28 out of 33 turtles didn’t reorient themselves daily or at a fine scale. As a result, the turtle would often travel hundreds of miles out of their way before correcting their course. This confusion most often occurred in the open ocean.

So, instead of reaching their small island destination with pinpoint accuracy, the turtles more often than not overshot their targets or wasted time searching for their favorite remote islands during the final stages of their migration.

“We were surprised that turtles had such difficulties in finding their way to small targets,” Hays says. “Often they swam well off course and sometimes they spent many weeks searching for isolated islands.

“We were also surprised at the distance that some turtles migrated. Six tracked turtles travelled more than 4,000 kilometers to the east African coast, from Mozambique in the south, to as far north as Somalia. So, these turtles complete round-trip migrations of more than 8,000 kilometers to and from their nesting beaches in the Chagos Archipelago.”

Although this study shows that highly accurate turtle navigation is a myth, the findings do not subtract from their impressive migrating abilities. After all, this is the first study that showed that sea turtles are capable of reorienting themselves in the open ocean, which implies they actually have a mental map of some sort.

The study also has important applications for sea turtle conservation. Once their nesting season is done, turtles travel extensively across the open ocean. As such, conservation efforts have to be coordinated across large spatial scales, covering many countries.

In the future, the researchers would like to employ novel tag technology that will enable them to not only determine their location but also the turtles’ compass heading.

“Then we can directly assess how ocean currents carry turtles off-course and gain further insight into the mechanisms that allow turtles to complete such prodigious feats of navigation,” Hays says.

The findings were reported in the journal Current Biology.

Social bot.

MIT designs robot to be a good pedestrian and not bump into you on the sidewalk

Engineers at MIT are working on instilling robots with “socially aware” navigation, allowing them to observe humans’ code of pedestrian conduct.

Socially walking bot.

Image credits Chen et al., 2017.

Generally speaking, most pedestrians follow a set of unspoken social conventions when they go out and about our day. Things like don’t walk into other people; try to walk past instead of through groups; keep to the right of the sidewalk and pass on the left; avoid incoming obstacles and walk at a steady pace so other pedestrians can avoid a collision in turn.

Robots aren’t at that level of social finesse just yet. So a team of researchers from MIT is trying to program it into the bots so they can better integrate and function alongside humans in society — while keeping annoying bumps in foot traffic to a minimum. Led by Yu Fan Chen, a former MIT graduate student, they designed and build a small robot which relies on “socially aware navigation”. They tested the robot inside the sprawling hallways of MIT’s Stata Center in Cambridge, Mass., where it managed to successfully avoid collisions while keeping up with the average speed of pedestrians.

A walk in the campus

“Socially aware navigation is a central capability for mobile robots operating in environments that require frequent interactions with pedestrians,” says Yu Fan Chen.

“For instance, small robots could operate on sidewalks for package and food delivery. Similarly, personal mobility devices could transport people in large, crowded spaces, such as shopping malls, airports, and hospitals.”

Successfully going about in traffic, if you’re a robot, mostly revolves around four processes:

  • localization (knowing where you are),
  • perception (having a way to observe your surroundings),
  • motion planning (deciding on the best path to a given destination), and
  • control (the ability to actually move along that path.)

As far as localization, perception, and control are concerned, Chen’s team went with standard approaches: off-the-shelf sensors such as webcams, a depth sensor, and a high-resolution LIDAR sensor for perception, and open-source algorithms to map the bot’s environment and determine its position for localization. Control was handled by a standard ground vehicle drive — an electrical motor and wheels.

What the team wanted to innovate on was the planning step. Roboticists usually tackle this issue by using one of two approaches: having the bots calculate everybody’s trajectories and then deciding on which one to take (a trajectory-based model), or selecting a general route then adapting on the fly to avoid possible collisions (reactive-based model). However, they both have limitations.

“But this [trajectory-based approach] takes forever to compute. Your robot is just going to be parked, figuring out what to do next, and meanwhile the person’s already moved way past it before it decides ‘I should probably go to the right,'” says MIT graduate student and paper co-author Michael Everett. “So that approach is not very realistic, especially if you want to drive faster.”

On the other hand, reactive-based approaches don’t always deliver since people don’t walk exclusively in straight, predictable lines — they tend to weave and wander around. Because of their unpredictable environment, these bots end up either colliding with people or being pushed around so much they take way too long to reach their destination — although to be fair, the first one might make them more likable in a goofy sort of way.

“The knock on robots in real situations is that they might be too cautious or aggressive,” Everett adds. “People don’t find them to fit into the socially accepted rules, like giving people enough space or driving at acceptable speeds, and they get more in the way than they help.”

Virtual lessons

The team’s solution was to use reinforcement learning (a type of machine learning) to drill pedestrian etiquette into the robot. The advantage of this method was that the team can train the robot in a simulation, by-passing the cost in time and computing power (which is limited based on the robot’s frame) of training in real life. Once there, it can use what it learned to handle similar scenarios.

A probably-unintended side effect was how cute this thing was when going about its day:

They guided the robot to prefer certain paths based on the trajectories of other objects in their environment. They also encouraged behaviors that mirror how human pedestrians interact in this phase, such as having the robot pass people or groups on the right by penalizing it when it passed on the left. To enable it to make the most out of what it’s learned, the team enabled the robot to assess the state of its environment and adjust its trajectory every one-tenth of a second.

“We’re not planning an entire path to the goal — it doesn’t make sense to do that anymore, especially if you’re assuming the world is changing,” Everett says. “We just look at what we see, choose a velocity, do that for a tenth of a second, then look at the world again, choose another velocity, and go again. This way, we think our robot looks more natural, and is anticipating what people are doing.”

To test the outcome, the team instructed the robot to make its way through the halls of MIT’s Stata Building. This location was chosen since it’s quite busy with people doing everyday things, such as going/rushing to class, getting food, hanging out — in other words, it offers a wide range of motion patterns. It was able to autonomously drive for 20 minutes at a time, rolling along with pedestrian flow, usually keeping to the right of hallways (although it did pass people on the left on occasion), and successfully avoiding any collision.

Moving forward, the team plans to refine their social navigation algorithms by teaching robots how to better interact with crowds in a pedestrian setting — things such as “don’t move through people, don’t split people up, treat them as one mass.”

The team will be presenting their paper “Socially Aware Motion Planning with Deep Reinforcement Learning” at the IEEE Conference on Intelligent Robots and Systems in September. Until then, it can be read on the preprint server ArXiv.

Vikings might have actually used sunstones to navigate

Icelandic legends tell of Vikings using sunstones to navigate the ocean when clouds hid the sun and stars. Now, a new study suggests that Vikings might have actually used these minerals to navigate, making the legends a reality.

Vikings might have used sunstone to navigate the oceans when the sun and stars were hidden by clouds. Credit: ArniEin/Wikipedia/CC BY-SA 3.0
Vikings might have used sunstone to navigate the oceans when the sun and stars were hidden by clouds. Credit: ArniEin/Wikipedia/CC BY-SA 3.0

Modern sunstone is a type of crystal that exhibits a spangled appearance when viewed from different angles. In the new study, the researchers conducted numerous experiments to test the possibility that Vikings used the unique properties of these crystals to navigate their way across the ocean and found that they can be beneficial navigational aids when the skies are blanketed with clouds.

Viking history has been well documented, with researchers uncovering the details of their raids across Europe from the late 790s until 1066. However, further research has revealed their travels to the Middle East and North America, leading scientists to wonder exactly how they made their way across such vast stretches of ocean, especially during periods of time when they could not use the stars or sun for guidance.

Sunstones have been speculated as Viking navigational aids for some time. In addition to their presence in legends, a recent examination of a 2002 Viking shipwreck yielded a sunstone near other navigational instruments, fueling speculation that the mythology could be true.

In the current study, the team suggests a three step process for sunstone navigation: holding a sunstone to the sky to determine the direction of light from the sky, using this information to determine the direction of sunlight, and using a shadow stick to determine which direction is north. Previous research from the same team confirmed the accuracy of the first two steps, leaving the current study to examine the third step.

The researchers gathered 10 volunteers and asked them to determine the position of the sun in a virtual planetarium, where dots represented the results of using a sunstone. Over the course of 2,400 trials, 48 percent resulted in accurate readings within one degree. Furthermore, the team discovered that the sunstone was most accurate when the digital sun was closest to the horizon, meaning that the method is ideal for use at dawn and dusk when the sun is lowest in the sky.

Journal Reference: North error estimation based on solar elevation errors in the third step of sky-polarimetric Viking navigation. 27 July 2016. 10.1098/rspa.2016.0171

Pigeon Bermuda triangle explained

Birds may not be the smartest bunch out there, but man do they know how to navigate! Pigeons can get around towns and even  continents with stunning accuracy – except for a particular spot in New York.

flying pigeon drawingWhenever homing pigeons were launched from that particular spot, they would always get lost. They could easily go from Europe to Asia and Africa, but that particular area was like a Bermuda Triangle to them. But now, new research suggests that birds are using low frequency sounds to find their way around – and they cannot hear the rumble at this US location.

In order to navigate, they use infrasound—low-level background noise in our atmosphere—to fly by “images” they hear, practically creating acoustic maps of the environment. Scientists have long suspected that birds use this method to for navigation, but until U.S. Geological Survey geophysicist Jonathan Hagstrum in Menlo Park, California, became intrigued by the unexplained loss of almost 60,000 pigeons during a race from France to England in 1997, no one actually pinpointed the phenomena. The race went bust just as the birds were crossing the route of a Concorde, and Hagstrum wanted to know why.

“When I realized the birds in that race were on the same flight path as the Concorde, I knew it had to be infrasound,” he says.

Concorde airplanes are now retired, but they were the fastest commercial airplanes to ever fly, traveling with speeds faster than the speed of sound, generating a sonic boom in the process – a sonic boom which interfered with the birds’ navigation.

In a paper published today in The Journal of Experimental Biology, Hagstrum correlates the trajectory of sound waves at release sites with the pigeons’ flight performance. He also showed that at that particular site in New York, the space geometry and background rumble covers the sounds used by birds.

“Jersey Hill was a bad spot for Cornell birds,” Hagstrum says. “The geometry of the area conspired to create a sound shadow.” On the single day in August 1969 that the birds returned home, there was a temperature inversion that bounced sound back to the release site, allowing the pigeons to navigate.

What’s surprising is that this study came from a geophysicist – not the typical area of activity for him; however, other researchers were thrilled by the results.

“I think it’s very convincing evidence that infrasound is a component of information birds use,” says Alfred Bedard, a physicist at the Cooperative Institute for Research in Environmental Sciences in Boulder, Colorado, who wasn’t involved in the study. “The open area is what infrasound they find most useful.” Still, “these results aren’t surprising,” he says. “If creatures have information in their environment that’s important to their survival, they would sense it.”

Via ScienceMag


Sensing technology destined for robots adapted to help the blind navigate

One of the most sophisticated parts of a robot is its navigation system, why requires precise sensing and processing of the information, if an anthropomorphic robot is to walk around a house safely or a rover trek through the rocky wastelands of Mars, for instance. Billions have been dedicated to this field, and naturally technological advances derived from research has been directed towards helping people with impairments as well.  A recent promising such device has been developed by scientists at the Institute of Intelligent Systems and Robotics at the Pierre and Marie Curie University in Paris, in the form of a pair of glasses equipped with cameras and sensors like those used in robot exploration.

blind-robotThe system was first demoed at a MIT conference last month, and functions by producing a 3D map of the wearer’s environment and their position within it, after two cameras capture the surroundings and a processor analyzes the images. These are constantly updated and displayed in a simplified form on a handheld electronic Braille device. The surface of the Braille device is actually a sort of dynamic tactile map which can generate  almost 10 maps per second, with the help of the system’s collection of accelerometers and gyroscopes which keeps track of the user’s location and speed, combined with the 3-D imaging information generated by the cameras.

“Navigation for me means not only being able to move around by avoiding nearby obstacles, but also to understand how the space is socially organised – for example, where you are in relation to the pharmacy, library or intersection,” Edwige Pissaloux says.

According to the researchers, the Braille map updates fast enough for a visually-impaired wearer to pass through an area at walking speed, fact truly impressive. Hopefully these can be manufactured cheaply enough to be commercially viable in the near future.

Also, related to this device is the MIT Media Lab’s EyeRing. This remarkable device is designed to be worn by the visually impaired as a ring, which is equipped with a camera and headphones. The wearer needs only to point the ring towards a desired object and vocally command what kind of action the device needs to describe, after which the camera snaps a picture and wirelessly transmits it to a tethered smartphone which processes it. The wearer can find out the color of a shirt, what’s the price tag for a book or even how much a currency bill is worth. Check out the video presentation for the EyeRing below.




Humpback Whale

Humpack whales flawless natural navigation studied

Humpback Whale

A recently published study 8 years in the making reveals the uncanny ability humpback whales have of following seemingly perfect straight paths for weeks at a time. The navigational precision of humpback whales cannot be explained by known theories.

Humpback whales feed during the summer near polar oceans and migrate to warm tropical oceans for the winter, where they mate and calves are born. This means that during a year a single humpback whale can easily amass 10,000 miles worth of return journeys, making them one of the most farthest migrating animals on Earth. Their migrating paths are perfectly straight, sometimes deviated only by a few degrees, fact that poised researchers to study them and see exactly what mechanism compels the huge watery mammals to become such precise navigators.

Researchers from the University of Canterbury, in Christchurch, tracked 16 radio-tagged whales as they migrated thousands of miles north from the South Atlantic and South Pacific with unswerving accuracy, often covering more than 600 miles but deviating off course by less than one degree.

“Such remarkable directional precision is difficult to explain by established models of directional orientation,” the researchers, led by Travis Horton from the University of Canterbury, wrote in the Royal Society journal Biology Letters.

Each animal was tagged with a special positioning device which attached to the whale from four weeks to seven months before falling out, transmitting precise position data and provided one of the most detailed sets of long-term migratory data for humpbacks ever collected.

Most long-distance traveling animals are believed to navigate using an internal compass that relies either on the earth’s magnetic field or the position of the sun. However, the scientists wrote, “it seems unlikely that individual magnetic and solar orientation cues can, in isolation, explain the extreme navigational precision achieved by humpback whales.”

They instead added, “The relatively slow movements of humpback whales, combined with their clear ability to navigate with extreme precision over long distances, present outstanding opportunities to explore alternative mechanisms of migratory orientation.”

Earth’s magnetism varies too much to explain the whales’ arrow-straight patterns, and you can’t really rely on solar navigation when navigating through water.

“Humpback whales are going across some of most turbulent waters in the world, yet they keep going straight,” said environmental scientist Travis Horton of the University of Canterbury, whose team will publish their findings April 20 in Biology Letters. “They’re orienting with something outside of themselves, not something internal.”

Horton suspects humpbacks rely on both mechanisms, and perhaps the position of the moon or stars. John Calambokidis of the Cascadia Research Collective, suggested a fourth mechanism for steering: long-distance songs that can carry for hundreds or thousands of miles underwater, and may provide navigational cues or help migrating whales coordinate their movements.

“These whales are clearly using something more sophisticated to migrate than anything we’ve surmised,” said Calambokidis. “I’m really looking forward to seeing what this team does next.”

Prepared to see, correction, hear something really amazing? Check out the video below.

UPDATE: a recent study has finally proven that sockeye salmon indeed rely on magnetic field to guide itself back to the freshwater stream of their birth – a trait that’s believed to be also used by the humpbacked whale.

The world may be too dependent on GPS, report says

Besides their evident telecommunications value, satellites also pose enormous benefits when synchronization and navigation are concerned, available and more and more used to the common public through GNSS (global navigation satellite system) or the US based GPS (global positioning system). However, a report published by the Royal Academy of Engineering in the UK warns that the nation has become overly reliant on the system, which academicians consider it to be very vulnerable and prone to natural hazards (solar flares) or deliberate attacks (terrorist endeavors).

Dr Martyn Thomas, who chaired the group that wrote the report, said: “We’re not saying that the sky is about to fall in; we’re not saying there’s a calamity around the corner.

“What we’re saying is that there is a growing interdependence between systems that people think are backing each other up. And it might well be that if a number these systems fail simultaneously, it will cause commercial damage or just conceivably loss of life. This is wholly avoidable.”

Remember, that GPS applications aren’t limited to simple, though widespread, auto-navigation or as personal mapping; they’re used by manufacturing industries, supply chains, drilling oil, various other logistics, banks, and virtually anything you can imagine. It’s not a UK based dependency either, it’s a fact well known applying to the whole world. The failure of such a system might indeed deem severe economic and social consequences.

Just how much? Let’s just stick to money-wise -the European Commission, in a recent update on its forthcoming Galileo sat-nav network, estimated that about 6-7% of Europe’s GDP, approximately 800bn euros (£690bn) annually, was now dependent in some way on GNSS data.

“The deployment of Europe’s Galileo system will greatly improve the resilience of the combined GPS/Galileo system, but many of the vulnerabilities we have identified in this report will remain,” says Dr Thomas.

“No-one has a complete picture of the many ways in which we have become dependent on weak signals 12,000 miles above us.”

The report goes on to suggest some solutions for backing-up and improving the signal, such that calamities might be avoided, such as awareness campaign so that users might begin to back-up their signals, R&D investments for new signal-enhancing technology, and probably the most practical – a plea to the UK government to ban jamming equipment. This kind of equipment can be bought for as low as 30$ and are used mostly by criminals to disrupt tracking signals for jacked cars.

I think the subjects begs for an interesting question to be pondered, how many of you know how to read a map?