Principles of goal-directed spatial robot navigation in biomimetic models

(a) Robotic perception

Sensing plays a key role in robot navigation. First and foremost, it is the means by which a robot can construct some form of world representation, whether simply remembered sensory snapshots [8] or a precise metric map of free and occupied space [9]. Sensing enables the robot to keep track of where it is within that world representation when navigating to a goal. Sensing can also be used to enable deviations around an unexpected obstacle blocking the planned path to the goal [10].

The issue of uncertainty in sensing has played a critical role in robotic navigation research. Without uncertainty, navigation becomes a trivial problem: with perfect dead reckoning, a robot can find its way from any location to any goal location, without requiring any other sensing modalities. Even when, as pointed out in biomimetic studies [11], dead reckoning alone becomes insufficient when an animal or robot is ‘kidnapped’ to an unknown new location, perfect sensing can enable a robot to instantaneously recognize where it is within the world and consequently resume navigating. Of course, perfect sensing does not exist, and consequently an immense amount of effort has gone into dealing with this uncertainty in robotic navigation systems.

Robotic navigation systems typically use one or more of five types of sensing:

The US Defense Advanced Research Projects Agency (DARPA) grand challenge robot described in the Introduction made use of sensors from four of these five categories; multiple laser range finders, cameras, GPS and wheel encoders. Most robotic systems do not rely on sensors from all five categories, for example the majority of indoor robot navigation systems do not use a global localization sensor, partly because GPS is not available indoors, and partly because with the exception of the relatively new WiFi-based localization [17], custom infrastructure is required. Functional requirements have driven most state-of-the-art field-deployed navigation systems to use a multi-modal sensing approach. For example, in the DARPA grand challenge navigation using only global GPS co-ordinates would probably have resulted in the robot car falling off a cliff [1]. Only through visual and range-based sensing of the immediate environment was disaster averted.

Of particular relevance when comparing robotic navigation systems to biomimetic models is the pivotal role that sensing has played in shaping the choice of world representation, the development of mapping and navigation algorithms and even the application domains for robotic navigation research. For example, the algorithms underlying many of the best performing robotic navigation systems have resulted from roboticists having access to high accuracy, range to obstacle sensors such as the ubiquitous two-dimensional scanning laser range finder [20]. These sensors also enable boosting of critical navigation processes such as dead reckoning: a process of scan matching between consecutive laser scans enables high-quality dead reckoning without the use of other self-motion information sources. Of course, as we shall see in the following section, such a long range, in-plane only scanning sensor is biologically implausible with the possible exception of bats [21], which has implications for the biological relevance of the world representations that have been developed using it. More recently, a large number of research groups and corporations have taken on the autonomous car navigation problem, with systems such as the Google driverless car [22] logging hundreds of thousands of kilometres of autonomous driving with only occasional human intervention. Such approaches benefit from the next generation of range-based sensors, such as the Velodyne Lidar [23], which provides long range distance to object information in three dimensions, as opposed to only in a plane as per traditional laser range finders.

Recently, owing to the rapid advances in camera technology and onboard computation over the past decades, high performance robotic navigation systems have shifted to incorporating two alternative types of sensing modality: cameras and RGB-D sensors. Using state-of-the-art techniques from the related field of computer vision, a standardized robotic navigation workflow involves taking medium-to-high resolution imagery (640 × 480 pixels) captured at 30 frames per second from a robot-mounted perspective camera with a moderate field of view (50–90° horizontally). When incorporating RGB-D sensors such as the Microsoft Kinect, a short-range three-dimensional layout of the environment is obtained, which has also reshaped how navigation algorithms are developed [12,24].

(b) Biomimetic perception

We argue here that the role of sensing in biomimetic navigation models is generally fundamentally different from its role in robotic navigation systems. Biomimetic navigation models primarily emulate the biological system's perception in one of two ways; either they use an approximate technological analogue for the animal's sensor(s), such as using a pair of fish-eye cameras to represent bee or rodent vision, or by abstracting the sensing problem to various degrees, either through simulation or by using artificial real-world environments. Critically, the key concept in robotics that all sensing is to some degree uncertain is typically not addressed in biomimetic modelling. Whether this discrepancy needs be addressed is an area of open discussion that we hope to resolve here. In addition, we shall see that there is one key area where sensing uncertainty has been extensively addressed in biomimetic models—dead reckoning—revealing surprising insights that would not have come to light in a ‘perfect’ sensing approach.

In the model by Erdem & Hasselmo [25], a virtual agent explores a simulated arena recruiting place cells at various scales. Navigation to a goal is achieved by conducting look-ahead probes over multiple place cell scales until the place cell encoding the goal location is hit. The encoding of space by place cells in this model is in effect a metric map. Sensing in this model is largely abstracted; the virtual agent traverses the arena with what is in effect a perfect self-motion sensor and has no ability to ‘observe’ the external world, lacking any range or vision sensing capability. The authors suggest that future work might add a ‘loop closure’ ability inspired by robotics to enable operation with imperfect sensing. In metric robotic mapping, loop closure must typically be followed by a map relaxation or consolidation process, which distributes the accumulated dead reckoning error by changing the spatial layout of the map. Without this map consolidation, the map manifold rapidly becomes unusable from a navigation perspective, as shown in experiments using the loosely grid cell-based RatSLAM model [26,27]; loop closure was implemented using an engineering solution based on graph-relaxation theory [28]. It is probable that adding a loop closure ability to deal with more realistic sensing (as suggested by Erdem & Hasselmo [25]) would require significant changes to the underlying navigation model. Pursuing this challenging line of investigation might reveal further insights into how multi-scale grid cells can perform navigation computation, not just for this model but for many others that lack a perception component [29].

It is possible that loop closure and map consolidation are not performed by animals; instead the animal may recalibrate its estimate of where it is in the environment by returning to a familiar location. This return and recalibrate behaviour is a key component of the rodent-inspired model by Arleo [30]. Its implementation was driven by engineering heuristics however; to deal with accumulation of self-motion errors, the robot was endowed with a monotonically growing sense of uncertainty, which eventually drove it to return to its home location and recalibrate its path integrator. More biological plausibility has been found for the model by Mathews et al. [31], in which the virtual agent, after encountering unexpected landmark configurations, reverted to traversing familiar terrain. Ants tested in parallel demonstrated similar performance, suggesting that they employ an active approach to dealing with sensing uncertainty.

Many biomimetic models do incorporate some form of sensing of the external environment. Typically, these approaches fall into one of two categories: landmark-based techniques and snapshot-based techniques.

Landmark-based models are particularly prevalent in insect- [11,31–35] and rodent-inspired models [30,36–42]. Landmarks typically take the form of artificial cylindrical cues added to a real or simulated environment, or ‘natural’ landmarks extracted by performing edge or blob detection on images. In the vast majority of models, there is little or no uncertainty associated with detecting these landmarks; either because the landmarks are not actually perceived, their location and identity being hardcoded in a simulation environment, or because relatively few, highly distinctive landmarks are used [37,38]. The challenge of perceptual aliasing is explicitly noted in some of these studies; for example, in the desert ant model of Lambrinos et al. [43], world views are pre-aligned to an absolute compass orientation in order to reduce, but not eliminate, the chance of aliased landmark configurations. This approach yielded plausible ant-like navigation behaviour, which, along with the ant's access to a polarized-light compass, may mean that ants possess mechanisms for reducing the effect of sensing uncertainty. Other methods of dealing with sensing uncertainty include active assessment of landmark reliability. In the bee- and wasp-inspired ‘turn back and look’ model by Lehrer & Bianco [34], as a robot retreats from a goal location, it moves from side to side over limited arcs centred on the goal location, capturing camera image templates at regular intervals. Landmarks that are reliably detected during this behaviour are learnt while unreliable landmarks are discarded. When returning to the vicinity of the goal, the robot navigates to the goal location by attempting to minimize the discrepancy between its current landmark view and the landmark configuration at the goal. Landmark-based biomimetic navigation models also exhibit a desirable performance capability in robotics; the ability to still successfully navigate when the agent is kidnapped. In [32], a robot forager dubbed SyntheticAnt uses a novel bioinspired path integration mechanism called head direction accumulators (HDAs), which integrate motion in a specific direction only, and a trained neural network for extracting salient hue and edge visual features for use as landmarks. HDA is a mapless biologically based model implemented in the framework of the distributed adaptive control (DAC), a coherent architecture for goal-oriented action [44,45]. Reactive behaviours handle collision avoidance, chemical tracking and food (odour) source detection. Together these components enable SyntheticAnt to forage for a food source, memorize the routes used in doing so and then find that food source using only landmarks even when kidnapped to an unknown starting location. Recovery from kidnapping using landmarks is also demonstrated in the place cell inspired approach of Giovannangeli et al. [11]. During exploration, place cells became associated with a specific spatial constellation of landmarks. To perform goal navigation, place cells are associated with a desired robot movement in order to navigate towards a specific goal place cell. The robot was capable of navigating to a goal even when kidnapped to an unknown but previously visited location.

Snapshot-based navigation models have different sensing and computation requirements to landmark-based approaches, requiring the ability to capture some form of sensory snapshot of the environment and compare it to previously captured snapshots. In the rodent-inspired model by Cheung et al. [46], navigation is performed by minimizing whole image differences between a reference image at the goal location and the image from the virtual rat's current location. This system generated navigation trajectories that mimicked those of rats in the same experimental paradigm and is robust to ‘kidnapping’ since navigation is based entirely on the current image difference rather than any state information.

The concept of sensing uncertainty, which has dominated robotic navigation research, has most extensively been studied in biomimetic modelling in the context of dead reckoning. This focus on sensing uncertainty has probably been driven from two biological observations; the apparent incredible dead reckoning capabilities of tiny-brained insects like the desert ant Cataglyphis, and the seeming stability of grid cell maps in the rodent brain over long periods of time when visual cues have been removed. In the case of rodent map stability, studies such as [47] have demonstrated surprising results; that map stability in the dark can be explained entirely by the combination of short-range whisking and knowledge of the geometrical wall layout, without unique wall identification (figure 2). In the case of insect navigation, theoretical studies have proved the importance of a global orientation sensor when performing long range dead reckoning [48]. These theoretical studies are qualitatively consistent with the biomimetic models of long range ant dead reckoning performed with and without a polarization compass by Lambrinos et al. [43].

• Download figure
• Open in new tab
• Download PowerPoint

(c) Summary

Clearly, there are both similarities and differences between the role of perception in robotic navigation systems and biomimetic navigation models. Robotic sensing and associated navigation algorithms are largely driven by the concept that all sensing is uncertain. For biomimetic models, uncertainty currently plays a role, especially in dead reckoning, but a less significant one. Undoubtedly, this is partly owing to the small artificial laboratory paradigms where the classical robotic navigation challenges of perceptual aliasing, odometric drift are less evident. It is probable that, without modification, many of these biomimetic models would provide adequate performance in robotic navigation applications within similar small, static indoor environments.

However, the real habitats of many animals and insects are often much larger and more perceptually challenging and complex than laboratory experimental mazes. We know from the history of robotic navigation research that many critical theoretical advances resulted from the ‘hard, operationalized task demands’ of navigation in real-world environments [49]. The benefits of this ‘enforced specification’ provided by testing in the real world rather than simulation environments were also noted by Webb [50]. It is likely that bringing those same hard task demands to biomimetic models will yield further insights into how goal-directed navigation is achieved in the brain. The proof of concept already exists in the desert ant models, where modelling uncertainty has led to insights into both a recalibration method for dealing with unexpected sensory input [34] and the critical role of global orientation sensing for long range dead reckoning [43,48]. We speculate that introducing realistic sensing into other biomimetic models will probably require significant modifications to the underlying navigation models; these modifications in turn may lead to both improved theories of animal navigation, new experimental paradigms and potentially new high performance techniques for robot navigation.

(a) Robotic world representations for navigation

With the exception of purely reactive robotic control architectures which use a ‘representation-less’ direct perception–action process such as [51,52], most robotic navigation systems employ some form of world representation. A world representation plays a critical role in goal-directed robotic navigation, by providing a framework within which to define a goal (whether spatial—go to a specific coordinate, or abstract—go to the kitchen) and a means by which to plan a route to a goal and track a robot's progress towards that goal.

Robotic goal-directed navigation can be a process as simple as a wheeled robot navigating from a well-illuminated area to a dark area, or highly complex, such as the robotic car navigation example described in the Introduction. The first navigation task can be achieved without any explicit world representation by relying on simple control rules relating sensory input to motor commands [52], while the latter task almost certainly requires some form of world representation or map. In-between these two examples, there are a range of world representations underlying goal-directed robot navigation, such as that used in the ‘Teach and Repeat’ approach; a robot is taught a path to a goal by being manually guided along it so that it can then autonomously repeat that route by recalling the relevant sensory and motor command sequence [8,53]. Robots often incorporate multiple different world representations for navigation; a standard approach is to combine a global topological map with a local metric map [54,55].

Much of the focus in initial robotic mapping research was on creating the most accurate maps of the largest possible environments, rather than the utility of these maps for robot navigation [56–58]. Consequently, many current state-of-the-art robot navigation systems are the result of a somewhat ad hoc development process after the core mapping algorithm was already established, in contrast to nature where map formation and map utilization processes have presumably co-evolved. The prime example of this separate development cycle would be the metric occupancy grid map, first developed in the 1980s [9,59]. Figure 3a shows a typical occupancy grid map, which represents the environment as a grid of locations that are either obstacles or free space with a calculated probability. This type of world representation is easily produced with the range-to-obstacle information provided by the sonar and laser sensors that dominated early robotic mapping and navigation research, and now three-dimensional range sensors such as Kinects and Velodynes. Robotics and computer vision research has also demonstrated that obtaining this depth information from stereo vision and scene understanding algorithms is possible but much more difficult [62]; a result we shall see is relevant to occupancy grid-like representations recently found in rodents.

• Download figure
• Open in new tab
• Download PowerPoint

A large range of algorithms [56,57,63–70] have been developed to deal with the key issues in producing and maintaining a suitable metric map for robot navigation: sensor observation uncertainty, scalability to larger environments and the need to incorporate changes in the environment. Metric occupancy maps have been used extensively both in forming global representations of a robot's entire operating environment, as well as for encoding the local area around the robot in order to facilitate object avoidance and local path planning. For example, most robotic cars including Stanley the DARPA grand challenge winner [1] maintain a high fidelity three-dimensional occupancy grid map in the robot's immediate area.

Topological robotic mapping algorithms encode the connectivity of places in the robot's world without necessarily maintaining a globally metric representation of space [71]. Figure 3b shows a typical topological map [72], with nodes encoding places in an environment and links between nodes encoding transitions the robot has successfully made between those places. Unlike occupancy grid techniques, which typically do not attempt to explicitly identify landmarks in the environment, many topological robotic mapping techniques incorporate landmark or feature detection as a critical component [73,74]. In the context of navigation, topological maps offer both advantages and disadvantages over metric occupancy grid maps: calculation of paths to a goal is generally simpler but navigation is limited to repeating already traversed routes—shortcutting based on dead reckoning or an assumption of map metricity is typically not feasible. Topological representations are also used by snapshot-based navigation techniques that recall sequences of sensory input in order to navigate to a goal [8,72].

Hybrid robot mapping and navigation approaches combine local and global mapping and navigation techniques [10,53–55,75,76], typically motivated by computational efficiency demands. Almost universally, hybrid robotic mapping approaches use a local, metric map of space with a global topology [54,55,77]. The mapping and navigation frameworks in these and other approaches have generally been limited to two distinct scales and are heterogeneous, in that different types of representations are used at different scales. This is especially relevant in light of biomimetic navigation models based on the recently discovered homogeneous multi-scale representations of space in the rodent brain [25,78].

(b) Biomimetic world representations for navigation

Where roboticists explicitly design and construct methods for constructing world representations suitable for navigation, biologists must infer the nature of these representations in animals from observing animal behaviour and in some cases, neural activity. Observations from animal experiments can indicate that a specific hypothesized world representation theory is probable or improbable owing to its consistency or otherwise with experimental observations. However, there is often a degree of uncertainty, clearly evident upon any review of the literature, with many unresolved world representation topics being debated: do insects use cognitive maps [79]; can rodent navigation behaviour be explained using geometry or view-based environmental representations [46]; what is the underlying neural mechanism for encoding space in the rodent brain [80,81]?

Given the preponderance of occupancy grid-based representations in robotics derived largely from decidedly biologically implausible laser range finders, it is worthwhile querying whether animals use occupancy grid-like representations to perform navigation. Differentiating representations from behaviour can be challenging: for example, we know that bats are capable of precise navigation around obstacles in flight [82], but is this a result of pure sensory-action loops or some internal metric representation of three-dimensional space? Perhaps the most suggestive evidence for animals encoding the world in a manner similar to robotic occupancy grid maps is found in rodents, and specifically boundary vector cells (BVCs), which fire at a certain range and relative orientation from an environmental boundary, and border vector cells, which may also include directionality in specific, short-range boundary detector cells [83].

It is almost certain that the mechanisms by which BVCs are formed are different from those used in robotics. First and foremost, it is unlikely that rodents can accurately and reliably determine ranges to distal boundaries from sensing alone; their stereo baseline and visual acuity is insufficient for such a task [84] while whisking is short-range. There are very few occupancy grid-based robotic mapping systems that do not use long range laser or sonar sensing, with one exception being the Shrewbot approach of Pearson et al. [19]. In this biomimetic mobile robot, mapping and localization was shown to be possible using only noisy dead reckoning information and short-range tactile information from a three-dimensional array of active biomimetic whiskers. If rodents do maintain an occupancy-based representation through BVCs without an explicit means of calculating boundary ranges, additional modelling in the vein of the Shrewbot system may provide further insights into the functional benefits of encoding this range to boundary information despite lacking a long range obstacle sensor. Investigations into the potential role of tactile sensing in spatial learning for navigation have also been performed using other animal models including crayfish [85], with qualitative replication of crayfish behaviour.

While relatively few biomimetic navigation models encode an actual map of occupied and free space in the environment, the navigation mechanisms of many rely upon the metricity of the underlying world representation. Biomimetic navigation models driven by dead reckoning are implicitly globally metric, such as the ant-based model by Lambrinos et al. [43]. The multi-scale navigation model by Erdem & Hasselmo [25] relies on the metric layout of space as encoded by the virtual place cells in the model; without this metricity the efficacy of the key probe-based navigation mechanism would probably degrade significantly. This metricity brings functional benefits, enabling shortcutting through parts an environment that the virtual rat has never visited [25]. Another rodent-inspired model [86] encodes a metric representation of space and proposes a linear look-ahead navigation mechanism that relies upon the metricity of that representation.

Many biomimetic navigation models use landmark-based world representations [11,36–38], usually in combination with a dead reckoning capability. At the simplest levels, models such as that by Burgess et al. [36] encode the average relative angle between the rat's heading and two specific visual landmarks, creating a phase precession effect, although there is no evidence that landmarks drive phase precession in this manner in actual rodents. In the insect-inspired model by Mathews et al. [32], hue- and edge-based landmarks extracted using a neural network are initially stored in a short-term memory repository before transitioning to a long-term memory when a goal location is reached. Navigation trials with this model demonstrated competent landmark-driven navigation to a goal, including from starting locations that the robot had never visited before. The bee- and wasp-inspired model by Lehrer & Bianco [34] encodes the landmark configuration at the goal location in order to perform difference-based homing to the goal.

Topological maps encode useful transition information for robotic navigation such as connectivity between places, as well as sometimes storing additional navigationally relevant information in the links between map nodes, such as robot motor commands, movement behaviours or temporal transition information [26]. Conjunctive grid cells (and directionally tuned place cells) in the rodent brain encode similar transition information and have inspired a number of topological biomimetic navigation models. The model by Cuperlier et al. [39] introduces transition cells, which are functionally indistinguishable from conjunctive grid cells or direction place cells. In an open area, the model learns multiple transition cells at a location representing all possible movement from that location, while in a constrained linear track, it learns only bi-directional transitions, providing a possible explanation for the directionality of place cells in linear track environments. Transition-based place cells also form the basis of the topological model proposed in [11]. Like topological robot navigation systems, these topological navigation models also do not provide the ability to perform shortcuts during goal-directed navigation however; rodents appear to neurally compute and exploit shortcuts [87,88].

In the model by Blum & Abbott [89], long-term potentiation (LTP) was used to learn temporal and spatial information about a rat's motion by modifying inter-place cell synaptic strengths. When a simulated rat traversed a familiar route, a delay in LTP induction strengthened links between presynaptic cells and postsynaptic cells further along the path. Over time, place cell activity started to anticipate the rat's future location along this route. Navigation was achieved by moving towards the position encoded by this anticipatory cell activity. This navigation model was tested in a simulated Morris water maze and produced rat-like decreasing platform acquisition times over multiple trials. To enable navigation to multiple goal locations in this model, place cell activity was modulated based on goal location [90]. Different specified goal locations then activated different navigational maps. With sufficient goal coverage, novel, ‘interpolated’ goal locations could also be specified by combining maps from multiple goal locations. Recent biomimetic modelling research has calculated theoretical upper bounds on the number of navigational maps that can be stored in parallel [91]; biological verification has yet to be performed.

Finally, several attractor-based models of grid cells have been used for and analysed in the context of robot navigation, both on simulated [92] and real robots [41,93]. In [92,94], theoretical analysis and simulation demonstrates the navigational benefits of a grid cell architecture with respect to accuracy, robustness and computational compactness. The RatSLAM rodent-inspired model encodes the spatial layout of space with a single-scale attractor model of grid cells [41]. The rate-coded attractor model used is significantly more abstracted from biology than the more sophisticated attractor and oscillatory-interference models used in higher fidelity biological models [95,96]; however, the current weight of evidence from biology is more supportive of attractor models [25]. RatSLAM uses an attractor model where the physical proximity of grid cells is correlated with the spatial locations they encode; biological studies suggest there is no such correlation in entorhinal cortex. To achieve hexagonal grid-like firing patterns, a hexagonal layout of grid cells is used; recent evidence suggests pyramidal cells are arranged in a similar hexagonal grid-like arrangement [97]. Where other models have postulated that conjunctive grid cells may encode a topological map, simulation experiments in a corridor paradigm with ambiguous landmark configurations with RatSLAM [98] have identified a possible role for conjunctive grid cells in filtering sensory uncertainty by maintaining and propagating multiple estimates of pose until the correct estimate can be resolved (figure 4). Under this theory, grid cell remapping plays a key role in managing this spatial uncertainty [98].

• Download figure
• Open in new tab
• Download PowerPoint

(c) Summary

As with perception, there are similarities and differences in how the world is encoded in robotic navigation systems and biomimetic navigation models. BVCs provide some evidence for a biological equivalent of the ubiquitous occupancy grid map found in many state-of-the-art robotic navigation systems, but their formation and function are most likely different. Why rodents apparently encode a range-based representation of boundary obstacles without possessing a laser-like sensor is an interesting question which has not been investigated thoroughly in robotic or biomimetic navigation models; further investigation may reveal new insights into possible functional benefits.

Topological-like maps are also extensively represented in the biomimetic modelling field. The highly abstracted graph-like topologies found in robotic navigation systems are probably not directly relevant to how neural systems encode space; instead researchers have searched for possible neural mechanisms for encoding topology, such as the conjunctive grid cells and directional place cells which may encode a form of topological map [39]. We shall see in the following section that the most glaring discrepancies between robotics and biological and associated biomimetic models result when these representations are actually used to plan and perform navigation to a goal.

(a) Robotic path planning and navigation

The techniques by which robotic navigation systems plan and execute a route to a goal location depend on three primary factors: their sensing capability, the world representation available to them, and motivating factors that constrain the method by which they reach the goal. In the case of spatial-based navigation strategies, sensing can both determine the robot's starting location and also update its estimate of navigation progress towards a goal [99]. For landmark- or snapshot-based navigation systems, sensing is critical to correctly detecting and discriminating between different landmark configurations or snapshot templates. When planning a path to a goal, motivating factors can vary immensely from concrete task constraints: minimizing time duration to reach the goal [72], distance travelled [10], energy consumed, to more abstracted concepts: planning a path that minimizes the chance of getting lost along the way [100], or the chance of being observed by hostile agents in the environment [101]. These concepts are all broadly relevant to animal navigation.

It is in the computational mechanisms for performing path planning where robotics diverges most significantly from biology and biomimetic models. Most state-of-the-art robotic navigation systems apply formal path planning and search techniques to their world representations in order to plan a path to a goal [100]; we shall see here that these methods use computational mechanisms that are highly abstracted from any neurally feasible computation, a point noted in many biomimetic studies. For example, when discussing how a conventional, gradient-based path planning algorithm might be realistically implemented in a model of rodent navigation, Cuperlier et al. [39] note that ‘using an external algorithm “looking for” the gradient of activity leads to the famous problem of the homunculus: “who is looking at the place cell activity?”’.

Robot navigation using metric maps typically involves the use of a search algorithm to find the best path from the current location to the goal in the environment. Dijkstra's algorithm [102] and variations of it, such as A* search, are commonly used to search for routes in both metric and topological maps (figure 5). For example, the Minerva museum tour guide robot [58] performed ‘coastal navigation’ [100], navigation designed to minimize the chances of the robot getting lost, using a laser range-finder and a metric occupancy grid map supported by a visual sensor and visual map of the museum ceiling. When the global navigation problem is simplified, such as in the case of Stanley the robotic car which was provided with GPS waypoints, path planning is primarily performed within the robot's three-dimensional metric map of local space, constrained by a number of motivating factors including avoiding obstacles and sudden turns, driving in the centre of the road and minimizing deviations from the global waypoints [1]. Path planning in both local metric [54] and global topological maps is performed in approaches such as the spatial semantic hierarchy (SSH) [38]. Robotic ‘teach and repeat’ algorithms plan and execute long range navigation by localizing and path planning within a series of topologically connected metric submaps [53].

• Download figure
• Open in new tab
• Download PowerPoint

There have also been several notable examples of snapshot and landmark-based navigation in conventional (not biomimetic) robotics. The snapshot-based navigation system by Zhang & Kleeman [8] learns visual snapshots along a route and then autonomously retraces the route by comparing camera images to reference images and extracting a relative orientation vector which drives the robot along the route, with demonstrated robustness to lighting variation and partial view occlusion. Snapshot- and spatial-based navigation is performed in the RatSLAM system, which uses visual snapshots to localize within a topological map and perform global path planning, but then navigates the path using laser sensing and a local metric occupancy grid map [72]. A complementary approach was adopted in [104], which similarly used a topological global path planning process but combined with a local landmark-driven precise path planning process. Landmarks are used to drive navigation in [105], which also incorporates a global topological representation; however, unlike many robotic navigation systems which perform loop closure and map consolidation to deal with dead reckoning drift, this system instead uses an active exploration and reversion strategy when uncertainty is detected, a process with broad similarities to the recovery strategies used by ants and biomimetic ant navigation models [31].

(b) Biomimetic path planning and navigation

Development of biomimetic navigation models is typically focused on qualitative or quantitative replication of animal-like navigation behaviours under similar experimental conditions, sometimes with neurally plausible computational mechanisms. Because most animal navigation experimentation occurs in small artificial laboratory environments, these navigation models can provide animal-like behaviour without necessarily addressing any of the real-world navigation concepts faced in robotics such as dead reckoning drift and the landmark data association problem. A key exception is the insect-inspired biomimetic models, since much of the behavioural data they are trying to emulate is from experiments in large natural animal habitats such as the Saharan desert [106]. Here, we review biomimetic navigation mechanisms with a focus on to what extent and how robotic navigation mechanisms are relevant to and replicated in biomimetic models. In particular, we address two key navigation concepts that are trivial (albeit sometimes computationally expensive) to compute in robotic navigation systems: long range path planning beyond the immediately observable environment and multiple goal-based navigation. Long range robot navigation is easily computed with a global metric or topological map, while imposing the requirement of navigation to multiple goals generally adds little demand upon a conventional robotic navigation system; extra goals can simply be specified in the map. These navigation tasks present significant challenges to biomimetic models: how can the short timescales of neural dynamics plan and execute a route over many minutes or even hours, and how can multiple goals and potentially routes to those goals be learned in a non-conflicting manner?

Insect-based models provide the most straightforward explanation of how animal navigation could be achieved over long distances in their natural habitats. Models of Cataglyphis navigation combine self-motion information from robot wheel encoders with absolute orientation information provided by a polarized-light compass to enable navigation using long range dead reckoning, with visually guided homing used in the vicinity of landmarks [43]. The model does not require that individual landmarks are uniquely identified but rather that landmark constellations are uniquely identified. This combination of dead reckoning navigation combined with landmark recognition is also found in other insect navigation models [32] which replicate ant-like behaviour. Insect anatomy is generally well known but recording detailed neural activity is challenging in such a small system. Consequently, modelling approaches try to emulate the known anatomy of the insect brain, with replication of insect navigation behaviour, rather than neural activity, being the primary indication of their biological plausibility.

Arguably, the strongest neural indication of long range path planning to multiple goal locations has been found in the rodent hippocampus, which has recently been shown to generate place cell activity sequences which encode the route from the rat's current location to a goal [107] in a process dubbed ‘preplay’. This discovery is particularly relevant because it extends previous evidence, which showed replay of previously traversed routes [108]—the current evidence reveals route replays between previously never before experienced combinations of starting and goal locations, providing a plausible neural basis for shortcutting [87,88]. A recent model by Azizi et al. [91] describes a continuous attractor model of the recurrent connectivity in brain region CA3 that could generate similar preplay activity. Relevant to the challenge of encoding multiple goals described earlier, this model was able to drive preplay activity in parallel in multiple different spatial maps or ‘charts’ encoded by the same network of cells. Novel path planning was also demonstrated using a ‘linear look-ahead’ model [86], which used slight phase offsets between conjunctive grid cells encoding similar orientations to drive navigation towards a goal. Action planning using replay is also performed in [109].

The discovery of multiple spatial scales in the medial entorhinal cortex grid cells [4,110] resulted in attempts to model long range navigation by exploiting this multi-scale world representation [25,111]. In these models, path planning is performed by probing linear look-ahead trajectories in multiple directions from the virtual rat's current location until a probe activates a place cell associated with the goal location. The advantage of a multi-scale approach is that goals at all possible ranges can be probed with similar computational efficiency; probes first being performed at the coarsest spatial scale and then selectively at finer spatial scales in the vicinity of the goal location. The current disadvantage of the model is that it does not model obstacles and boundaries, which have been shown in rodent experiments to disrupt spatial cell firing fields [112]. This map fragmentation over large environments is particularly relevant to modelling approaches, since many rodent-inspired navigation models explicitly or implicitly assume that the world representation within which path planning occurs is metric, or at the very least spatially contiguous. If this assumption breaks down, navigation can be compromised. In an early RatSLAM model, applying a non-biological gradient-based path planning algorithm using virtual grid cells was sufficient in a small environment [27], but broke down in larger more complex environments as the spatial representation fragmented.

Because of the homunculus problem associated with applying algorithmic approaches to path planning within a grid or place cell encoding of space, some models implement transition-based encodings of routes to goals, such as the transition cells implemented in [39] and other models that encode place transitions [11,89]. The mechanisms proposed by these models have possible biological analogues; for example, transition cells are similar to directional place and grid cells. However, like robotic topological navigation systems, these models are unable to plan navigation between locations that have not previously been connected by traversals, which seems implausible given recent evidence of such in rats [107]. A model combining aspects of these approaches with a model capable of novel path planning such as [25] may yield more plausible behaviour, while relaxing the strict metric spatial requirements of the metric-based approach [25].

(c) Summary

The differences between state-of-the-art robot navigation systems and biomimetic navigation models are perhaps most apparent when considering the computational mechanisms used to perform path planning and navigation. Most robotic world representations readily lend themselves to path planning approaches using formal search algorithms, for which there is no realistic biological analogue. By contrast, biomimetic modelling approaches face a number of challenges in realistically implementing solutions to the problems of path planning over long distances and towards multiple possible goal locations, sometimes over routes that have never previously been traversed. Insect models have demonstrated long range ant-like navigation by combining accurate self-motion and compass-driven dead reckoning with visual landmark homing. Modelling insect navigation is both easier and more challenging than modelling rodents; there is little explicit neural evidence to constrain a model's biological plausibility, but whatever mechanism is proposed in a model must be computable in real-time using relatively little computation and storage [113].

As well as the discovery of multi-scale maps, rodent studies have revealed temporal patterns of neural activity which appear to encode long distance, sometimes novel paths to goals [107]. Many biomimetic models however are based on older ‘route replay’ evidence where only previously traversed routes can be used to navigate to a goal; only recently have new models appeared that attempt to explain this evidence for more general and possibly novel path planning to goals [25,91]. These new experimental results and associated theories are probable fertile grounds for future biomimetic modelling research.