AND IDENTITY OF A PHYSICAL OR LOGICAL SPACE OR ATTRIBUTE THEREOF

TECHNICAL FIELD

[0001] A system and computer-implemented method for parsing a multi-dimensional space and determining the structure of the space, particularly for the purposes of navigation in unfamiliar environments, and for the visual classification of objects and/or images.

BACKGROUND OF INVENTION

[0002] Simultaneous localization and mapping (SLAM) is the problem and process of computationally constructing or updating a map of an unknown environment, while simultaneously keeping track of an agent's location within it. SLAM algorithms are based on concepts in computational geometry and computer vision, and are used in robot navigation, robotic mapping and odometry for virtual reality or augmented reality.

[0003] SLAM algorithms are also used in the control of autonomous vehicles, to map out unknown environments in the vicinity of the vehicle. The resulting map information may be used to carry out tasks such as path planning and obstacle avoidance.

[0004] Visual SLAM uses an approach consisting of a front end, which processes images from a camera to perform ‘feature extraction’. This feature extraction process finds small regions of the image that meet certain criteria for being visually distinct, such as high local spatial frequency and contrast. These regions can then be stored for the purpose of locating the same region in a subsequent camera image from the same camera, taken a short interval later. These features’ locations are then mapped onto directions in the real world by applying a camera model that accounts for the distortions of the camera lens. These are then provided to the back end of the algorithm, which is known as a bundle adjuster. The bundle adjuster attempts to compare the predicted locations in 3D space of the features based on previous camera images with the new directions from the current camera image and determine, simultaneously, the location of the features relative to each other in 3D space, and the location of the camera relative to the features. By repeating this process the bundle adjuster tracks the location of the moving camera and the locations of a map of features over time.

[0005] This approach suffers from several drawbacks that limit its effectiveness in real world robotic applications. Firstly, both feature extraction and bundle adjustment are very computationally expensive processes. Feature extraction can be readily parallelised for improvements to efficiency, however bundle adjustment is a strictly sequential process.

[0006] Secondly, bundle adjustment requires that the new feature directions and the predicted feature locations converge to a stable solution, something that is heavily influenced by sensor noise and changes in the environment, such as wind blowing leaves on bushes. If features are erroneously detected in incorrect locations on the camera image, then bundle adjustment can fail to converge to a stable solution, and the system becomes ‘lost’ and unable to localise.

[0007] To address bundle adjuster convergence failure, the state of the art takes two approaches. One reduces failure, and the other allows the system to continue with reduced performance when convergence fails.

[0008] The first approach is outlier rejection. A set of constraints is used to evaluate how likely it is that when a feature is found it is the same one as found previously. If the feature has moved from one side of the camera to the other, for example, it is unlikely to be the same unless the camera is moving very fast, and is rejected as a match. If it is close to the previous location, then it is likely to be the same feature and is accepted. Accepted features are passed to the bundle adjuster, rejected ones are not. Outlier rejection is another highly computationally expensive process, and for some SLAM systems is the largest computational component.

[0009] The second approach is Visual-Inertial Odometry. This is a system that uses the features located by the feature extractor in a different way. It uses a second source of motion information, a measure of linear acceleration from an inertial sensor, along with tracking features, to predict the velocity of the camera, rather than the position. This velocity measure can then be integrated over time and used in combination with the bundle adjuster to compensate for convergence failure. However, integrating VIO will accumulate a position error over time, and since this approach to SLAM relies on metric measurements of position this will cause failure over longer integration times. Due to VIO and bundle adjustment using the same features, feature extraction is a single point of failure for the entire system. [0010] Another weakness of the feature extraction front end is that the size of the features means that the data is relatively low dimensional for a single feature, and as such, there is a high probability of multiple parts of the image matching the feature, especially in aliased environments, such as a hotel corridor with identical doors that are evenly spaced. In these environments, it is possible for the bundle adjuster to converge to an incorrect location.

[0011] Loop closure is another weakness of the state of the art. When the moving camera traverses a complete loop and returns to the same location from a different direction the system must identify that it has returned to the same location. As the system is metric, it must also make sure that the map is consistent with the same location at the same place. Due to accumulated errors in the bundle adjustment process, this is rarely true, and there is usually a metric error between the representations of the location at the two ends of the loop. The system must then go back though all the features it stored around the entire loop and adjust them to compensate for and remove this error. This loop closure process is both computationally expensive and prone to error.

[0012] Computational complexity for algorithms that can cope with such environments and problems is very high, limiting the platforms they can be deployed on. Additionally, memory consumption for generated maps is very high, in the order of hundreds of megabytes to multiple gigabytes.

[0013] It is thus appreciated that a method and system for localization and mapping that enables an agent to understand the structure and identity of a space and the objects within it, which is less error-prone and less computationally and memory intensive, is required.

SUMMARY OF INVENTION

[0014] This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description.

[0015] According to a first aspect of this disclosure, a computer implemented method of parsing a multi-dimensional space is provided. The method is based on a series of observations and displacements performed by an agent in the space, to find an attribute of the space. The method comprises: making a first observation from a first location of the agent in the space, wherein the first observation includes data descriptive of a first portion of the space in the local vicinity of the first location; comparing the first observation to a set of stored observations and displacements to identify a first stored observation of the set of stored observations and displacements that is most similar to the first observation; determining a hypothesis of the attribute of the space based on the first stored observation, wherein the first stored observation is associated with the hypothesis; retrieving a hypothesis subset of the set of stored observations and displacements, wherein the hypothesis subset includes at least the first stored observation, a predicted observation and a predicted displacement required to reach the predicted observation, wherein the predicted observation and the predicted displacement are also associated with the hypothesis and testing the hypothesis. The hypothesis is tested by: moving the agent to a second location in the space based on a movement function, wherein the movement function is dependent on the predicted displacement of the hypothesis subset; making a second observation from the second location of the agent in the space, wherein the second observation includes data descriptive of a second portion of the space in the local vicinity of the second location; and comparing the second observation with the predicted observation to obtain an observation comparison measure, and/or comparing an actual displacement between the first and second location to the predicted displacement to obtain a displacement comparison measure; adjusting, maintaining or confirming the hypothesis based on the observation comparison measure and/or the displacement comparison measure; wherein confirming the hypothesis comprises: determining that a hypothesis confirmation condition is met; and finding the attribute of the space.

[0016] The movement function may comprise: a first movement component which is dependent on the predicted displacement of the hypothesis subset; and a second movement component which is dependent on the predicted observation of the hypothesis subset, wherein the first movement component is weighted according to a distance remaining of the predicted displacement , such that the first movement component weakens as the agent moves along the predicted displacement, and wherein the second movement component is weighted according to the predicted observation , such that the second movement component strengthens as the agent approaches the predicted observation.

[0017] The method may include measuring the actual displacement travelled from the first location to the second location.

[0018] If the agent reaches an end of the predicted displacement, or within a displacement-threshold-distance from the end of the predicted displacement, the first movement component of the movement function is weighted as zero, such that the first movement component ceases to contribute to the movement function.

[0019] The second movement component may comprise an expected direction and a magnitude to the predicted observation, wherein the direction and magnitude are obtained by: making a transitional observation away from the first location, after or during the agent moving; and performing a transitional comparison of the transitional observation to the predicted observation, to obtain the direction and magnitude to the predicted observation; and wherein the second movement component is weighted according to the transitional comparison, such that a stronger comparison with the predicted observation results in a stronger weighting of the second movement component.

[0020] The method may include the second movement component including the direction and magnitude being updated repeatedly as the agent moves away from the first location, such that the method comprises making a plurality of transitional observations.

[0021] The method may include stopping the agent at the second location using the movement function, wherein the second location is: a location of one of the transitional observations of the second movement component of the movement function, wherein the transitional comparison of the one of the transitional observations is indicative of a best match with the predicted observation from the plurality of transitional observations; and/or a location at which the magnitude of the second movement component function is equal to or falls below a magnitude threshold. The one of the transitional observations at the second location may be the second observation, and the transitional comparison indicative of the best match may be the second observation.

[0022] The observation comparison measure may comprise one or more of: a first observation comparison measure component; a second observation comparison measure component; a third observation comparison measure component; and a fourth observation comparison measure component; wherein the first observation comparison measure component is a similarity measure indicative of a similarity between the second observation and the predicted observation; wherein the second observation comparison measure component is a measure indicative of the orientation of the predicted observation with respect to the second observation; wherein the third observation comparison measure component is a vector from the second observation towards the predicted observation; and wherein the fourth observation comparison measure component is a second similarly measure indicative of a similarity between the second observation and the predicted observation.

[0023] The observation comparison measure may comprise the first, second and third observation comparison measure components. This effectively provides the method with a way of determining similarity between compared observations, an orientation change between compared observations, and a direction and magnitude, such as in the form of a vector, from a location of the agent to the location of a compared observation.

[0024] The observation comparison measure may additionally comprise the fourth observation comparison measure component. This provides redundancy and can advantageously be used to discriminate the first observation comparison measure component from environmental factors and features.

[0025] The first observation comparison measure component may be formed by an observation similarity function that takes the inner product of the second observation and the predicted observation, wherein the second observation and the predicted observation are vectors, and in particular unit vectors.

[0026] The third observation comparison measure component may be formed by: splitting the predicted observation into a first plurality of sub-regions; obtaining the first and second observation comparison measure components for comparisons between the first plurality of sub-regions and a second plurality of sub regions of the second observation, such that each of the first plurality of sub-regions is associated with a first and a second observation comparison measure component; and aggregating the first and second observation comparison measure components to form the vector from the second observation to the predicted observation.

[0027] Adjusting, maintaining or confirming the hypothesis based on the test of the hypothesis may comprise: adjusting the hypothesis if the observation comparison measure falls below a first observation threshold level; maintaining the hypothesis if the observation comparison measure exceeds the first observation threshold level; and confirming the hypothesis if the observation comparison measure exceeds a hypothesis confirmation observation threshold level, wherein the hypothesis confirmation observation threshold level is the hypothesis confirmation condition; or: adjusting the hypothesis if the displacement comparison measure falls below a first displacement threshold level; maintaining the hypothesis if the displacement comparison measure exceeds the first displacement threshold level; and confirming the hypothesis if the displacement comparison measure exceeds a hypothesis confirmation threshold level, wherein the hypothesis confirmation threshold level is the hypothesis confirmation condition; or: combining the observation comparison measure and the displacement comparison measure to form a two-dimensional similarity measure; adjusting the hypothesis if the two-dimensional similarity measure falls below a first two-dimensional similarity measure threshold level; maintaining the hypothesis if the two-dimensional similarity measure exceeds the first two- dimensional similarity measure threshold level; and confirming the hypothesis if the two-dimensional similarity measure exceeds a hypothesis confirmation two- dimensional similarity measure threshold level, wherein the hypothesis confirmation two-dimensional similarity measure threshold level is the hypothesis confirmation condition.

[0028] The set of stored observations are associated with a plurality of hypotheses, and include a plurality of hypotheses subsets each including at least one predicted observation and predicted displacement related to a particular hypothesis.

[0029] Adjusting the hypothesis may comprise: rejecting the hypothesis; moving the agent from the second location to the first location according to a negative displacement of the actual displacement, selecting a new hypothesis of the plurality of hypotheses based on comparing of the first observation to the set of stored observations and displacements to identify a next stored observation of the set of stored observations and displacements that is next-most similar to the first observation.

[0030] The hypothesis subset may include a plurality of predicted observations and a plurality of predicted displacements predicted to be required to move between the predicted observations.

[0031] Maintaining the hypothesis may comprise: retrieving a next predicted observation and a next predicted displacement from the hypothesis subset; and repeating testing of the hypothesis, with respect to the next predicted observation and the next predicted displacement.

[0032] The method may comprise repeating testing of the hypothesis for the plurality of predicted observations and the plurality of predicted displacements of the hypothesis subset until the hypothesis is adjusted or confirmed.

[0033] The attribute of the space to be found may be an object or image in the space, wherein: the hypothesis is indicative of a predicted object or image, such that the predicted observation and the predicted displacement associated with the hypothesis are associated with the predicted object or image; finding the attribute of the space comprises: identifying the object or image in the space as the predicted object.

[0034] The attribute of the space to be found may be a destination in the space, wherein: the hypothesis is indicative of a path to the destination, such that the predicted observation and the predicted displacement associated with the hypothesis are associated with an expected path to the destination; finding the attribute of the space comprises: reaching the destination in the space.

[0035] The space may be a physical or logical space and is two-dimensional or three- dimensional.

[0036] The method may further comprise extracting a set of low-level spatial features from the physical or logical space; wherein determining the hypothesis based on the set of stored predicted observations and displacements comprises processing the first observation and the low-level spatial features to determine the hypothesis, wherein the set of low-level spatial features are assigned a weighting factor in the determination of the hypothesis.

[0037] The method may include processing the second observation and/or nth observation to test the hypothesis relating to the physical or logical space, extracting a second or nth set of low-level spatial features from the physical or logical space; and processing the second or nth observation and the second or nth set of low-level spatial features to test the hypothesis, wherein n is a positive real integer.

[0038] According to a second aspect of this disclosure, there is provided a system comprising: a processor; a memory; and a sensor or virtual sensor, configured to capture spatial data descriptive of a portion of space in the local vicinity of the sensor or virtual sensor, the memory having instructions stored thereon, which, when executed by the processor, cause the system to perform the method of the first aspect outline above.

[0039] The system may be a robot or vehicle comprising the sensor, wherein the robot or vehicle is the agent configured to operate in a physical space, and further comprises: a controllable movement module configured to cause the robot or vehicle to move within the physical space; and wherein the sensor is a camera, LIDAR sensor, infrared sensor, radar, tactile sensor or any other sensor configured to provide spatial information.

[0040] The system may be a computer system comprising the virtual sensor, wherein the computer system is configured to operate on a logical space, wherein the agent is represented by a point in the logical space. [0041] The logical space may be an image, the point in the logical space is a pixel of the image, and the virtual sensor is configured to capture a portion of image data in the local vicinity of the pixel.

[0042] According to a third aspect of this disclosure, there is provided a computer program stored on a non-transitory computer-readable medium, which, when executed by a processor, is configured to cause the processor to execute the method according to the first aspect set out above.

[0043] According to a fourth aspect of this disclosure, there is provided a computer implemented method of parsing a physical or logical space, based on a series of observations and displacements performed by an agent in the physical or logical space, to determine an attribute of the physical or logical space, the method comprising: selecting a hypothesis of the attribute of the physical or logical space, based on a comparison between a current observation of the agent in the physical or logical space and a current predicted observation of a stored set of predicted observations and displacements associated with the hypothesis; wherein the current observation is recorded from a current location of the agent in the physical or logical space and includes data descriptive of a current portion of the logical or physical space in the local vicinity of the current location; retrieving a next predicted displacement and a next predicted observation from the set of predicted observations and displacements associated with the hypothesis, with respect to the current predicted observation; and iteratively: comparing the next predicted observation associated with the hypothesis and the current observation to obtain an observation comparison measure indicative of the similarity between the next predicted observation and the current observation; determining a direction and magnitude of a movement required to reach the predicted observation based on the observation comparison measure; moving the agent according to the determined movement and the next predicted displacement such that the agent is displaced from the current location to a next location in the physical or logical space; making a next observation from the next location of the agent in the logical or physical space, wherein the next observation includes data descriptive of a next portion of the logical or physical space in the local vicinity of the next location; and setting the next observation as the current observation and the next location as the current location; and repeating the method until an observation comparison condition is reached wherein the agent is at a final location in the physical or logical space; measuring the actual displacement from the original current location to the final location in the physical or logical space; comparing the actual displacement to the next predicted displacement to obtain a displacement comparison measure; determining whether a hypothesis confirmation condition is met; wherein if the hypothesis confirmation condition is not met: setting the next predicted observation as the current predicted observation, the next observation as the current observation, and the next location as the current location; retrieving a new next predicted displacement and a new next predicted observation from the set of predicted observations and displacements associated with the hypothesis, with respect to the current predicted observation and repeating the method until the hypothesis confirmation condition is met; and determining the attribute of the physical or logical space based on the meeting of the hypothesis confirmation condition.

[0044] According to a fifth aspect of this disclosure, there is provided: a computer implemented method of parsing a physical or logical space, based on a series of observations and displacements performed by an agent in the physical or logical space, to determine an attribute of the physical or logical space, the method comprising: recording a first observation from a first location of the agent in the logical or physical space, wherein the first observation includes data descriptive of a first portion of the logical or physical space in the local vicinity of the first location; processing the first observation to determine a hypothesis based on a set of stored predicted observations and predicted displacements, wherein each of the set of stored predicted observations and predicted displacements are associated with one or more hypotheses; determining a direction and magnitude of a movement required based on a predicted observation associated with the hypothesis; moving the agent according to the movement required, such that the agent is displaced from the first location to a second location in the physical or logical space; recording a second observation from the second location of the agent in the logical or physical space, wherein the second observation includes data descriptive of a second portion of the logical or physical space in the local vicinity of the second location; processing the second observation to test the hypothesis relating to the physical or logical space; adjusting or maintaining the hypothesis based on the processing of the second observation; and determining whether a hypothesis confirmation condition is met.

[0045] Processing of the first observation to determine the hypothesis may comprise: comparing the first observation to the predicted observations of the set of stored predicted observations to determine an similarity measure between the first observation and the predicted observations of the set of stored predicted observations; and retrieving the hypothesis corresponding to the predicted observation of the set of stored predicted observations having the strongest similarity measure.

[0046] According to a sixth aspect of this disclosure, there is provided a computer implemented method of generating a map of a physical or logical space, based on a series of observations and displacements performed by an agent in the physical or logical space, the method comprising recording a first observation from a first location of the agent in the logical or physical space, wherein the first observation includes data descriptive of a first portion of the logical or physical space in the local vicinity of the first location; moving the agent by a first displacement such that the agent is displaced from the first location to a second location in the physical or logical space; generating a second observation from the second location of the agent in the logical or physical space, wherein the second observation includes data descriptive of a second portion of the logical or physical space in the local vicinity of the second location; recording the second observation; recording the first displacement from the first to the second observation; recording a negative first displacement from the second observation to the first observation; and repeating this process for at least of n-1 displacements, n observations and n-1 negative displacements to generate a set of connected n-1 displacements and n observations that define a map of the physical or logical space, wherein n is a positive real integer.

[0047] Recording an observation and a displacement may be considered to be making an observation and a displacement by the agent.

[0048] Prior to recording the second or nth observation, the method may comprise: comparing the nth observation to the previous n-fth observation to determine a observation similarity measure between the nth observation and the n-1Vn observation; comparing the observation similarity measure to a predefined maximum similarity threshold; and if the similarity measure does not exceed the maximum similarity threshold: recording the nth observation; recording the n-1th displacement from the n-fth to the nth observation; recording a negative n-1th displacement from the nth observation to the n-1th observation; or if the similarity measure exceeds the maximum similarity threshold: moving the agent by a further displacement such that the agent is displaced from an nth location to an n+fth location in the physical or logical space; generating a n+1Vn observation from the n+1Vn location of the agent in the logical or physical space, wherein the n+1th observation includes data descriptive of a n+1th portion of the logical or physical space in the local vicinity of the n+fth location; comparing the n+7th observation to the previous n-7th observation to determine a observation similarity measure between the n+7th observation and the n-7th observation; comparing the observation similarity measure to the predefined maximum similarity threshold; and repeating this process until the predefined maximum similarity threshold is not exceeded.

[0049] The method may comprise: forming an identity from the n observations and the n-1 displacements, wherein the identity includes at least a subset of the n observations and n-1 displacements; and storing the identity.

[0050] The method may further include, associating or labelling the identity and the corresponding subset of observations and displacements that form it with an attribute of the space.

[0051] A plurality of identities from the n observations and n-1 displacements may be formed.

[0052] The map and/or identities may include more or less than n-1 displacements, as an observation may have more than two displacements to other observations, for example, imaging a set of three observations where each connects to the other two, forming a triangle with three observations and three displacements. It is understood that for larger numbers of observations the number of displacements can be higher than the number of observations.

[0053] According to a seventh aspect of this disclosure, there is provided a method of navigating a map of a physical or logical space generated according to the sixth aspect set out above, the method comprising: obtaining an overall target observation, wherein the target observation is an observation of the set of n observations and n-1 displacements; making a first observation from a first location of the agent in the logical or physical space, wherein the first observation includes data descriptive of a first portion of the logical or physical space in the local vicinity of the first location; comparing the first observation to the set of n observations and n-1 displacements to identify a first target observation of the set of n observations and n-1 displacements, wherein the first target observation is the observation connected to the overall target observation in the map of the physical or logical space that is most similar to the first observation; determining a first movement from the first observation to the first target observation, based on the comparison between the first observation and the first target observation; relocalising the agent to the first target observation by moving the agent according to the first movement, and iteratively: moving the agent through the n-1 displacements and n observations towards the overall target observation in the map by: moving the agent according to the n-1 displacements; and making transitional observations at the n observations; comparing the transitional observations to the n observations; comparing measured displacements to the n-1 displacements; and adjusting the moving of the agent based on the comparisons until the overall target observation is reached.

[0054] According to an eighth aspect of this disclosure, there is provided a computer- implemented method of determining a similarity between a portion of physical or logical space navigable by an agent and stored spatial data for localisation of the agent in the physical or logical space, the method comprising: sequentially: recording a series of observations from respective locations of the agent in the physical or logical space, wherein each observation includes data descriptive of a respective portion of the logical or physical space in the local vicinity of the agent; moving the agent between the respective locations and recording a series of displacements between the respective locations; comparing each of the series of observations with a set of previously stored observations to obtain an observation similarity measure for each observation with respect to one or more of the previously stored observations; comparing each of the series of displacements with a set of previously stored displacements to obtain a displacement similarity measure for each displacement with respect to one or more of the previously stored displacements; determining that the series of observations and/or displacements are similar to previously stored set of observations and/or displacements if the observation similarity measure and/or displacement similarity measure passes a confidence threshold.

[0055] The method may include combining the observation similarity measure and the displacement similarity measure to produce a two dimensional identity comparison measure; and processing the identity comparison measure to determine a type of similarity between the observations and displacements and the previously stored observations and displacements.

[0056] According to a ninth aspect of this disclosure, there is provided a computer- implemented method for performing simultaneous localisation and mapping in a logical or physical space, the method comprising: recording a first observation from a first location in the logical or physical space, wherein the first observation includes data descriptive of a first portion within the logical or physical space; performing a first displacement from the first location to an unknown second location in the logical or physical space; recording a second observation from the second location, wherein the second observation includes data descriptive of a second portion within the logical or physical space; repeating the method for n observations and n displacements, wherein n is a positive real number, to form a set of sequential observations and a corresponding set of displacements; comparing the set of sequential observations and the corresponding set of displacements with a stored set of observations and a stored set of displacements, wherein the stored sets are captured in a closed loop, wherein the comparing includes comparing using at least one of a displacement comparison measure and one or more observation comparison measures to determine whether a feature corresponding to the stored set exists within the space.

[0057] This method is effectively used for parsing a multi-dimensional space based on a series of observations and displacements performed by an agent in the space, to find an attribute of the space. The method includes making sequential observations and displacements from locations of the agent in the space, and comparing the observations and displacements to a set of stored observations and displacements to identify a hypothesis of the attribute of the space and to test the hypothesis, by obtaining an observation comparison measure, and/or a displacement comparison measure, and adjusting, maintaining or confirming the hypothesis based on the observation comparison measure and/or the displacement comparison measure.

[0058] Each of the above aspects relate to an agent in a space which is configured to move and observe the space, in a minimalistic manner such that a network of connected observations and displacements may describe the space in a map.

Current observations and displacements made by the agent and compared against stored observations and displacements on the map may influence the agent's behaviour, in terms of movement and function. In this way, the agent is capable of observing a space for image and object recognition purposes at the same time as navigating and/or exploring a space.

[0059] The agent may be a real object, such as a robot, vehicle, autonomous vehicle, unmanned aerial vehicle or the like, but is not limited to such possibilities.

[0060] A group of agents may be used together, and may communicate with a computer system or the like to update a global map or resource based on the spaces in which the different agents reside. BRIEF DESCRIPTION OF FIGURES

[0061] Embodiments of the invention will be described, by way of example, with reference to the following drawings, in which:

[0062] Figure 1 is a schematic diagram of a physical space to be parsed by an agent;

[0063] Figure 2 is a schematic diagram of a physical/logical space to be parsed by an agent;

[0064] Figure 3 is a flow diagram outlining a method of finding an attribute of a space;

[0065] Figure 4 is a detailed flow diagram outlining a section of the method of finding an attribute;

[0066] Figure 5 is a schematic diagram outlining a system for performing the methods;

[0067] Figure 6 is a schematic diagram of a function performed by the agent in various methods;

[0068] Figure 7 is a schematic diagram showing various ways in which an agent can move according to the methods;

[0069] Figure 8 is a schematic showing an identity which may be used to generate a map of a space; and

[0070] Figures 9 and 10 show various schematic representations of vectors and matrices obtained in various methods.

[0071] Common reference numerals are used throughout the figures to indicate similar features.

DETAILED DESCRIPTION

[0072] Embodiments described herein relate to a computer implemented method and system for parsing a multi-dimensional space and determining the structure of the space, or one or more attributes thereof. The approach taken by the embodiments described herein treats the problem of understanding space as a closed loop problem, wherein sensory data from a sensor or a virtual sensor, describing the environment of an agent, directly drives changes in the behaviour of the agent. [0073] The term 'agent' is used to refer to either or both of a physical agent that exists in a real-world physical space, such as a vehicle or robot, and a non-physical agent, that exists in a logical space, such as a point or pixel in an image or map.

[0074] The agent is capable of moving within its respective space. In the physical space, the agent moves from activation of a movement module, which may be an actuator or motor for example. In the logical space, the agent moves from a first point or pixel to a second point or pixel. The agent may be real or virtual. A real agent, such as a robot, occupies an area in the space. A virtual agent is a projection onto the space, and does not actually exist in the space. For example, a virtual agent may be the projection of a center point of the field of view of a camera that observes a two-dimensional scene. The camera may move and/or rotate to change the center point of the field of view on the scene and thus the location of the virtual agent. This is explained in more detail below.

[0075] A physical space refers to any three-dimensional space that may be physically reached or traversed by an object, vehicle, robot or any other agent in the real world. The three-dimensional space may comprise one or more other physical or material objects. The three-dimensional space may also encompass an interval of distance (or time) between two points, objects, or events, with which the agent may interact when traversing the physical space.

[0076] A logical space refers to a space, such as a mathematical or topological space, with any set of points. A logical space may thus be an image or map or a concept map, for example. A set of points may satisfy a set of postulates or constraints. The logical space may correspond with the physical space as described above.

[0077] Data is captured with respect to the position of the agent in the space, and the data captured describes the environment of the space in the vicinity of the agent. The capturing of data is performed by a sensor in the physical space, such as a camera, radar, tactile sensor, LIDAR sensor, infrared sensor or the like. The capturing of data is performed by a virtual sensor in the logical space, which retrieves data of the logical space within the vicinity of the agent.

[0078] In the physical space, there is an observability problem in that not all the physical space may be observable by the agent at any given time. The physical space may be too large for the sensor to observe, and/or the physical space may include objects, terrain or the like that occludes regions of the physical space. [0079] In the logical space, all of the logical space may be observable at once. For example, when the logical space is an image, the entirety of the image may be stored on a memory accessible by the agent.

[0080] However, in the logical space, it is not necessary, and is more efficient, if the agent does not observe the entire logical space at once. For this reason, the virtual sensor may only obtain a portion of the logical space, thus simulating the sensor of the physical space in that only the vicinity of the agent in the logical space is captured and/or retrieved by the virtual sensor.

[0081] Thus, in both scenarios of an agent in a logical space and an agent in the physical space, it is not necessary for the agent to observe the entirety of the respective space, and it is advantageous computationally if the agent only observes a portion of the respective space in the vicinity of the agent.

[0082] When the agent is a non-physical agent in the logical space, it is not necessary that the vicinity of the agent is observed directly by a sensor or a virtual sensor. For example, the vicinity of the agent may be a portion or region of a prerecorded image that defines the overall logical space.

[0083] Data captured by the sensor or virtual sensor observing the space in the vicinity of the agent is defined as observation data. This observation data is used to make an 'observation'. An observation is thus the result of processing the observation data in a way that concisely describes the environment in the vicinity of the agent.

[0084] In the physical space, an observation may be represented by a matrix or vector that provides spatial information derived from observation data. The observation data may be an image or point cloud data of the surroundings of the agent, for example.

[0085] In the logical space, an observation may be represented by a matrix or vector that provides spatial information in the vicinity of the agent. The observation data from which this observation is derived may be a collection of pixels or points from the logical space around the agent. For example, the observation data could be a matrix of pixels that are within an observable threshold distance away from the agent.

[0086] The agent may make a plurality of different observations at different locations in the space. The agent moves between these locations to make the observations. The vector between two observations is defined as 'a displacement', which has both a magnitude and direction. Thus, the agent moves between two particular locations where observations are made by travelling along the displacement between the two particular locations.

[0087] Each of the observations and displacements made by the agent within the space may be stored in a memory associated with the agent. If the agent makes a series or sequence of observations and displacements in the space, the series or sequence may be stored together as a set of observations and displacements. The sequence of observations and displacements may form an 'identity'. An identity may be descriptive of a particular feature or attribute of the space in which it was found. The terms attribute and feature are used interchangeably henceforth.

[0088] For example, in a physical space, an identity may be descriptive of an attribute such as a particular object or a path to a particular destination within the space. The observations in the set that form the identity indicate how the space is perceived by the agent and thus how the particular feature is perceived. For example, if there is a particular object such as a chair in the space, the identity of the chair may include several observations taken from different locations of portions or aspects of the chair. Similarly, if there is a particular destination in the space, the identity may include several observations taken from locations on a path to the destination. The displacements in the set that form the identity indicate how the agent moves between the locations of the observations. For example, a first observation of a chair in the space may be made from a position near a rear leg of the chair. A second observation of the chair in the space may be made from a position near a front leg of the chair. A first displacement of the identity is then a displacement required to move from the position near the rear leg of the chair to the position near the front leg of the chair.

[0089] An example identity is illustrated in Figure 1 . Figure 1 shows a series of observations 101 connected by a series of displacements 102 in an exemplary room space comprising a door and a central obstacle. This exemplary room space may be a physical space, such as an apartment in the real world. The observations 101 may be captured using a camera on a robot. The displacements 102 may be made by moving the robot. In this example, the identity represents a path to the door, which may be considered to be a destination. Each of the observations 101 provide data descriptive of the environment from the location at which the observation is made.

[0090] Although the displacements are illustrated as being one-directional in Figure 1 , it is to be understood that a corresponding set of negative displacements may also be recorded such that the identity comprises the observations 101 , and a set of displacements 102 and negative displacements linking the observations.

[0091] The attribute of the space of the identity as illustrated in figure 1 may be the destination, such as the door. This identity can thus be used for the purposes of navigating in the room, around the central obstacle, and to the door.

[0092] A second example of an identity is illustrated in Figure 2. Figure 2 shows a series of observations 201 connected together by a series of displacements 202 on a chair. The chair may be three-dimensional in a physical space such as the real-world, or may be two dimensional in a logical space, such as in an image. As with figure 1 , the displacements 202 may also include opposite negative displacements.

[0093] A camera may be responsible for capturing the observations 201 and performing the displacements 202 to obtain the identity as seen in Figure 2, for example, in the physical space. In the logical space, this may be performed by a virtual agent.

[0094] In the case of a camera in the physical space, the camera may or may not be in a fixed position. If in a non-fixed position with respect to the space, the camera may move within the space. For example, the camera may be attached to a robot. In this case, the agent may be the robot (or camera), and observation data is recorded at the location of the agent simply by recording an image or images of the surroundings of the robot or camera. If in a fixed position, the camera may rotate or zoom or the like so as to focus on different parts of the chair. In this case, the aim and focus of the camera, (i.e. the direction of gaze) in terms of the visual field of view of the camera may represent the agent. In this case, the agent may thus be defined as a centre point or projection of another certain pixel in the field of view of the camera, for example. The camera does not move in a translational manner, but the agent 'moves' when the camera is zoomed or rotated, because such actions modify the position of the centre point or certain pixel in the field of view of the camera with respect to the scene/image being observed. The location of the agent thus does not have to correspond to the location of the camera. When fixed, the camera may not displace between the observations to obtain the displacements 202. Instead, the displacements may be made and stored as the distance between two fixed points in the field of view of the camera across two observations. The displacements can be performed by rotating the camera to 'move' the agent, by moving the centre point of the field of view of the camera. [0095] For example, the camera may first capture an image centred on the chair leg. This image is then processed into a first observation. The location of the agent is deemed to be the centre point of the field of view of the camera with respect to the first image. The camera may then pan upwards by rotating, and capture and process a second image, of the back rest of the chair. The second observation is thus processed from the image of the back rest. The location of the agent for this second observation is deemed to be the centre point of the field of view of the camera with respect to the second image, and the displacement between the first observation and the second observation is the distance, in pixels and/or relating to the size of the rotation, between the centre point of the field of view with respect to the first image and the centre point of the field of view with respect to the second image. This may be estimated using visual inertial odometry, for example.

[0096] When the camera is not fixed, the agent is the camera itself (or the device to which the camera is attached). In this example, the camera/device moves to a location, makes an observation at that location, and then performs a displacement. The displacements are recorded, using odometry for example, as will be understood.

[0097] In the case of a logical space, figure 2 may represent an image of a chair. In this example, the entire image is stored, so no observability problem exists and it is possible to observe the entire image at once. However, to improve computational efficiency, logical space is treated in the same way as physical space, in that the entire image is not dealt with at once and instead, smaller observations of portions of the image are made. In particular, a portion of the image plane is observed, for example, a portion including the chair leg. The size of the portion may be fixed or may be dependent on the size of the image. As with the fixed camera example in the physical space, the location of the agent is deemed to be a particular point in the portion of the image, for example, a particular pixel such as the central pixel of an image portion.

[0098] The 'agent' or virtual agent in this case, may then perform a displacement by 'moving' by a number of pixels across the image plane, before making a second observation. In reality, this involves merely acquiring a second portion of the image plane from memory, whereby the second portion is centred around the new location of the agent (the pixel the virtual agent has 'moved' to). Thus, in the logical space, the agent is a tool for selecting different portions of an image based on a fixed point in the image. Moving the virtual agent includes translating from the pixel at which the virtual agent was previously located to a different pixel. [0099] When referring to an 'agent' it should therefore be understood that an agent can be three things. Firstly, an agent can be a physical device that can move, such that the agent physically moves to a location in physical space to make an observation at the location of the device. In this case, the agent performs displacements between observations by moving the physical device, and observation data corresponds to data captured by the agent at its present location. Secondly, the agent can be a projection of a physical device that is fixed. In this case, observations are made in different orientations of the fixed physical device, and the agent is a projection of a point in the field of view of the physical device related to the orientation of the physical device. For example, the agent is located at a centre point of a field of view of the fixed physical device. Displacements in this case are measured based on the distances between projections of the point in the field of view of the physical device caused by changes in orientation of the physical device. Thirdly, the agent may be a virtual agent, in a logical space. In this case, the agent is located at a point or pixel in the logical space. The point or pixel designates a portion of the space around it which is corresponds to observation data. For example, the agent may be located at a central pixel of a portion of space corresponding to observation data for an observation. Displacements are measured as the distances between pixels or points in the logical space.

[00100] Thus, when referring to an agent and particularly to the 'location of the agent' in the foregoing description, it is noted that any of the above definitions of an 'agent' may apply. The location of the agent is not required to be the location of a physical device. Similarly, when referring to an agent performing an action, such as moving, or making an observation, the above definitions apply, such that a physical device is not required to move, and an observation may be made by a physical device or computing device that is not necessarily the agent itself.

[00101] Returning to figure 2, the attribute of the space defined by identity formed by the series of displacements 202 and observations 201 may be an identification of the feature, which in this case, is the chair.

[00102] Thus, figures 1 and 2 show that identities can be formed in both physical and logical space, in two or three dimensions, and for the purpose of identifying objects, such as a three-dimensional chair, identifying images or features of images, such as a two-dimensional chair, or for the purpose of navigating a three-dimensional space to reach a destination. It is to be understood that there are other uses for identities and object/image recognition and navigation are merely examples. [00103] Several identities such as those in figures 1 and 2 may be stored in a set of stored observations and displacements from previous experiences of one or more spaces. It is not necessary for the identities to be labelled, meaning in the above examples, it is not necessary that the identity corresponding to the chair is labelled as a chair or is even known to correspond to a chair. Rather, once the set of observations and displacements are stored as an identity, the agent is able to use this information to locate and identify matches to the identity in other areas of the space or in other spaces entirely. It is not necessary for the system or method to understand the real-world feature to which the identity relates.

[00104] In some embodiments described below, an identity may be labelled according to the feature or attribute of the space that it represents. In the above example, the identity corresponding to the chair may thus be labelled as a chair. The process of labelling identities within the set of stored observations and displacements may be performed as part of a general training process, wherein the training process is performed according to existing techniques as will be understood by the skilled person. For example, various machine-learning techniques may be used, including supervised and unsupervised learning processes, the use of neural networks, classifiers, and the like.

[00105] For example, the stored set of observations and displacements may be acquired from test spaces, such as test images, which include or show one or more known features. For example, a test image or images of a chair may be presented to the agent such that the identity formed from the image or images and stored in the set of stored observations and displacements is known to correspond to a chair and is labelled as such. The process of acquiring the set of stored observations is set out in more detail later.

[00106] Using a set of observations and displacements to effectively describe a feature of a space, rather than an entirety of a map or image of the space is computationally efficient, since the observations and displacements only include respective portions of the feature and thus require less memory and computation to identify it in a part of a space. In addition, the observations and displacements can be computed by using different data, such as a vector encoded from the output of a set of spatial filters applied to the visual data for observations, and the local temporal correlation of low level features in the case of displacements. This removes a common failure mode and thus enables the two parts of the system (the observations and the displacements) to compensate for weaknesses in the other, providing diversity. In the application area of 3D spatial SLAM the system also performs not just localisation and mapping, but additionally navigation and path planning intrinsically, removing the need for additional components to be added to achieve a full implementation in the real world.

[00107] Compared with standard SLAM, the methods and systems set out here are more robust to environmental factors and occlusions. The methods and systems set out here also have the advantage of storing the minimum set of measurements required to navigate and observe a particular space. Observations are made in a space according to the complexity and/or changes within a space, such that the methods and systems are adapted to perform optimally in any space. For example, in a wide-open field or area of little information and features, fewer observations will be made and stored when compared to a feature-rich environment. As the method does not involve the tracking of features or objects that subtend a small part of the visual field, but instead entirely uses the properties of a majority of the full sphere of solid angle, occlusions or changes to parts of the visual scene have less impact on the ability of the system to complete a task, when compared to traditional systems and approaches.

[00108] The feature or attribute to which a set of stored observations and displacements relates may be identified in a different area of the same space, or in a new space entirely. For example, in a physical space, such as a living room or dining room, the set of stored observations and displacements associated with the chair may be used to identify an identical or similar chair in another part of the living room or dining room. Additionally, the set of stored observations and displacements may be used to identify an identical or similar chair in an entirely different space, such as in a separate building.

[00109] Similarly, a destination in a space, such as a store or landmark, may be navigated to from a first known or previously visited location in the world from a stored set of observations and displacements linking the starting point to the destination. Additionally, the destination in a space may be navigated to from an unknown area in the world or an unknown starting point from the set of observations and displacements.

[00110] Identifying an attribute of a space in this way relies on making comparisons between the stored set of observations and displacements and current observations and displacements made in the particular space. The following part of the description sets this process out in more detail. In this following part of the description, stored observations and displacements are referred to as predicted observations and displacements, and target observations and displacements. It is to be understood that these terms define the same technical features, and are different simply to give context as to why or when they are being used. Similarly, current observations from the space are referred to as first, second and transitional observations. Again, these terms define the same technical feature, which is an observation made by the agent in the space in which the agent is residing, but are labelled differently to provide context as to why or when they are being made or used. The same terminology is applied to displacements.

[00111] A method in which this process of identifying/determining an attribute of a space is performed, using existing knowledge in the form of a stored set of observations and displacements, is explained in detail below with reference to Figure 1. A benefit of this method is that only portions of the space are required, in terms of current observations and displacements, to identify the attribute.

[00112] Figure 1 shows a flow diagram of a method 300 of determining an attribute of a space in which an agent can explore or move, according to various embodiments.

[00113] In the initial conditions of the method 300, an agent is in a space, and is able to observe a portion of the space through a sensor, virtual sensor or the like. The space may be previously explored by the agent or entirely unknown to the agent. The starting position may be known to the agent, or may be entirely unknown to the agent.

[00114] In a first step 301 , the agent makes an observation from its current location in the space of the agent in the space. The observation may be considered to be a current or first observation from a current or first location, although it is to be understood that it is not required that this observation is the very first observation in the space. Rather, 'first' is used here simply to disambiguate the current observation from later observations.

[00115] The first observation includes data descriptive of a first portion of the space in the local vicinity of the agent. For example, where the agent is a robot or vehicle, the first observation may be made using sensor data from a sensor such as a camera, radar, LIDAR or the like, wherein the sensor data is indicative of a view of the world from the robot's current location. The local vicinity of the agent is the local vicinity of the robot's current location. In a physical space, the extent of the local vicinity is determined by constraints of the sensor and the environment of the robot. For example, the sensor may have a limited range, such that data for the observation sensor data is only acquired for the environment of the space within that range.

Similarly, the environment of the robot may include one or more features that limit the observable surroundings, such as a wall or other obstruction that occludes the field of view of the sensor. The vicinity of the agent is thus not fixed, but may have a maximum distance from the location of the agent based on the constraints of the sensor. In logical space, the local vicinity of the agent is a portion around the location of the agent, and is smaller than the entirety of the space. Since the entire space may be stored, for example, if the space is an image, it is not necessary to obtain data from a sensor to make an observation. Rather, the portion of the space around the location of the agent is retrieved from the stored entire space. This 'virtual sensor' simulates the same effect as using a sensor in the physical space, wherein the observation only considers a portion of the entire space rather than the whole. The vicinity of the agent in the logical space may therefore be set based on a distance from the location of the agent. In the example where the space is an image, and the agent is located at a pixel in the image, the vicinity may be set by a number of pixels away from the pixel of the agent, for example.

[00116] Once the first observation has been made in the first step 301 , it is compared in a second step 302 to stored observations from a set of stored observations and displacements.

[00117] The comparison between the first observations and the stored observations produces an observation comparison measure, indicative of how similar each of the stored observations are to the first observation. The observation comparison measures for each stored observation are ranked; the highest observation comparison measure is identified, and the stored observation it corresponds to is retrieved. In this way, the stored observation that is most similar to the first observation is determined and selected. The process of comparing observations is set out in more detail later.

[00118] In a third step 303, a hypothesis is determined, relating to the stored observation that is most similar to the first observation. In particular, the stored set of observations and displacements include one or more identities, which form subsets of the stored set of observations and displacements. Each subset includes one or more observations and one or more displacements that are each associated with a particular attribute or feature to which the identity relates. In the third step 303, the attribute or feature to which the selected stored observation is associated, is determined. This attribute forms the basis of the hypothesis, which is effectively a prediction of what the agent is observing in the space. The prediction could be a two dimensional or three dimensional object or image, or a destination that can be navigated to, for example.

[00119] The stored set of observations and displacements may include several subsets of observations and displacements, wherein each subset is associated with a particular attribute, and thus a particular hypothesis. In an example, there is a subset related to the attribute 'chair', a subset related to the attribute 'table' and a subset related to the attribute 'door'. The comparison in the second step 302 is performed with respect to all of the observations in the stored set of observations and displacements and may result in the observation comparison measure being highest or strongest for a particular observation, wherein the particular observation is part of the subset related to the attribute 'door'. In the third step 303 the hypothesis thus becomes that the first observation is part of a door, or in other words, the attribute of the space that the agent has observed is a door in the space. The subset of stored observations and displacements relating to the attribute is referred to as a hypothesis subset.

[00120] In a fourth step 304, the observations and displacements of the hypothesis subset are retrieved. In particular, the stored observation that is most similar to the first observation is part of a hypothesis subset of stored observations and displacements as explained above. Furthermore, the observations and the displacements in the hypothesis subset are linked, such that they form a network of observations separated by displacements. The linkage between the observations and displacements in the hypothesis subset is stored in the set of stored observations and displacements, such that the network arrangement is preserved in memory. When retrieving the hypothesis subset of observations and displacements, the method includes retrieving an observation and a displacement that are connected to the stored observation that is most similar to the first observation. In other words, the neighbouring observation and the displacement required to reach it from the stored observation that is most similar to the first observation are retrieved from the hypothesis subset. This observation and the displacement become the predicted observation and predicted displacement, whereby, if the agent moves from its current location by the predicted displacement, it is expected, according to the hypothesis, that the agent will arrive at a location in the space where it can observe the predicted observation. [00121] It is to be understood that the terms 'predicted observation' and 'predicted displacement' simply refer to the subset of observations and displacements related to the determined hypothesis. Each of these observations and displacements are predicted, according to the hypothesis, to be present in the space the agent currently occupies.

[00122] In a fifth step 305, the hypothesis is tested. To test the hypothesis, the agent is sequentially moved along the network of stored observations and displacements that form the hypothesis subset, or in other words, the predicted observations and predicted displacements. At each iteration in this sequential process of moving the agent along the network, the agent is configured to repeatedly perform new observations, compare the new observations to the predicted observations, and/or compare the predicted displacements to actual displacements, and determine whether to maintain the hypothesis, reject the hypothesis, or confirm the hypothesis. This hypothesis testing is explained below in more detail with reference to steps 305- 1 to 305-5.

[00123] In a first step 305-1 of the hypothesis testing process, the agent moves from its current location, where it made the first observation, to a second location in the space based on a movement function. The movement function is dependent on a predicted displacement of the hypothesis subset. In particular, the movement function is dependent on the predicted displacement that is connected to the stored observation that is most similar to the first observation, identified from the linked network of observations and displacements that forms the subset. The second location is thus unknown to the agent until it has performed movement based on the movement function.

[00124] In a second step 305-2 of the hypothesis testing process, the agent makes a second observation from the second location of the agent in the space, wherein the second observation includes data descriptive of a second portion of the space in the local vicinity of the second location. For example, where the agent is a robot or vehicle, the second observation may be made in the same way as the first observation, using sensor data from a sensor such as a camera, radar, LIDAR or the like, wherein the sensor data is processed to become an observation indicative of a view of the world from the robot's position at the second location.

[00125] In a third step 305-3 of the hypothesis testing process, an actual displacement from the first location of the agent to the second location is determined. In physical space, the actual displacement may be estimated using odometry, for example. In logical space, the actual displacement may be measured according to known techniques, using vector or matrix calculations. For example, if the logical space is an image, the number of pixels between the first location and the second location may be determined as the distance. In a physical space, displacements are measured using an odometry system comprising visual inertial odometry combined with motoric odometry such as wheel odometry where applicable. The system provides interfaces for the input of visual inertial odometry and motoric odometry. Displacements indicate a physical or logical distance between pairs of observations. Odometry is stored in a coordinate system that is referenced to the rotation of a starting observation (the predicted observation that is most similar to the first observation). Additional data can be stored characterising other aspects of the displacement, such as, but not limited to, vibrations encountered transitioning the displacement or energy expended transitioning the displacement, displacement similarity is measured by the end-point error between pairs of displacements, where the displacements commence at the same location and the end-point error is the physical or logical Euclidean distance between the points located by transitioning along the two displacements.

[00126] In a fourth step 305-4 of the hypothesis testing process, a comparison is performed. The comparison compares observations, displacements, or both. The second observation may be compared to a predicted observation from the hypothesis subset, and in particular to the predicted observation linked to the predicted displacement on which the movement function was based. The comparison between the second observation and the predicted observation provides an observation comparison measure. Similarly, the predicted displacement on which the movement function was based when the agent moved from the first location to the second location in the space may be compared to the actual displacement between the first and second location, to obtain a displacement comparison measure. Thus, comparisons can be made to generate both an observation comparison measure and a displacement comparison measure. It is advantageous to use both of these measures, as will be set out in detail later. It is to be understood that the ordering of the above steps, after the moving of the agent, is interchangeable.

[00127] In a fifth step 305-5 of the hypothesis testing process, the hypothesis is adjusted, maintained, or confirmed based on the observation comparison measure and/or the displacement comparison measure from the fourth step of the hypothesis testing process 305-4. [00128] In this step, the observation comparison measure and/or the displacement comparison measure are assessed to effectively determine whether the agent's perception of the space it occupies, in terms of the second observation and the actual displacement, match that of the attribute according to the hypothesis, in terms of the predicted observation and predicted displacement. The observation comparison measure and the displacement comparison measure are explained in more detail later, but generally, the stronger these measures are, the more likely that the hypothesis is correct and the agent is in fact observing the attribute according to the hypothesis, in the space it currently resides.

[00129] The observation and/or displacement comparison measure may be compared to one or more respective thresholds to determine whether to confirm, maintain, or reject the hypothesis.

[00130] Adjusting the hypothesis includes rejecting the hypothesis. This occurs when it is determined that the space being observed by the agent is unlikely to include or represent the attribute according to the hypothesis. This conclusion may be met in several different ways. Firstly, the hypothesis may be rejected when the observation and/or displacement comparison measure falls below a first observation threshold level and/or a first displacement threshold level. The first observation threshold level and the first displacement threshold level may be set globally as a minimum likeliness required to maintain the hypothesis and for the agent to test the hypothesis further. Alternatively, these thresholds may be adaptive and changeable based on environmental conditions of the space such as a brightness/darkness factor, for example. In particular, the lighting in the space may affect the observation comparison measure if the observations made by the agent are made at a different environmental brightness level to the brightness level at which the subset of stored observations relating to the hypothesis were captured and stored. The thresholds may also be adapted based on colour, contrast, and other image/sensor data properties.

[00131] Furthermore, different observation comparison measures may be used that address different additional aspects of the space, and when used in combination permit identification of specific dimensions of difference to the hypothesis. For example, changes in lighting affect a vector comparison measure more than they affect a measure of the spatial distribution of filtered elements around the agent location. Colour changes to an object will affect the colour filtered elements of an observation more than the luminance and orientation filtered elements. Consideration of a variety of observation comparison measures allows the nature of the dissimilarity to be observed. In the case of lighting condition changes, the use of a measure of the spatial distribution of filtered elements of the observation around the agent location can be used to adapt the thresholds, such that a strong match for that measure can be used to update the hypothesis prior and thus reduce the acceptance criteria (a second observation threshold level) for the 'similarity' observation comparison measure. The different types of observation comparison measures discussed here each come from a different method of comparing observations. This is explained in more detail later.

[00132] The first observation threshold level may be set according to the initial ranking of the observation comparison measures, for each stored observation, against the first observation made by the agent. In particular, the first observation threshold level may be set equal to the next-highest ranked observation comparison measure that corresponds to a stored observation of the stored set of observations and displacements that is not in the subset relating to the current hypothesis. This particular stored observation thus relates to a different hypothesis. In this way, the first observation threshold level is set according to the similarity of the first observation to a stored observation relating to a different hypothesis to the one currently being tested. This effectively allows the agent to consider a different hypothesis to the one being tested if the tested hypothesis produces a weaker observation comparison measure than originally found for the different hypothesis. The hypothesis being tested can thus be rejected and ultimately replaced with the different hypothesis that is associated with the first observation threshold level.

[00133] Ultimately, adjusting the hypothesis includes rejecting the current hypothesis and replacing it with a different hypothesis. This may involve the method returning to the second step 302 as illustrated in figure 3 and selecting next-best observation comparison measure in the ranked observation comparison measures to determine the next-best observation and the hypothesis to which it relates. The agent may also return, via an opposite displacement to the actual displacement made, to the location of the first observation in the space before selecting a new hypothesis. The replacement of the hypothesis is explained in more detail later.

[00134] Maintaining the hypothesis occurs when the hypothesis is neither adjusted or confirmed. The hypothesis is thus maintained when the observation and/or displacement comparison measure matches or exceeds the first observation threshold level and/or the first displacement threshold level respectively. This means that the hypothesis does not require adjusting. According to the embodiment introduced above, wherein the first observation threshold level is set according to the 'next-highest observation comparison measure', this means that the current hypothesis still provides the highest observation comparison measure with respect to the predicted observation out of any of the subsets of the stored set of observations and displacements, meaning the attribute according to the current hypothesis is still the most likely attribute to be found in the space in which the agent resides. Another condition that results in the hypothesis being maintained is that a hypothesis confirmation condition is not met. The hypothesis confirmation condition may be a second, higher observation threshold level and/or second, higher displacement threshold level. The hypothesis confirmation condition is indicative of a minimum confidence level that the hypothesis is correct and that the attribute of the space is the attribute according to the hypothesis.

[00135] In other words, the hypothesis is maintained when it is determined that the observation and/or displacement comparison measure with respect to the predicted observation and the predicted displacement matches or exceeds the first observation threshold level and/or the first displacement threshold level respectively, but does not match or exceed the second observation threshold level and/or the first displacement threshold level respectively.

[00136] When the hypothesis is maintained, a next predicted observation and a next predicted displacement, linking the current predicted observation to the next predicted observation, are retrieved from the subset of stored observations and displacements relating to the hypothesis. The process of testing the hypothesis as set out above then repeats as shown in figure 3 with respect to the next predicted observation and the next predicted displacement. In this way, the method 300 involves a sequential testing of a hypothesis subset of predicted observations and displacements until the hypothesis is either confirmed or adjusted.

[00137] At each observation the agent makes, for which the hypothesis is maintained, a historical observation and/or displacement comparison measure is updated, and the historical observation and/or displacement measure is then factored into future observation and/or displacement comparisons. The historical observation and/or displacement measure is stored in memory and acts to increase future observation and/or displacement comparison measures based on the number of consecutive times a hypothesis has been maintained. This effectively increases the confidence that the hypothesis can be confirmed, on the basis that the hypothesis has not been rejected for a plurality of consecutive observations and displacements. It also helps to prevent the agent from becoming stuck in a local minimum whereby the hypothesis is never rejected or confirmed. This process of utilising historical observations and/or displacement measure data may include a single hypothesis sequential probability ratio test against the null hypothesis (that the data do not match the identity) or as a multi-hypothesis sequential probability ratio test between alternative hypotheses including the null (that none of the hypotheses match).

[00138] Confirming the hypothesis comprises determining that the hypothesis confirmation condition is met and determining the attribute of the space based on the meeting of the hypothesis confirmation condition. As noted above, the hypothesis confirmation condition may be a second, higher observation threshold level and/or second, higher displacement threshold level which the observation comparison measure and/or displacement comparison measure must match or exceed.

[00139] Like the first observation threshold level, the second observation threshold level may be modified or adapted based on lighting conditions in the space, using the brightness/darkness factor.

[00140] When the hypothesis is confirmed, the method 300 may stop, as the agent identifies the attribute of the space. The identity of the attribute may be stored to memory, and the observations and displacements that were performed by the agent to identify the attribute may be stored in the memory and linked to the space in which the agent resides.

[00141] The method 300 advantageously uses observations and displacements to determine the attribute of the space, without having to consider the entirety of the space as a whole. This presents a much more computationally efficient method of parsing space.

[00142] The method 300 will now be described in more detail. Firstly, a method 400 of making and comparing an observation will be explained with reference to figure 4. Making and comparing observations occurs in the method 300 in at least two points. Firstly, in the first and second steps 301 and 302, wherein the agent makes an observation and compares it to the set of stored observations to ultimately determine a hypothesis, and secondly during the fifth step 105 when the hypothesis is tested. This process thus requires a minimum of two observations and two comparisons. However, it is to be understood that more observations can be performed, and that is it advantageous to make observations sequentially, not only in the two instances above, but also in transition between the first and second location, whilst the agent is moving from the location of the first observation to the location of the second. These transitional observations are discussed in more detail later. The process of making and comparing observations is described here.

[00143] In a first step 401 , observation sensor data is captured. In the physical space, the observation data is input data that is captured using a sensor, such as a camera. In this example, the observation data is a captured image. The captured image and its content depend on the orientation of the camera. In particular, the camera may be at the same position, for example, attached to a robot at the same position in the world. However, if the orientation of the robot is modified, the content of the observation data may change even though the position of the robot has not changed.

[00144] For this reason, it is advantageous to make observations in physical space using a camera system or other sensor capable of capturing a triaxially stabilised cylindrical projection of three dimensional space, oriented with the main axis of the cylinder perpendicular to the direction of gravity. Fixing with respect to gravity in this manner allows observations to be made with the same roll and pitch (since these can also be fixed according to the gravity direction). The capture resolution of the image may be 256 columns by 64 rows of pixels, for example, but equally could be any resolution. This 256 x 64 pixel image represents input data for the observation that is then manipulated in a second step 402. In a non-physical or logical space, the observation data may be data taken from the logical space from around the location of the agent. The entirety of the logical space may be pre-stored. The observation data may be sourced from a portion within a predetermined distance of the location of the agent in the logical space. For example, where the logical space is an image or map, the observation data may be the pixels or points that are contained within a pixel/point distance of 5, 10, 50, 100, or any number of pixels from the location of the agent.

[00145] In the second step 402, the observation is generated from the input data captured by the sensor, virtual sensor, or retrieved from memory. The input data is encoded through a pipeline of stages into a set of vector/matrix representations.

[00146] The process of generating an observation to be stored, to form part of the stored set of observations and displacements, is very similar to the process of generating a current observation from input data for comparing to a stored observation. However, when making a current observation to compare with, the relative orientation between the agent in its current position and the orientation of the agent when it made the stored observation may not be the same, and may not be easily distinguished. To solve this problem, when making a current observation from input data, the process includes making observations for each possible permutation of the orientation of the agent. In reality, this means that a current observation is associated with a plurality of rotations, whereby each rotation represents the input data shifted or adjusted to represent a different orientation of the agent. How this affects the process in comparison to making a 'stored' observation is referenced below.

[00147] The general process of generating an observation (current or stored) includes the following steps.

[00148] Firstly, low level features are extracted from input data. This may include the use of one or more filters and/or masks, for example, to pre-process the input data. The low-level features may be edges, colours, shapes or the like. The pre-processing may also include colour conversions and the like to provide a plurality of channels of the input data. The result of this first step is processed data, potentially including several channels.

[00149] Secondly, the resolution of the input data is reduced, using filters or the like, by extracting or deleting parts of the input data, such as rows of pixels, and/or by summing and averaging data over large areas of the input data.

[00150] Thirdly, further processing may be performed with one or more kernels to convolve the input data to obtain a useful result, for example, to identify regions of interest, edges, regions of greatest change and the like. If there are several channels this process is performed over all of the channels.

[00151] Fourthly, the resulting data forms a vector or matrix of processed and reduced input data. This is then concatenated across dimensions (columns, rows and channels) and normalised, to produce an observation vector o.

[00152] As noted above, when storing an observation, for the purposes of storing the set of observations, for an identity or map for example, only one observation vector o is required. When making a current observation for comparison purposes, this general process is performed for a number of rotation permutations of the input data. Where the resolution of the data is Xx Y, this may mean including X permutations, each representing a shift of X+1 from a previous permutation. This results in X observation vectors for a current observation, each of which can then be compared to the one stored observation.

[00153] This encoding of input data to form one or more observation vectors o uses a computer device such as a Central Processing Unit (CPU), Graphical Processing Unit (GPU), Field-Programmable Gate Array (FPGA) or application-specific integrated circuit (ASIC), for example.

[00154] A detailed example of this process is provided below, for the above example of an image captured from a camera, wherein the image is a cylindrical projection. In this example, the resolution of the image is 256 x 64 pixels, so, for a current observation, there are 256 possible rotations of the projection, whereby the columns are rotated (shifted) from their originally captured position. As noted above, these rotations represent the different permutations of the original observation data. It is to be understood that there could be any number of permutations based on the input resolution of the image. The detailed process is as follows.

[00155] At a first stage, for each pixel, a colour conversion process may be performed, whereby colour channel data from the captured image is converted. For example, a red, green, and blue-channel data is converted into red, green and luma channels, where luma is 1/3(red+green+blue). It is to be understood that these colours and conversions are exemplary, and that the image may have different colour channels and may be converted into different colour channels.

[00156] At as second stage, the luma channel result of the first stage is convolved with a filter using a convolution kernel [1 ,-1 ; 1 ,-1 ; 1 ,-1 ] or similar vertical edge filter, for example a Sobel or other filter to create a luma vertical (luma_v) channel.

[00157] At a third stage, the luma channel result of the first stage is also convolved with a filter using a convolution kernel [1 ,1 ,1 ;-1 ,-1 ,-1] or similar horizontal edge filter, for example a Sobel or other filter to create a luma horizontal (luma_h) channel.

[00158] This processing results in a new image that contains pixels for four channels: red, green, luma_h and luma_v. It is to be understood that other choices of pixel filter could be used here, and for the set of filters chosen, all subpixels from all channels, (red, green, luma_h or luma_v) are passed into the next following pipeline of processing.

[00159] At a fourth stage, a series of box filters are computed and centred on a set number of evenly-spaced rows of the image for each channel, wrapping around the rows. It is to be understood that there may be more or fewer filters and the size of 19x19 is exemplary. The box filters smooth the image for each channel. Each pixel of each channel is modified by the box filter from the summation of pixels contained within each box filter, this provides a smoothed (or blurred) image. The box filters may overlap with each other. [00160] At a fifth stage, the blurred image is reduced to form a sliced image. In particular, the resolution of the blurred image is significantly reduced. This process is shown in Figure 9. In particular, four evenly spaced rows 902 are extracted from a blurred Image (not shown) processed from an original image 901 (or other observation dataset), to produce the sliced image 904.

[00161] The sliced image thus includes 256 columns and 4 rows, in figure 9.

[00162] At a sixth stage, the columns of the sliced image formed from the fifth stage are separated into sets of evenly spaced columns. In an example, the 256 columns are separated into 256 sets, each set including images of 16 columns by 4 rows, where each has a different first column from the full set of 256 columns. As can be seen from Figure 9, there are 16 sets of 16 (total 256 permutations) of the 16x4 images, whereby columns are shown in different colours to illustrate how data is divided from the 256-column sliced image 904 into the 16x16x16x4 sets. These sets represent every possible rotation position of the input data (by increments of a one column rotation for all possible 256 rotations. It is to be understood that Figure 9 is an illustrative example and more or fewer rows, columns and permutations are possible, meaning there may be more or fewer than 256 possible rotations.

[00163] When an observation is to be stored to memory, to form part of the set of stored observations and displacements, it is only necessary to store one of the 16x4 images of a set formed in the fifth stage. For example, the first permutation 906 of the first set may be selected to be stored as an observation. It is only necessary to consider the rotations, (and thus the 256 possible permutations of a 16x4 image) when making an observation to compare with a previously stored observation. Thus, considering permutations is only required for current observations. When comparing, it is still not necessary to store each permutation of the 16x4 images to memory. Rather, each permutation is iteratively compared against a stored 16x4 observation vector to identify the best match, indicated by one or more observation comparison measures. Storing the permutations is not necessary. Comparing observations is explained in more detail later.

[00164] Returning to the detailed example of making an observation, at a seventh stage, the 16 x 4 image is convolved cyclically with an on-centre, off-surround (or the inverse) kernel. For example, where the element with a value of 1 is the kernel centre. For the first row the kernel may be: [-Vs,1 ,-Vs;-Vs,-Vs,-Vs], for the second and third rows it and for the fourth row [-Vs.-Vs-Vs.-Vs.'l

Vs], for example. An example of this is shown in figure 10, which shows an on-centre, off surround horizontally wrapping filter 1001 to 1003 for a 16x4 image. This kernel identifies the areas of greatest change in the image. As noted above, when storing an observation, this is only required for one 16x4 image. When making a current observation for comparing to the stored observation, this is done for each of the separated sets, (i.e. the 16x16 sets from the sixth stage).

[00165] Following this pipeline, a 16x4x4 image is produced, or in the case of comparison, 256 rotations of a 16x4x4 image. There are 16 columns, 4 rows, and 4 channels. The channels of the 16x4 image may be subdivided into two data subsets, one consisting of red and green, the other luma_h and luma_v. Each of these data subsets are normalised via vector normalisation such that the elements of each describe values on a set of orthogonal values, and the result is a unit vector. These normalised vectors are then concatenated into a single unit vector by scaling each by the square root of two. This provides, the Observation vector, o. This Observation vector in this example is concatenated from 16 columns, 4 rows and 4 channels to give a 256 element vector that is then stored. If being compared, 256 permutations of the vector o are compared against one stored vector.

[00166] As well as the observation vector o, the final vector can store additional data related to the Location of the Observation, such as, but not limited to, a user-defined label, the angular Locations and identities of objects, the data from additional sensory modalities such as, but not limited to, auditory or odour information, the passability of different directions in physical or logical space and the directions that have previously been explored.

[00167] The observation vector o is a coarse representation of the original observation data captured by the sensor, that provides a statistical summarisation of the environment in the vicinity of the agent in the physical or logical space. The coarseness of the vector in comparison to the original data allows the method to run more efficiently. Also, the observation data is filtered at high resolution to create the different channels prior to the coarsening process. Coarsening is also advantageous as it provides a representation of a location that is less sensitive to changes in the lighting or objects in the environment than the state-of-the-art, as information is integrated over large parts of the visual field.

[00168] It is to be understood that the observation vector o may be a vector or a matrix. The vector o may comprise a number of sub regions, each corresponding to a part of the whole vector. The sub-regions may be content/colour sub-regions split based on the channels used to form the vector (in an example, red, green, luma_h and luma_v), or may be spatial sub-regions corresponding to different directions around the agent. The sub-regions may be represented by sub-vectors, whereby the combination of sub-vectors together form the whole observation vector o. As noted, vectors representing rotation permutations are required when comparing observations, when a current observation is made and is required to be compared against a stored observation, It is not necessary to store all permutations.

[00169] It is to be understood that the numbers given above in terms of dimensions, filter and kernel sizes, row selections and rotations permutations can be more or fewer than the example values.

[00170] Returning to Figure 4, in a third step 403, a current observation vector o is compared to stored observations from the stored set of observations. In other words, a current observation is compared to a target observation.

[00171] Observations may be compared using several functions. The comparison of the observations provides the observation comparison measure. The observation comparison measure may differ depending on the function used to compare the observations. In some embodiments, more than one observation comparison measure may be produced by comparing observations using more than one comparison functions. These comparison functions can be used alone or in combination in the method 300 for testing a hypothesis, and for other related methods as is explained later. Environmental features such as a scene brightness level may affect one observation comparison measure but not another. Thus, using a combination of the observation comparison functions and the resultant observation comparison measures allows the method 300 to be performed more accurately in a range of environmental conditions.

[00172] Functions for comparing observations include an observation similarity function 403-1 , an observation rotation function 403-2, an observation action function 403-3 and an observation variance function 403-4. As illustrated in Figure 4, any one or more of these functions can be performed with respect to a current observation and a stored target observation. The initial conditions and system required for each method of comparing observations are thus the same. This system is schematically shown in Figure 5.

[00173] Figure 5 shows a schematic functional diagram of a system or apparatus 500 including various modules involved in the comparison of observations. These modules may be implemented by a computer, computing device, or computer system. It is to be understood that the function of these modules may be separated into further modules and may be separated across components, or their function may be performed by one device or component. A first module of the device or system is a memory module 501 . The memory module 501 stores the set of stored observations and displacements. These observations and displacements may be stored as vectors. The set of observations and displacements, with one or more hypotheses subsets, may be stored in a cyclic or acyclic graph and/or directed graph. Alternatively, the observations and displacements may be stored with metadata identifying the displacements and observations to which they are respectively connected, or may be organised in a look-up table or the like, which preserves the links between respective observations and displacements.

[00174] The memory module 501 is connected or otherwise capable of communicating with a stored observation processing module 502. The stored observation processing module 502 is configured to select the stored observation from the memory module 501 which is to be compared. The stored observation processing module 502 may also select one or more masks for the purpose of reducing the stored observation to a portion of the stored observation, for input to the comparison functions. The masks may include an observation mask, a user/system-selected mask, or a combination thereof. The masks mask certain regions of the selected stored observation vector whilst preserving other regions, known as regions of interest (ROI). The mask may be a binary mask, masking/preserving through values of 0s and 1s, or vice versa.

[00175] The stored observation processing module 502 is connected or otherwise capable of communicating with a comparison engine 503 that performs the comparison according to one or more of the comparison functions 403-1 , 403-2, 403- 3 and 403-4.

[00176] On a second side of the system or device, a sensor module 504 is provided. The sensor module 504 includes a sensor capable of deducing spatial information from its environment, and may thus include a camera, LIDAR sensor, tactile sensor or the like. The sensor module 504 also includes any necessary control circuitry and memory for recording sensor data. The sensor module 504 is configured to capture current observation data.

[00177] The sensor module 504 is connected with or is otherwise capable of communicating with a current observation processing module 505. The current observation processing module 505 processes the sensor data from the sensor module 504 to obtain a current observation, such as a current observation vector. This includes the total rotations possible for the sensor data according to the process set out above with respect to figures 9 and 10. The current observation processing module 505 may also select a mask for masking the current observation vector.

[00178] The current observation processing module 505 is connected or otherwise capable of communicating with the comparison engine 503 that performs the comparison according to one or more of the methods of comparison 403-1 , 403-2, 403-3 and 403-4.

[00179] The comparison engine 503 is configured to acquire or receive the stored observation from the stored observation processing module 502, and the current observation from the current observation processing module 505, and the respective masks, for the purposes of performing a comparison observation according to any of the methods of comparison 403-1 , 403-2, 403-3 and 403-4. The comparison engine 503 may be implemented by a computing device, a server, a distributed computing system, or the like.

[00180] The system 500 further includes a movement module (not shown) configured to move the agent within the space. In the physical space, this could be a motor, engine or the like, configured to translate the agent by physically moving the position of the agent and/or by changing the orientation of the agent. In the logical space, the movement module may be implemented by a computer or the like.

[00181] Whilst the comparison methods are set out separately below, it is to be understood that they may be performed concurrently, or in the same overall process performed by the comparison engine 503. These methods can be performed in the same overall process because they each rely on the same fundamental data points and operations. In particular, each of the following methods compares the current observation with a stored target (predicted) observation. When the observations are represented by vectors for example, each method does this by taking the inner product between the vectors or sub-vectors thereof. The methods of comparison differ in additional pre/post-processing steps as set out below.

[00182] In the first method 403-1 , observations are compared based on a similarity function, to obtain a first observation comparison measure component. The first observation comparison measure component is the 'similarity' observation comparison measure discussed above. This similarity function requires that the vectors of the observations to be compared are vector normalised. The similarity function includes calculating the vector inner product of the observation vectors to be compared. The inner product comprises the cosine of the angle between the two vectors. The similarity function thus returns a single value or score indicative of the similarity between the two vectors corresponding to the observations being compared. When the current observation includes a number of possible rotations, as is the case in the above example whereby there are 256 possible rotations, the vectors corresponding to each of the rotations are compared to the predicted observation. In this case, the inner product which provides the highest value is stored as the first observation comparison measure component. This single value may be used in the second step 302 of the method 300, for example, to produce the set of ranked observation comparison measures, corresponding to the set of stored observations, from which the stored observation that is most similar to the first observation is determined and selected to determine the hypothesis. In other words, this similarity function may be used to determine the similarity between the first observation and the set of stored observations to identify which of the stored observations is most similar to the first observation, and thus which hypothesis to test.

[00183] This similarity function may also be used in a similar way in the fifth step 305 when comparing the second observation and the predicted observation.

[00184] When the current observation is associated with a plurality of rotation positions, each corresponding to an observation vector, the similarity function is configured to find the highest inner product between the different observation vectors and the target observation. To do this, the similarity function keeps track of a 'maximum inner product value' as it iteratively takes the inner product for each of the rotated observation vectors with respect to the target observation. Once all rotations have been assessed, the maximum inner product value is retrieved as the first observation comparison measure component.

[00185] The advantages of using this similarity function are that it is relatively computationally-efficient to run, and the resultant first observation comparison measure component drops off very smoothly as a function of distance from the original observation location, (or from the location of the target observation to which the current observation is compared).

[00186] This function may however be affected by environmental conditions such as a brightness or darkness of the environment. For example, if the stored observation relates to observation data that was captured in low level light conditions, and the current observation relates to observation data captured in direct sunlight, the current observation data may be different from the stored observation data, resulting in different vectors, even if the features captured in each observation are spatially the same. In order to negate these effects, the first observation comparison component can be combined or used with a fourth observation comparison component formed from the fourth observation comparison function 403-4 set out below.

[00187] In the second observation comparison function, observations are compared using an observation rotation function, to obtain the second observation comparison measure component. This rotation function takes the rotations of a current observation o and compares each of these to a target observation, as above for the similarity function. For example, during the fifth step 305 of the method 300, wherein the hypothesis is tested, the observation rotation function may be used to compare the second observation (current observation) to the predicted observation (target observation). In the above example, there are 256 rotations, corresponding to the 256 different possible column positions from the original cylindrical observation data. Whilst the similarity function is configured to retrieve the inner product indicative of the best match between the rotated observation vectors and the target observation, the observation rotation function is configured to identify what specific rotation is responsible for this best match. The observation rotation function outputs the rotation direction of this best match as an offset value, which corresponds to the index of the rotation position of the observation. For example, the best match between the observation vector o and the predicted observation may be the 120 ^th of the 256 possible rotations. This corresponds to the vector formed from the observation data when it is rotated such that the 120 ^th column of the 256 is at the center of the data, or at any other predefined rotation position. The rotation observation function may thus output an offset value corresponding to the index of the 120 ^th rotation position, which may be 120 for example.

[00188] In a physical space, when an inertial measurement unit (IMU) is used as part of or included in the sensor, for example, the offset value is indicative of how much yaw (roll and pitch can be fixed because of gravity) has drifted since the target observation was originally made (assuming that the stored observation that forms the target observation has been visited previously in the current space). Thus, the offset value of the observation rotation function provides an output that is indicative of IMU yaw drift. This IMU yaw drift can be discerned from the output and used to update the set of stored observations and displacements, as each of these are all relative to the original yaw in which they were made and stored. Thus, if there is a level of confidence from the first observation comparison measure component and/or the second observation comparison component, that indicates the current observation is the target observation, the offset value can be used to adjust the set of stored observations and displacements accordingly.

[00189] If the physical space in which the agent resides is not the same space from which the stored observation was captured, then the offset value is indicative of how the space in which the agent resides is oriented in comparison to the space in which the stored observation was captured.

[00190] In summary therefore, the second observation comparison measure component, produced by the observation rotation function, provides an offset result indicative of the strongest similarity between the target observation and a plurality or rotations of the current observation (e.g. 256 rotations). In addition, the index of the rotation indicative of the strongest similarity indicates the alignment between the current orientation of the agent (i.e. the x and y axes as they are currently understood by the agent) and the orientation of the target observation when it was made and stored. The offset can thus recover orientation information, such that target (predicted) observations and displacements can be remapped accordingly.

[00191] This rotation function may be used when comparing the first observation to the set of stored observations in the second step 302 of the method 300, and may also be used in the fifth step 305 when comparing the second observation and the predicted observation, to re-calculate predicted displacements and observations based on the relative orientation (frame of reference) of the agent.

[00192] The observation similarity function 403-1 and the observation rotation function 403-2 described above can be performed in the same process or independently. An example single process in which these functions can be performed together is set out below, in the form of example pseudo-code for running both the observation similarity function 403-1 and the observation rotation function 403-2. The pseudo code is as follows: combined_function(cam_observation[ 16x4x4x256], cam_mask [16x4x4x256], memory_observation [16x4x4], memory_mask [16x4x4], user_mask [16x4x4])

• Initialise max_similarity to -1

• Initialise offset to 0

• For each of 256 rotations: o Initialise cam_sum, mem_sum, match_sum to zero o Combine cam_mask, memory_mask and user_mask using a logical binary OR (If 0 use element, if 1 do not) o For each vector element of the 16x4x4 (256 total): If mask is 0:

• Add square of the element from cam_observation to cam_sum

• Add square of the element from memory_observation to mem_sum

• Add product of elements from cam_observation and memory_observation to match_sum

■ else:

• Do nothing o Renormalise by dividing match_sum by the product of the square roots ofcam_sum and mem_sum o This is the curr_similarity score for this rotation o If similarity score greater than the max_similiarity:

■ Set max_similarity to curr_similarity

■ Set offset to rotation index o else:

■ Do nothing

• After all rotations are considered, max_similarity is the output similarity, the first observation comparison measure component

• After all rotations are considered offset is the output rotation, the second observation comparison measure component.

[00191] In the above pseudocode, 'cam' refers to the sensor, for example a camera, and thus the current observation. Similarly, 'mem' and 'memory' refers to the memory and thus the stored target observation to be compared.

[00192] The cam, memory and user masks function to include and/or disregard certain parts of the current and target observation vectors in the comparison functions. The cam and memory masks comprise information regarding the reliability of the information from parts of the visual scene that are in the observation vectors. For the memory mask, this refers to a single observation vector, and for the cam mask this refers to the set of observation vectors for the different rotations of the visual field. This can be used, for example, to exclude parts of a camera image where excessive contrast has led to saturated input data, where the data is of low quality. The user mask comprises information provided either by a function internal to the system that seeks to select a subset of the full observation vector elements, or an external function to perform the same. This can be used, for example, to determine the observation match for certain input features, or for different parts of the visual scene encoded into the observation.

[00193] The user mask is configured to remove outlier/erroneous data from the observation data.

[00194] The above pseudocode iterates for each of the possible rotations of the current observation to identify a maximum normalised similarity measure over all rotations (the first observation comparison measure component) and the rotation offset to which this maximum corresponds (the second observation comparison measure component).

[00195] In the above first and second observation comparison functions 403-1 and 403-2, and in the third comparison observation 403-3 explained below, the observation vector o may be created from an image of a physical space. The image has the property that the x axis is angle around the agent, and the y axis is some property perpendicular to the x axis, either distance radially, or elevation vertically. In the examples provided above, The vector comprises 4 channels with subpixels (which are red, green, luma_h and luma_v). There may be more or fewer channels, which make the observation vector larger or smaller. Furthermore, the image, and each channel thereof, comprise a series of rows and columns that provide spatial information of a portion of the space in which the agent resides.

[00196] The observation vector o may thus be relatively large, with spatial information in multiple directions and colour/edginess information from different channels. This relatively large vector may be manipulated or sliced to make a range of different comparisons. For example, if only the edge channels luma_h and luma_v are used, the comparison is less affected by colour variations. If only the green channel is used, changes in the distribution of, for example, plants can be determined. If all the channels are used, but only for a spatial sub-region of the input image, then only the corresponding part of the visual world will be compared. This enables partial comparisons to see how well certain parts/features of the world match.

[00197] To perform the slicing of the observation vector o, one or more masks are used. Each mask is a vector of the same number of elements as the observation vector o, which is configured to mask certain regions of the observation vector o whilst preserving other regions. For example, a binary mask of 0s and 1s may be used for such purposes. When there are 256 elements in the observation vector o, the mask comprises 256 elements, where a value of 1 indicates that the corresponding index from the observation vector o should be included/disregarded in a subset of the observation vector o to be compared, whilst a value of 0 in the mask indicates the corresponding element of the vector o should not be included/disregarded in the subset of the observation vector. The mask may additionally be used to filter areas of erroneous data as set out above.

[00198] In the third method of comparing observations, an observation action function 403-3 is used to obtain a third observation comparison measure component. The observation action function may be used to compare observations, and may also be used as part of the movement function to move the agent to the second location, whilst testing the hypothesis according to the fifth step 305 of the method 300.

[00199] The observation action function relies on the same basic principles as the observation similarity function and the observation rotation function. The observation action function differs from the two previous functions in that a plurality of sub-regions of the observation vector o are evaluated, and an offset determined for each subregion. Thus, instead of the entire observation vector o, a subset of the observation vector corresponding to a spatial sub-region is evaluated with the observation action function, from which it is possible to obtain an offset value for each sub-region corresponding to a subset of the vector relative to the target observation. To obtain the relevant sub-region, a mask is used. Each sub-region may overlap with one or more neighbouring sub-regions.

[00200] The use of sub-regions for this purpose originates from the concept that, as the agent moves away or towards the location of a predicted observation, not all parts of the visual field will change equally. This is distinct from classical triangulation as it considers not the movement of an identified object or signal source, but the distortion of the entire visual scene. As such, it is robust to occlusions of parts of the visual scene, making it more tolerant of environmental changes. Additionally, it does not require metric calculations to function, making it more robust to measurement noise. This property can be used to understand both how far the agent is from the location of the target observation, but also allows for a further vector to be calculated for the purposes of moving to that location. This further vector, calculated by the observation action function, uses the same principles as the observation similarity function, except the inner product is obtained for N spatial sub-regions, and these are compared to corresponding sub regions of the target observation. For example, where N=8, 8 spatial sub-regions have half the x axis extent of the full field of view of the whole observation vector o and are each centred on a different direction. In this example, the observation action function is thus effectively the observation similarity function combined with the observation rotation function, performed 8 times, once for each sub-region, to find 8 similarities and 8 offsets. The 8 similarities and 8 offsets are effectively the same as the first observation comparison measure component and the second observation comparison measure component respectively, except only in respect of a specific sub-region of the observation vector o.

[00201] In terms of the actual comparison that is performed therefore, the stored target observation vector is split into /V sub-regions, and for each of the /V subregions, corresponding sub-regions of the current observation vector are compared for all possible rotation permutations to identify which permutation is most similar to the stored target sub-region. The particular permutation that is most similar has an index, for example, the 120 ^th rotation, which is used to identify the offset. An offset is calculated for each sub-region of the stored observation vector and these offsets are used to obtain a movement vector required to reach the position of the target observation, and the similarities are used to evaluate confidence in the movement vector and to weight it when this movement vector is used in the movement function as explained later. The overall output of the observation action function 403-3, and the third observation comparison measure component, is thus this movement vector.

[00202] Figure 6 shows a schematic diagram of observation data corresponding to the sub-regions of the observation vector that are produced for the purposes of performing the observation action function. Figure 6 also shows the process that the sub-regions are subject to in the observation action function (with respect to the observation data for visualisation purposes).

[00203] As shown in figure 6, observation data is represented by a two-dimensional circle 601 of spatial data around the agent 602. It is to be understood that this is a representative example, and the observation data could be in three-dimensions, such as in a cylinder. The observation action function processes the observation vector o in a comparison with a target observation. According to the observation action function, a plurality of sub-vectors of the observation vector are processed, wherein each sub-vector is focused or centred on a different direction. In figure 6, these directions are illustrated as a plurality of directions 604-1 to 604-n in the corresponding observation data 603. In figure 6, there are 8 directions and 8 subregions. However, it is to be understood that there may be more or fewer directions selected for the process of creating sub-regions. [00204] Each of the eight directions correspond to eight sub-regions 605-1 to 605-n of the observation data (not all shown). These sub-regions correspond to parts of the visual field (or sensor field if not a camera), each part being centred on one of the eight directions. The specific direction associated with the sub-region is referred to as a sub-region direction.

[00205] In the observation action function, as explained in more detail below, pairs of sub-regions 605-1 to 605-n are compared against corresponding portions of a stored observation. This is illustrated in the observation data 606, comprising the comparison of a first sub-region 606a and a second sub-region 606b with corresponding portions of the target observation (not shown).

[00206] The observation action function computes the offset between each sub region 606a and 606b and the corresponding portions of the target observation. This produces a pair of offsets 607a and 607b as shown in the observation data 607. From these offsets 607a and 607b, a resultant offset vector 609 is determined as shown in the observation data 608. The sub regions 606a and 606b used in this process are different sub-regions, and may be opposing sub-regions although this is not necessary.

[00207] The observation action function 403-3 will now be described in more detail, with reference to sub-regions of the observation data and the corresponding sub vectors of the observation vector as explained above and illustrated in Figure 6.

[00208] As noted above, the observation action function uses the set of masked subvectors, each of which are a subset of the stored observation vector o and correspond to a contiguous sub-region of the visual field. The sub-regions of the stored observation vector are compared to corresponding sub-regions of a current observation vector arranged around the agent at equal angles. Following the previous example, the sub-regions of the stored vector may cover a set of contiguous columns in a stored 16x4 observation vector. An even number of overlapping subregions are extracted, where there are /V pairs of sub-regions, and where the central column of each sub-region projects into the real world with an opposing vector as illustrated in Figure 6. Figure 6 includes 8 sub-regions. These opposing sub-regions are matched to the 256 rotations of the current observation, and the rotation where the best match occurs is extracted using the observation rotation function 403-2. In particular, an offset is determined for each opposing sub-region, corresponding to the rotation index of the best match between the sub-vector corresponding to the sub region and the rotated stored observation. The differences in the directions of the offset of opposing pairs of sub-sets of the observation vector are compared. This provides a vector indicating the direction and magnitude of the displacement required to get to the stored observation (which, in figure 6, is along the resultant offset vector 609 perpendicular to the line connecting the centres of the two opposing sub-regions 606a and 606b). This direction and magnitude is towards the location where the target Observation being compared was captured. A weighted average of the resultant offset vectors 609 from all the opposing sub-regions provides a single action vector that indicates a direction that moves closer to the location of the target Observation being compared from the location of the current observation. This vector is rotated from the stored observation rotation to the current observation rotation using the second observation comparison measure component, or another rotation measure, to align the direction of movement to the current world frame of the agent. It should be understood that an alternative implementation can be performed where the sub-regions are evaluated in the current observation world frame, whereupon no such rotation need be made, however this is more computationally intensive as the sub-region mask must be evaluated for each of the current observation rotations, and is less accurate as evaluating exact sub-regions in the stored observation is not possible.

[00209] The observation action function 403-3 can thus be considered to be a process that includes repeated use of the observation similarity function 403-1 and the observation rotation function 403-2 to obtain a vector in the direction of the location of the target observation. The observation action function 403-3, the observation rotation function 403-2 and the observation similarity function 403-1 described above can thus be performed in the same process, by the same comparison engine 503, or independently.

[00210] An example process for performing the observation action function 403-3 with the comparison engine 503 is provided below in the form of example pseudo-code:

Action_function:

• For the current observation vector: • Select a cyclically contiguous subset of the columns in the spatial elements, note that cyclically contiguous is such that for a 16 column dimension columns 2,3,4 and columns 15,0, 1,2 would represent contiguous subset examples, while 1,3,4 would not as it missed the intervening column 2. These subsets should have the same width, for example 8 columns, and should be evenly spaced across the columns: for example for 4 subsets of width 8 columns indices 0,4,8, 12 would comprise an example of even spacing when referring to the first, last or other determined column within each subset;

• The determined subset is applied as a user_mask, where the elements in each column in the subset are set to 0 (they are used) and the elements of columns outside are 1 (not used);

• For each subregion: o do combined_function (as above)

• The max_similarity and offset is stored for the subregion

• Given a set of max_similarity and offset where, for each of the subregions, there is a single max_similarity and offset: o For pairs of the offsets where the sub-regions correspond to opposing directions in the agent field of view (e.g. for 8 sub-regions this would be pairs comprising indices 0 and 4, 1 and 5, 2 and 6, 3 and 7) calculate the cyclical distance between the offsets first and second indices in the pair, minus 128. This corresponds to the angle between the offsets, and how the two subregions have moved across the field of view. The direction perpendicular to the sub-region direction pairs is the action direction. The offset difference is used to calculate the action magnitude. The action directions and magnitudes for all the pairs are vector averaged to form the final action function output - the action vector. o The action magnitude is that of the resultant of the vectors described by the offsets (where the second offset is incremented by 128, thus corresponding to a PI radian rotation) .

[00211] Therefore, in the observation action function, opposing pairs of the N offsets are taken (N=8), and each pair represents a direction described by the perpendicular to the direction of the opposing offset's mask centres. This direction is combined with a magnitude calculated from the difference between the two offsets, such that if the offsets are both zero, (i.e. the centres of the sub-regions of the current observation vector are the same as the sub-regions of the stored observation), then the magnitude is zero. If the difference between the first and second of the offsets cyclically, such that if the first offset is 200 and second one is 10 (with 256 rotations) then the difference is -66, but if the first is 10 and the second 200 it is +190. This difference can then be converted into an angle and used to calculate the exact magnitude, or simply scaled down by a factor of, for example, 16, to provide a coarse magnitude for the purposes of the action vector. This can then be used in the movement function to relocalise the agent to a predicted observation, by rotating using the second comparison measure and combining as a vector average with the action vectors for all pairs. Vectors can be excluded from the average based on quality measures, such as a minimum similarity score of the sub-regions. It is understood that, as there is redundancy in the vectors produced by the pairs, this allows parts of the visual scene where there is high environmental difference to be weighted lower in comparison to those where there is low environmental difference.

[00212] In the fourth method of comparing observations, an observation variance function 403-4 is used to determine a fourth observation comparison measure component. The observation variance function uses similar properties to the similarity function and the action function. The observation variance function 403-4 includes calculating the circular variance or the circular standard deviation of offsets of sub regions around the agent. Effectively, this observation variance function identifies some measure of the spread of offsets on a circle around the agent.

[00213] The observation variance function 403-4 uses the same sub-regions of the stored vector as used for the observation action function 403-3, to determine offsets in the same way with respect to a rotation permutation of a sub-region of the current observation vector. For example, consider there are 8 sub regions providing 8 offsets. Because the 8 offsets describe how different parts of the field of view move differently as the agent moves towards/away from the location of the target observation, when the agent is at the target observation location they should all be identical and equal to the offset of the full vector match. As the agent moves away, they diverge and spread. By using a circular statistic, as in the observation variance function 403-4, it is possible to measure this spread, and it increases with distance from the observation location. The circular statistic, which may be circular variance of the eight offsets or circular standard deviation, provides a scalar value that forms the fourth observation comparison measure component. The circular statistic may be any measure of circular dispersion.

[00214] To perform the observation variance function 403-4, the observation action function 403-3 is initially performed, but to obtain /V offsets. From this point, the cyclical circular variance of the offsets is calculated, after first converting from the offset index range (0->255) to a suitable angular range (e.g. radians (0->2*PI). From this point, any sub-region offsets that are more than a given angle from the circular mean angle (e.g. PI/2 radians) are identified, and the circular variance is recalculated excluding these sub-regions, as long as more than a given number of sub-regions remain (e.g. 4).

[00215] The observation variance function 403-4 is another way of determining a similarity between a current and stored observation. Unlike the observation similarity function 403-1 , the observation action function is extremely robust to lighting environmental changes, because it relies on offsets of sub-regions rather than the entire observation vector. However it tends to have discontinuities as the subvectors used have lower dimensionality than the full observation vector o, and at larger distances can generate erroneous matches, which greatly affect the comparison. For this reason the observation similarity function and the first observation comparison measure component provided by the observation similarity function is a better at-distance measure of similarity.

[00216] The circular variance function 403-4 can be used to measure similarity in the same way as the similarity observation function 403-1 , as it provides a scalar output indicative of similarity. Furthermore, the circular variance function 403-4 can be used to determine an environment adjustment factor that can then be used to weight or modify other comparison measure components, such as the first observation comparison measure component from the similarity function 403-1. In particular, if there is a high degree of confidence from another observation comparison function, such as the observation action function 403-3, that the agent is at the target observation, the circular variance function 403-4 should, in a perfect space, provide a high measure of similarity since each of the offsets between the stored vector and the current observation vector should be 0. Thus, the output of other functions can be weighted based on the deviation provided by the fourth observation comparison measure component of the circular variance function 403-4. When for example, the similarity function 403-1 is combined with the circular variance function 403-4, this means that the first observation comparison measure component from the similarity function 403-1 can be modified according to the fourth observation comparison measure component from the circular variance function 403-4, to reduce and quantify the effects of environmental conditions.

[00217] It is to be understood that, although examples are provided above for the observation comparison functions 403-1 , 403-2, 403-3, and 403-4, including numerical examples, the functions may be performed with any choice of number of sub-regions, masks, channels, rotations, and array size.

[00218] The observation comparison measure may include any one or more of the first, second, third and fourth observation comparison measure components resultant from the observation similarity function, the observation rotation function, the observation action function and the observation variance function respectively. The observation comparison measure is produced each time an observation is compared, such as in the second step 302 of the method 300, when a first observation is compared with the set of stored observations, in the fourth step 305-4 of the hypothesis test, when a predicted observation is compared with a second observation, and when transitional observations are compared with the predicted observation, which will be explained in detail later.

[00219] It is to be understood that the observation similarity function, the observation rotation function, the observation action function and the observation variance function described above are examples of functions that may be used to compare a current observation to a target observation. Other functions or adaptations of the above functions may also be used. Generally, such functions are used for comparing observations to determine: how much a current observation looks like a stored observation, what the rotation/orientation of the current observation is in comparison to the stored observation; and when the agent is not at a location of the stored observation, what direction is the location of the stored observation from the current observation.

[00220] Once the observation comparison measure is obtained for the second step 302 of the method 300, and the hypothesis is y determined, a first step of testing the hypothesis is to move the agent to a second location in the space in the first hypothesis test step 305-1 . The movement of the agent is carried out according to a movement function, which depends at least on a predicted displacement of the hypothesis subset. In particular, the movement function depends on the predicted displacement required to reach the location of the predicted observation intended to be compared. Thus, the correct predicted displacement must be selected from the hypothesis subset, which may include a plurality of predicted displacements. In order to ensure that the correct predicted displacement is selected for the movement function, the predicted displacements and the predicted observations stored in the hypothesis subset are linked to each other, as explained previously, in a network of predicted observations connected by the predicted displacements. The linking of observations to one or more displacements in this network may be stored and preserved in any suitable way. For example, the stored set of observations and displacements, which include the hypothesis subset, may be stored in a cyclic or acyclic graph or directed graph. Alternatively, the observations and displacements may be stored with metadata identifying the displacements and observations to which they are respectively connected, or may be organised in a look-up table which preserves the links between respective observations and displacements.

[00221] As discussed with respect to Figure 3, the determination of the hypothesis is based on the stored observation that is most similar to the first observation made by the agent. The predicted displacement selected for the purposes of the movement function is thus the displacement that is linked in the stored set of observations and displacements to the most similar observation to the first observation.

[00222] Once the predicted displacement from the hypothesis subset, which is expected to lead from the most similar observation to a next predicted observation of the hypothesis subset, is identified, the movement function is updated such that the movement is based on the particular predicted displacement.

[00223] It is to be understood that the predicted displacement has both a magnitude and direction.

[00224] The movement function may comprise one or more movement components. A first movement component of the movement function is dependent on the predicted displacement. In particular, the first movement component is a contribution to the movement function that decreases as the agent moves according to the predicted displacement. The first movement component is thus effectively weighted based on a magnitude of the predicted displacement. At the location of the first observation, the magnitude of the predicted displacement is relatively large, so the first movement component is correspondingly more strongly weighted. As the agent begins to move according to the movement function, the magnitude of the predicted displacement is updated based on an actual displacement the agent has already travelled. Thus, the magnitude of the predicted displacements decreases as the agent moves towards the end of the predicted displacement, and the first movement component is weighted such that it gradually becomes weaker. In an example, the first movement component is a function of the predicted displacement given as: predicted displacement - displacement travelled. The displacement travelled is the actual displacement, estimated using odometry, visual inertial odometry or the like. In this example, the weighting discussed above may simply be the factor provided by the subtraction of the distance travelled. As more distance is travelled, the first movement component reduces from an initial value equal to the predicted displacement. In other words, this can be considered as an 'unravelling' of the predicted displacement as the agent travels along the predicted displacement. The value of the first movement component at any given time is thus a function of a 'displacement remaining' of the predicted displacement. This provides a first value which is contributed to the movement function. It is to be understood that this first value may be scaled according to a scaling factor, such that the contribution of the first movement component to the movement function is suitable in view of any additional movement components.

[00225] The contribution of the predicted displacement to the movement function tends to zero as the agent approaches the end of the predicted displacement. In one example, when the actual displacement measured is equal to the predicted displacement, such that the entirety of the predicted displacement has been travelled, the first movement component based on the predicted displacement goes to zero such that it ceases to contribute to the movement function of the agent. When the first movement component is the only movement component of the movement function, such that the movement function only depends on the predicted displacement, then the position of the agent once the predicted displacement has been travelled becomes the second location, where the second observation is recorded.

[00226] Alternatively, the first movement component may cease to contribute to the movement function before the entirety of the predicted displacement has been travelled. In particular, the movement function may be configured to disregard the first movement component when the magnitude of the first movement component, or in other words, the distance remaining of the predicted displacement, is within a displacement-threshold-distance from the end of the predicted displacement. This is advantageous because it reduces the effects of drift on the movement of the agent. In particular, estimation of the actual displacement using odometry is subject to drift related error, such that it is possible the estimate of the actual displacement (actual distance travelled) is less than the true value. Thus, it is possible that the agent may have already travelled the entirety of the predicted displacement even though the estimated actual displacement is less than the predicted displacement. To avoid overshooting the end of the predicted displacement, the first movement component may be stopped before the end of the predicted displacement based on the displacement threshold distance. The displacement threshold distance may be set based on the particular environment or scenario in which the agent is used. In physical space, this may be 5cm before the end of the predicted displacement, 10cm, 1m, 5m, 10m or any suitable value depending on the scenario.

[00227] A second movement component that may be included in the movement function is dependent on the observation action function described above with respect to observation comparisons. When this second movement component is used on the movement function, it is necessary to continuously, iteratively or sequentially make transitional observations between the first location in the space where the first observation is made and the second location in the space where the second observation is made. In other words, the transitional observations are made as the agent moves away from the first location.

[00228] As such, one or more transitional observations are made along the movement path of the agent. Each transitional observation is a type of 'current' observation that is compared to the predicted observation to which the predicted displacement is expected to lead, according to the hypothesis. From each comparison, using the observation action function explained above, an action vector is produced, which defines both an expected magnitude and direction towards a location at which the predicted observation may be found. The action vector forms the second movement component of the movement function. As with the first movement component of the movement function, the contribution of the second movement component may be scaled by a scaling factor, and may also be weighted. In particular, the second movement component may be weighted such that the closer the action vector of the second movement component indicates that the agent is to the location of the predicted observation, the stronger the contribution of the second movement component becomes to the movement function. For example, the magnitude of the vector of the second movement component, resultant from the observation action function, is configured to increase as the agent moves closer to the location of the predicted observation. This increase in magnitude may directly provide the weighting that makes the second movement component stronger as the agent approaches the location of the predicted observation.

[00229] The second movement component may be used alone as the sole contribution to the movement function, or may be used in combination with the first movement component. Advantageously, if both the first and the second movement components are included, such that both of these components provide contributions to the movement function, the movement of the agent depends on both the predicted displacement and transitional comparisons between the predicted observation and transitional observations. This means that there are two separate sources of data that are used to move to and find the predicted observation in the space. This is more reliable and accurate than using just one set of data, as it effectively provides redundancy. Furthermore, the first movement component and second movement component are advantageously complementary to each other, in that the relative weighting of the first movement component is such that the first movement component weakens in its contribution to the movement function, as the agent approaches the end of the predicted displacement, whilst the relative weighting of the second movement component is such that the second movement component strengthens its contribution to the movement function as it approaches the location of the predicted observation. The first movement component and the second movement component therefore behave in an opposite manner.

[00230] If the hypothesis is correct or at least partially correct or similar, such that the attribute relating to the hypothesis is at least similar to the attribute of the space the agent occupies, then the end of the predicted displacement should at least be in close proximity to the location at which the predicted observation is found. As such, having a first movement component dependent on the predicted displacement and a second movement component dependent on the predicted observation aids to move the agent, according to two mechanisms and dimensions, towards the location of the predicted observation.

[00231] The relationship between the first movement component and the second movement component with respect to their contributions to the movement function of the agent can take any suitable form. Examples of the relationship between these two movement components are now described with respect to Figure 7, which shows schematic maps of an agent moving between a first location and a second location in space. [00232] In a first example of the relationship between the first movement component and the second movement component of the movement function, as illustrated by the first graph 701 , the relationship is simple and depends only on the relative weighting of the first movement component and the second movement component. Since the relative weightings of the first movement component and the second movement component decrease and increase respectively as the agent moves away from the first location 701-1 , the first movement component naturally dominates in terms of contribution to the movement function when the agent is nearer the first location 701- 1. This is useful because, in general, the observation action function responsible for the second movement component only provides a weak indication of where the predicted observation may be in the space when the agent is at a position that is far from the predicted observation. This is because the transitional observation made for the purposes of the observation action function will generally be very different from the predicted observation, as the distance between the point of capture of these observations will likely be large, and the observations will thus be of different areas of the space. The observation action function depends on a comparison of, and identifying similarities between, observations, and thus is not as reliable when observations appear very different. Therefore, the fact that the first movement component dominates when the agent is closer to the first position 701-1 of the agent is advantageous, as it can use the predicted displacement to travel closer to where the predicted observation should be. This is more reliable than using the second movement component alone.

[00233] In the first graph 701 , a series of transitional observations 701-2 are made as the agent travels, to regularly, continuously or iteratively update the second movement component and in particular the observation action function responsible for the second movement component. The agent travels a path 701-3 according to the movement function, to a second location 701-6 in the space. As the agent nears the end of the displacement from the first movement component, the second movement component from the observation action function becomes dominant and relocalises the agent to the second location 701-6. It is to be understood that the second location 701-6 is not known to the agent prior to moving, rather, the second location 701-6 represents the identical or best match in the space to the predicted observation (target observation) linked to the predicted displacement. The second location 701-6 is determined by the location at which the second movement component from the observation action function settles at a point in space, such that the magnitude and direction of the observation action function vector indicates that the second location 701-6 is the location of the predicted observation or a best match thereof.

[00234] In a second example of the relationship between the first movement component and the second movement component of the movement function, as illustrated by the second graph 702, the relationship is sequential, such that the movement function depends initially only on the first movement component, and upon expiry of the first movement component, depends only on the second movement component. This relationship usefully does not require transitional observations for a large portion of the journey of the agent between a first location

702-1 and a second location 702-6, since the first movement component depends on the predicted displacement and not the predicted observation. According to this relationship, the agent is configured to move from the first location 702-1 via a first path 702-3 corresponding to movement solely according to the first movement component based on the predicted displacement. When the predicted displacement is depleted, such that the agent reaches the end of the predicted displacement, or reaches a predetermined threshold from the end of the displacement, at an intermediary location 702-5, the movement function switches from using the first movement component to using the second movement component. At this point, the agent makes sequential or iterative transitional observations 702-2, and performs the observation action function to obtain the vector of magnitude and direction that points to the location of the predicted observation. Using this information, the agent follows a second path 702-4 to the second location 702-6. Thus, in the second relationship, the agent effectively travels by the first displacement before relocalising using the observation action function.

[00235] In a third example of the relationship between the first movement component and the second movement component of the movement function, as illustrated by the third graph 703, the relationship is a winner-takes-all type relationship, such that the movement function depends only on whichever of the first movement component and the second movement component has the highest weighting at any particular time and position in space along a path to the second location. As noted above, the first movement component dependent on the predicted displacement naturally has a higher weighting than the second movement component nearer to a first location

703-1 . Thus, the agent travels according to a first path 703-3 based on the first movement component and thus the predicted displacement. During this movement along the first path 703-3, the agent makes a series of transitional observations 703- 2 for the purpose of updating the second movement component. The purpose of this is to determine when the second movement component becomes more dominant than the first. The frequency of transitional observations made along the first path 703-3 is not as important when compared to the first relationship as set out in the first graph 701 , because the transitional observations 703-2 of the first path 703-3 are only made to compare the first movement component to the second movement component, rather than to direct the agent itself. Increasing the frequency simply increases the precision at which it is determined that the 'winner' of the winner-takes- all relationship becomes the second movement component. At a point 703-5 along the path, this determination occurs, when the second movement component is determined to be more dominant than the first. At this point, the second movement component, depending on the observation action function, is used in the movement function to relocalise the agent to the second location 703-6. In this phase, the agent follows a second path 703-4 and makes more transitional observations 703-2 which are needed to obtain the vector from the observation action function to provide a direction and magnitude of travel for the agent to the second location 703-6.

[00236] The movement function thus uses two components to relocalise to the location of a predicted observation. The above three relationships between these two components are exemplary, and any suitable method or combination thereof may also be appropriate.

[00237] The ability of the movement function to relocalise the agent to the position of the predicted observation relies on the observation action function, which relies on similarities being found between the current observation and the predicted observation. Thus, if the similarity between observations are below a certain level, the action function will not relocalise. In this case, the agent may move according to the first movement component of the movement function, based on the predicted displacement. When it is determined that it is not possible to relocalise the agent due to a lack of similarity between the current observation (transitional observation) and the predicted observation, the hypothesis is rejected, since the predicted observation cannot be found at the end or near the end of the predicted displacement. In this case, the agent is moved back along the predicted displacement in an opposite manner, to arrive back at the location in space of the previous observation where the hypothesis was determined. The hypothesis is then adjusted to a different hypothesis related with a different hypothesis subset of the stored set of observations and displacements.

[00238] The movement function thus provides the agent with the capability of moving to a location where: the predicted observation is found; a location of a 'best match' to the predicted observation in the space, (if for example, the agent is relocalised to a position that does not provide an exact match with the predicted observation but is still similar); or to a location where the predicted observation is not found. Since the movement function may comprise two components, there may also be differences between the predicted displacement and the actual displacement travelled. For example, the agent may not be required to be relocalised using the second movement component if the best match or identical match of the predicted observation with a transitional observation is at the end of the predicted displacement. Alternatively, the agent may need to be relocalised by a minor further displacement, such that the actual displacement travelled is similar to the predicted displacement. Finally, the second movement component may relocalise the agent by a greater extent in comparison to the predicted displacement, in which case the predicted displacement is not similar to the actual displacement.

[00239] These possibilities ultimately provide the method with a way of determining, in two separate dimensions, how similar a set of observations and displacements performed by the agent relate to the attribute of the hypothesis. This ultimately informs the decision of whether the hypothesis is adjusted, maintained or confirmed as set out above. In particular, a first dimension is the similarity between the current observation (or observations where the method 300 is continued or repeated for more than two observations), and the hypothesis subset of stored observations. This similarity is determined by the observation comparison measure(s) and is termed 'style'. A second dimension is the similarity between the current displacement (or displacements where the method 300 is continued or repeated for more than two displacements), and the hypothesis subset of stored displacements. This similarity is determined by the displacement comparison measure and is termed 'composition'. The displacement comparison measure is determined by comparing the actual displacement with the predicted displacement.

[00240] In general, there are four combinations of style and composition. These are high style and high composition, high style and low composition, low style and high composition, and low style and low composition. Each of these possibilities are explained in more detail below with respect to what they mean for the hypothesis. [00241] Firstly, a high style and high composition indicates that the observations made by the agent are very similar/identical to the predicted observations of the hypothesis subset, and that the actual displacements made by the agent are very similar/identical to the predicted displacements of the hypothesis subset. 'Very similar' means that the observation comparison measure and the displacement comparison measure are both above the second, higher observation threshold level and the second, higher displacement threshold level as explained above with respect to the fifth step of the hypothesis test 305-5. When both of these levels are matched or exceeded by the displacement and observation comparison measures, it is determined that the space in which the agent resides includes an attribute that matches the identity as defined by the hypothesis subset. As noted previously, it is not necessary that the identity is labelled, but it may be associated with a label defining the attribute associated with the identity. Confidence that the attribute in the space matches the identity increases if the attribute of the space matches the hypothesis subset for a plurality of consecutive predicted observations and displacements. Thus, the determination that the attribute of the space matches the identity may require a plurality of consecutive predicted observations and displacements to be compared and matched to the sufficient level.

[00242] Secondly, a high style and low composition indicates that the observations made by the agent are very similar/identical to the predicted observations of the hypothesis subset, but that the actual displacements made by the agent are not similar/identical to the predicted displacements of the hypothesis subset. 'Very similar' means that the observation comparison measure is above the second, higher observation threshold level, but that the displacement comparison measure is not above the second, higher displacement threshold with respect to the fifth step of the hypothesis test 305-5. In terms of the space the agent resides in, this means that the space 'appears', in terms of the sensor (observation) data, to be the same or very similar as the attribute defined by the hypothesis subset, but that at least one of the size, location, and/or distances between points of the attribute are not as predicted according to the hypothesis. This relationship is referred to as 'context'. In the above examples as illustrated in figures 1 and 2, context may be represented by a similarlooking room with similar furniture as that in Figure 1 , but perhaps a larger room or with furniture rearranged (for example, a central feature may be moved to one side). In figure 2, context may be found if the chair is imaged from the rear view or if the proportions of the chair are modified (e.g. shorter legs, longer back-rest). [00243] Thirdly, a low style and high composition indicates that the observations made by the agent are not similar/identical to the predicted observations of the hypothesis subset, but that the actual displacements made by the agent are very similar/identical to the predicted displacements of the hypothesis subset. 'Very similar' means that the displacement comparison measure is above the second, higher displacement threshold level, but that the observation comparison measure is not above the second, higher observation threshold with respect to the fifth step of the hypothesis test 305-5. In terms of the space the agent resides in, this means that the space appears to have a very similar size, location, and/or distances between points according to the hypothesis, but does not appear to be/ look like the same attribute defined by the hypothesis. This relationship is referred to as 'class'. In the above examples as illustrated in figures 1 and 2, class may be represented by a room of same size and structure, but perhaps of a different colour, with different furnishings. In figure 2, class may be found if the chair is coloured differently, or in a different style of detail while retaining the same proportions, such as some types of chairs designed for dining at a table. For navigation this may be different floors of a building, where the floorplan is identical, but different companies may have provided the decor. In order to determine a class relationship between an attribute in the space in which the agent resides and stored observation data, multiple observation comparison measures may be used. While there could be low similarity indicated by the first observation comparison measure component, from the observation similarity function 403-1 , the second and/or third observation comparison measure components can be used. If the observation action function provides no convergence to a point, then there is no match and the basis of the comparison is invalid, in which case the hypothesis is rejected.

[00244] Finally, a low style and low composition indicates that the observations made by the agent are not similar/identical to the predicted observations of the hypothesis subset, and that the actual displacements made by the agent are not similar/identical to the predicted displacements of the hypothesis subset. In this case, the displacement comparison measure is not above the second, higher displacement threshold level, and the observation comparison measure is not above the second, higher observation threshold with respect to the fifth step of the hypothesis test 305- 5. In terms of the space the agent resides in, this means that the space appears not to be related to the structure or appearance of the attribute related to the hypothesis. The hypothesis may be maintained for further comparison or rejected and adjusted as explained previously.

[00245] By comparing current observations and displacements against stored observations and displacements, for one or more hypothesis subsets, it is possible to identify characteristics of the space in terms of the two dimensions of composition and style, (structure and appearance). When a space is repeatedly or periodically assessed by an agent, it is also possible to use these dimensions to determine changes in the space. In this scenario, the stored hypothesis subsets may include observations and displacements taken directly from the same space in previous operations by the agent. Using this information the agent can detect what has changed in the space over time, in terms of structure and appearance. Identifying differences can help in path-planning applications, and finding alternative routes, for example. The agent may store a mean displacement to a particular stored observation that is updated each time the agent makes the displacement to the observation. This mean displacement provides a historical average of previous displacements made to a particular observation. Furthermore, the standard deviation of previous displacements made by the agent to the particular observation may also be stored. Using the mean displacement and the standard deviation, statistical analysis may be performed to determine the likelihood that the space has changed. For example, if a new displacement to the observation is significantly different from the mean displacement, and/or is different from the standard deviation of previous displacements, it is determined that there is a high likelihood that the space has changed. This could happen if for example, an attribute of the space has been moved. A historical record may be stored for each observation and displacement, including mean displacements, observations, and standard deviations for performing statistical analysis. This historical record may be updated with each exploration of the agent.

[00246] A second historical record may be stored and updated in a similar manner. The second historical record relates to the /V most recent observations and displacements made by the agent, as the agent travels to a particular observation, and particularly a similarity or aggregate similarity score between these /V most recent observations and displacements and the corresponding stored observations and displacements to which they have been compared. The second historical record thus represents a localisation confidence that indicates how confident the system is that the agent has localised to the stored observations and displacements on its way to a particular observation. If the second historical record indicates that the /V most recent observations made by the agent are a very good match to the /V most recent stored observations, this gives confidence that the agent is well-localised to the subset or path it is following, in terms of observations and displacements. Should the displacement made to the particular observation, or the particular observation itself, then be significantly different from the corresponding stored observation and displacement, then the second historical record can be used to show and determine with confidence that the space has changed in some respect for that particular observation and displacement. For example, if /V=5, the five most recent displacements made by the agent may exactly match the stored displacements. If the 6 ^th displacement made is then different to the 6 ^th stored displacement, the fact that the second historical record indicates a high-level of matching (identical in this case) for the previous 5 displacements, means that it can be easily determined that the space has been changed with respect to the 6 ^th displacement. This could be due to moving an obstacle, a feature of the like.

[00247] Furthermore, although as described above, the hypothesis may be confirmed, maintained, or rejected on the basis of observations or displacements separately, it is advantageous to use both observations and displacements, and thus composition and style, in determining the outcome of the hypothesis. By combining the observation comparison measure and the displacement comparison measure to form a two-dimensional similarity measure, adjusting the hypothesis may include adjusting the hypothesis if the two-dimensional similarity measure falls below a first two- dimensional similarity measure threshold level. Maintaining the hypothesis may include maintaining the hypothesis if the two-dimensional similarity measure exceeds the first two-dimensional similarity measure threshold level, but does not exceed a higher second two-dimensional similarity measure threshold level. Confirming the hypothesis may then occur if this second two-dimensional similarity measure threshold level, also referred to as a hypothesis confirmation two-dimensional similarity measure threshold level, is exceeded. Where there is change in the visual identity of an observation encountered at a different time, the agent may, if confident that the current and past observation are captured of the same Identity, use the current observation information to update the stored observation. As both observations are represented by normalised vectors this could comprise averaging the two vectors with an optional weighting applied to each, such that the final observation would align more or less with the past or current observation vector. For example, if the past observation is multiplied by 5 and the current by 1 , then the summed vector re-normalised, then the final observation vector would be more aligned to the past vector.

[00248] Adjusting the hypothesis includes rejecting the hypothesis and returning to a previous observation to identify a second hypothesis. In particular, if, at any observation, the current observation does not match the predicted observation to a suitable level of confidence, and/or the actual displacement does not match the predicted displacement to a suitable level of confidence, the hypothesis is rejected. The agent is then configured to return to a previous observation, by making an opposite displacement from the displacement made to get to the current observation. This may include returning to an initial observation although this is not necessary. The method 300 then repeats to test a different hypothesis, selected based on a comparison between the previous observation and each of several hypothesis subsets of predicted observations. Optionally, the agent may store observations and displacements even if such observations and displacements do not match the hypothesis, and the hypothesis is subsequently rejected. Storing these observations and displacements can be useful in generating a map of the space for future navigation and attribute identification purposes. Thus, before retreating to a previous observation, the agent may make and store one or more observations and displacements even if the hypothesis is rejected.

[00249] Confirming the observation includes identifying or finding an object, image or destination in the space, but is not limited to these examples. Once the attribute has been found, reference to it, including the observations and displacements made in the space by the agent, are stored to memory. These may form part of a map of the space in which the agent resides. If the hypothesis is associated with an identity or an attribute that is labelled, then the agent may also store reference to the label to memory, with the observations and displacements that it has made in the space. Where the hypothesis is based on previous visits to the same space, in that the hypothesis subset effectively defines an attribute as previously observed in the space, the hypothesis subset may be updated with the set of displacements and observations made by the agent most recently in testing the hypothesis. In this way, the hypothesis subsets may be kept up to date with respect to a particular space.

[00250] It is to be understood that the above methods may be performed by one agent or one or more agents working together. When one or more agent is included in the space, the one or more agents may communicate with each other, and/or have access to the same memory. For example, the plurality of agents may each be linked to the same server or computer system. The plurality of agents may simultaneously update a map of a space, or test one or more hypotheses simultaneously. Generation of the map is discussed in more detail below.

[00251] In the above description, a method 300 is described for the purposes of parsing space and identifying an attribute of the space. The attribute may be an object, or image, such that the method 300 is used for object or image recognition purposes, or a destination, such that the method 300 is used for navigation purposes. The method 300 relies on an agent making observations and displacements in the space and comparing these to stored observations and displacements. Thus, one principle of the method 300 is the ability of the agent to compare observations and displacements. This is set out in figures 4 to 6 and the accompanying description above. Another principle is the ability of the agent to move, which is set out in figure 7 and the accompanying description above.

[00252] Further aspects will now be described that are complementary to the method 300, which may be incorporated in the method 300 or may alternatively be performed or implemented separately.

[00253] A first further aspect is the generation and storing of the linked observations and displacements that form identities and the hypothesis subsets. This may be considered a 'training process' as briefly mentioned previously. The process of forming identities may be performed specifically for the space in which the agent is intended to reside, or may be performed in a separate space. There are benefits for both of these implementations. Where identities are formed in the same space the agent is later configured to investigate, it becomes possible to identify how attributes of that space change over time after further explorations of that space. Where identities are formed in separate spaces, it is possible to identify recurrences of attributes of one space in another, and to identify similarities and differences between spaces.

[00254] The process of forming and storing an identity is set out here with reference to figure 8. Figure 8 shows a schematic diagram 800 of an identity. Consider that no observations or displacements have been stored. The agent is 'dropped' or otherwise activated in a previously unknown and unexplored space. An initial Observation o1 is made in the space. The initial observation o1 may be made based on low-level features detected in the space, although this is not compulsory. The use of low-level features is discussed separately later as a further complementary aspect. The choice of initial Observation can further be chosen at random, or based on a learned process. From the initial observation o1 , an initial displacement is made from the location of o1 to make a new Observation o2, and the Displacement between o1 and o2 is stored to memory denoted as d12, as well as the inverse Displacement from o2 to o1 which is the negative of d12 denoted as d21.

[00255] Optionally, an additional effort value is stored which is a better measure of a property to be optimised in routing such as, but not limited to, energy usage, and/or vibrations encountered.

[00256] A sequential set of Observations Oi{oi, 1 ...oi,n} with a corresponding set of Displacements Di{di, 1 ...di,n-1} are then travelled by the agent and stored in the same way. This forms an Identity. The set of observations and displacements that form the identity describe a predicted path through space, along with the expected surroundings at points on the path. Travelling the path allows the agent to test the prediction (i.e. hypothesis), by comparing the measured displacements and observations on-by-one against the prediction. The sequential set of observations and displacements that form the identity are stored as set out above. In some examples, the identity can be stored as a subset of a larger stored set, wherein the larger stored set includes a plurality of subsets, and wherein each subset defines a pathway within the same or different space. It is thus possible that identities are linked to other identities, and for identities to share one or more common observations and/or displacements.

[00257] As shown in figure 8, a series of observations o1 to o4 and corresponding displacements can be captured in a closed loop to form the identity, and this can then be tested against further future observations and displacements sequentially for a contiguous subset or for the entire set in sequential order using the Style and Composition dimensions as set out above. The identity can be used for purposes including, but not limited to: Localisation or identification of specific objects; Extraction of general repeated Classes such as objects or navigational topographies such as, but not limited to, building corridors and rooms; and Extraction of Contexts, which are regions or objects with similar components or properties (e.g. forests I offices I streets or wheeled vehicles I flying objects).

[00258] During or once the identity has been stored as a subset of observations and displacements, a further, optional process may include the use of a separate system to determine the attribute to which the identity relates. For example, the identity could be related to a pathway, for navigation purposes to a destination in the space. Alternatively, the identity could be related to an object, such as a chair, or an image, such as a cartoon-chair or a painting of a chair. To correctly associate the identity with these attributes, a training process may be used. The training process may involve identifying the attribute via an established training algorithm, including the use of training data to train a classifier, for example. It is to be understood that any machine learning process may be used, and may include the use of neural networks or the like.

[00259] A second further aspect is the formation of a map of the space in which the agent resides. Whilst the agent may be controlled to test a hypothesis to identify an attribute of the space in which it resides according to the method set out above, the agent may also/alternatively be controlled to generate a map of the space in which it resides. It is to be understood that generation of a map can thus be performed independently or in combination with identity generation and attribute determination/hypothesis testing.

[00260] The agent may generate a new map if the space is entirely unknown from previous explorations of the agent, or the agent may update an existing map in memory if the space has been previously visited by the agent.

[00261] To generate a map, the agent makes a first observation in the space. This could be the same observation as the first observation made in the first step 301 of the method 300 for testing a hypothesis described above. The first observation is stored to memory, indicative of a corresponding 'first location' of the map.

[00262] The agent is then configured to move away from the first location to make one or more further observations.

[00263] When the map is being made or updated in combination with the agent performing hypothesis testing, the agent moves according to the movement function as set out above. In this case, the agent is configured to make one or more new observations as it moves away from the first location. The new observations may be made whilst the agent moves according to the movement function (transitional), or may be made thereafter. In this respect, the agent may wait until it arrives at the second location of the second observation of the method 300 described above before making the 'new' observation, in which case the second observation is the new observation.

[00264] The new observation is compared with the first observation, using one or more observation comparison functions as set out above. This gives one or more observation comparison measures. The observations comparison measure is compared against a mapping threshold that defines a maximum likeliness that consecutive observations must fall below in order to be recorded on the map. In other words, the method of generating the map requires that observations stored on the map are not too similar. This avoids unnecessary points being added to the map, which keeps the map concise and the memory required to store and access it at a minimum. When the observation comparison between the first observation and the new observation results in an observation comparison measure that is lower than the mapping threshold, the new observation is stored to memory on the map, at a 'new location'. A displacement between the first observation and the new observation is measured and/or retrieved from the movement function and is also stored to the map, together with the inverse displacement from the new observation to the first observation. When the map is generated when hypothesis testing is also happening, this means that the agent performs two comparisons - a first between the current observation and a predicted observation (to test the hypothesis), and a second between the current observation and a previous observation (such as the first observation), to determine whether these observations are non-similar enough to both be included on the map. Thus, even when the hypothesis is rejected, and the current observation does not match well enough to the predicted observation, the agent can still usefully make an observation or use the current observation for the purposes of adding to or updating the map, by comparing it to the previous observation.

[00265] If the mapping threshold is exceeded, the new observation is not stored on the map, and instead, the agent is configured to move again by a further displacement before making a further observation, until the mapping threshold is not exceeded.

[00266] Once the new observation is stored on the map with the displacement between the first observation and the new observation, the new observation effectively becomes the first observation (or a previous observation), and the process repeats for a further displacement and a further observation. This process iteratively builds a connected network of observations that form a map descriptive of the space in which the agent resides.

[00267] The map of a space can also be generated separately from identifying an attribute of a space. The method of generating a map is largely the same. The agent makes a first observation, and stores this in memory as the first location in a map. The agent then moves away from the first location of the first observation in a direction that is unexplored and physically or logically passable. The movement of the agent is recorded as a first displacement. As above, the agent then makes one or more new observations away from the first location, and compares the first observation to the new observation to determine whether the mapping threshold is exceeded. If the mapping threshold is not exceeded, the new observation is stored on the map, with the first displacement and an inverse first displacement linking the first observation with the new observation. The relative directions between the first and the new observations are marked as 'explored'. The process then repeats for further displacements and observations from the location of the new observation, in an unexplored direction. The use of the mapping threshold means the number and density of observations made in a particular space is dependent on the complexity and features of that space. For feature-rich environments, more observations are made, as similarity between observations drops below the mapping threshold faster and in less distance. In feature-poor environments, whereby the space is not as complex, fewer observations are required. Thus, the method of mapping and/or identifying an attribute is performed in a manner that means it is automatically adapted to the constraints of the space being observed or travelled by the agent. The methods are thus sensitive to the complexity of the environment.

[00268] Multiple agents may contribute to the same map. In particular, a plurality of agents may each contribute and have access to a shared database or memory, and are configured to update the shared database with sets of observations and displacements to generate a map. Where hypotheses are tested and attributes identified, identities relating to the attributes may be stored on the map and where possible labelled as such. Thus, the map may include multiple identified attributes and stored labels for these attributes. Agents can contribute to the generation of the map in real or near-real time, and are each communicatively coupled to the shared database, via any suitable means. For example, in a physical space, the plurality of agents may be a fleet of drones, robots, vehicles or the like, each of which is able to communicate with a computer system or distributed computer systems such as a plurality of servers.

[00269] The map can be used for navigation of the space thereafter. In particular, a destination on the map can be selected for moving the agent to. This destination is represented by an observation that forms part of the map.

[00270] Navigation of the map works in a similar way to the method 300 for testing a hypothesis and determining an attribute of the space. When navigating the map, the attribute is effectively the destination. The process of navigation is described in more detail here.

[00271] The map is generated and stored in memory as noted above, and forms a set of stored observations and displacements, wherein at least a subset of the stored observations and displacements are connected to or form a network with the observation associated with the destination. The map is thus similar to a hypothesis subset as explained above.

[00272] The agent is configured to make a first observation in the space to identify which of the stored observations of the stored map the agent is closest to. In particular, the first observation is compared to each of the observations connected to the destination in the stored map. From these comparisons, a closest matching observation to the first observation is identified. The agent is then moved so as to relocalise to the position of the closest matching observation.

[00273] From the position of the closest matching observation on the map, a route is planned using a routing algorithm. Any suitable routing algorithm may be used, such as Dijkstra’s algorithm that determines the route that minimises a measure that may be distance, effort, vibration or some other measure that can be retrieved from the displacements stored in the map.

[00274] Once the route is planned, the agent moves along the route in a sequential manner, wherein a process is repeated as the agent moves from observation to observation on the map. The agent starts this process from the 'closest matching observation' and the route may, for example, include a plurality of observations between the closest matching observation and the destination. The observation at which the agent is currently at is the current observation, and the next observation in the route to the destination, from the map, is referred to as the target observation.

[00275] The repeated process includes using the stored displacement vector between the current and target observations to move the agent in the direction of the target observation. This is analogous to moving the agent according to the movement function, dependent on the predicted displacement, as explained above with reference to the method 300 for hypothesis testing. As with hypothesis testing, the process also includes using one or more observation comparisons using one or more of the observation similarity function, the observation rotation function, and the observation action function. For example, the stored displacement to reach the target observation may be used in combination with the observation action function to move the agent from the current observation to the target observation. The agent may thus make a plurality of transitional observations whilst travelling between the current observation and the target observation, to use the observation action function to relocalise to the position of the target observation. This is analogous to the movement function comprising the first movement component and the second movement component as described above, and allows the direction of travel to be modified and account for odometric drift and uncertainty when recapitulating the displacement between the current observation and the target observation.

[00276] Once the observation comparison measure (or measures) is above a predetermined threshold value, or a continuously calculated threshold value, it is determined that the agent has reached the target observation. This is analogous to determining a match between the second observation and the predicted observation in the hypothesis testing method 300. Once it is determined that the agent has reached the target observation, the process is repeated for the next observation in the route to the destination, until the destination is reached. Thus, the target observation becomes the current observation, a next observation becomes the target observation, and the displacement to be travelled is the displacement between the current observation and the target observation. Once the agent reaches the observation associated with the destination, the agent is configured to wait at that position unless instructed otherwise.

[00277] Thus, the use of observations, displacements, and a movement function can be used to identify attributes and features of a space, generate a map of the space, and navigate the space. It is to be understood that one or more or all of these processes can take place concurrently. For example, the agent can be instructed to follow an existing route to a destination, identify attributes or features en-route to the destination, and add to the existing map using transitional observations. The agent is thus capable of learning and navigating its environment concurrently.

[00278] In the above described methods and systems for parsing logical or physical space, including identifying an attribute/feature of the space, generating a map of the space, and navigating the map of the space, the agent is configured to make and compare observations, and move between these observations. As noted previously, it is not necessary that the logical or physical space is known to, or has been previously visited by the agent. There are thus several sets of initial conditions that the agent may encounter when being put into the space.

[00279] In a first instance, the agent may be put in a space whereby the space has been previously visited, and wherein the agent has access to a stored map or stored subsets including observations and displacements made in the space. In this instance, when making the first observation, the first observation may be identical or otherwise match with a stored observation (such as a predicted observation of a hypothesis subset and/or an observation in a path to a destination). In this case, it is not necessary to relocalise the agent before performing the method 300 to test the hypothesis, or to navigate a route to a stored destination.

[00280] In a second instance, the agent may be put in a space whereby the space has been previously visited and wherein the agent has access to a stored map or stored subsets including observations and displacements made in the space. In this instance, when making the first observation, the first observation may not be identical to any of the stored observations of the map or stored subsets. Since the location of the agent is thus unknown, it is not possible to use stored displacements to relocalise the agent onto a stored observation. Rather, the agent must first relocalise to a stored observation without the use of predicted displacements, in order to understand its position on the map or with respect to the stored subset of observations and displacements. To do this, the first observation is compared with each of the stored observations, and the observation action function is used to determine a vector towards one of the stored observations, referred to here as the target observation. The agent then moves along this vector, iteratively or continuously updating it with further transitional observations to relocalise onto the target observation.

[00281] The choice of which stored observation becomes the target observation may be decided in any reasonable manner. In one example, the stored observations may each be compared, for all rotations, against the first rotation, using the observation similarity function. The most similar stored observation may then be selected for the purposes of comparing to the first observation for determining the action vector from the observation action function.

[00282] Alternatively, the action vector for each stored observation may be determined, and the strongest of these is then selected for relocalising the agent to a stored observation. The action vector is determined from the observation action function as explained above, and is weighted, and thus becomes stronger, based on the similarities between sub-regions of a stored observation vector and corresponding dub-regions of a current observation vector, or based on the overall similarity measure.

[00283] In a third instance, the agent may be put in a space whereby the space has not been previously visited, but wherein the agent has access to stored subsets including observations and displacements from a different space or spaces. In this instance, when making the first observation, the first observation may not be identical to any of the stored observations of the stored subsets. Since the location of the agent is thus unknown, it is not possible to use stored displacements to relocalise the agent onto a stored observation. Rather, the agent must first relocalise to a stored observation without the use of predicted displacements, in order to understand its position in the space with respect to the stored subset of observations and displacements. To do this, the first observation is compared with each of the stored observations, and the observation action function is used to determine a vector towards one of the stored observations, referred to here as the target observation. The agent then moves along this vector, iteratively or continuously updating it with further transitional observations to relocalise onto the target observation.

[00284] The choice of which stored observation becomes the target observation may be decided in any reasonable manner. In one example, the stored observations may each be compared, for all rotations, against the first rotation, using the observation similarity function. The most similar stored observation may then be selected for the purposes of comparing to the first observation for determining the action vector from the observation action function.

[00285] Alternatively, the action vector for each stored observation may be determined, and the strongest of these is then selected for relocalising the agent to a stored observation.

[00286] However, unlike the first and second instances above, in this third instance, the stored subset of observations and displacements are from a different space to the space in which the agent currently resides. It is thus possible that none of the stored observations exist in the space in which the agent resides. In this instance, the agent may not be able to relocalise to a stored observation. If the agent is testing a hypothesis, such that the stored subset of observations and displacements is a hypothesis subset, the agent may reject the hypothesis relating to the hypothesis subset if the agent cannot localise onto a stored observation of the hypothesis subset. The agent may then return, by a negative displacement, to the location in the space of the first observation. From here, the agent may select a different hypothesis and a corresponding hypothesis subset to test. The agent may repeat this process as necessary for all stored hypotheses and hypotheses subsets. If all of the hypotheses are rejected, meaning that the space does not include any recognisable features or attributes corresponding to the stored subsets of observations and displacements, the agent may enter an exploration mode whereby the agent makes observations and displacements to generate a map of the space as explained above.

[00287] In a fourth instance, the agent may be put in a space whereby the space has not been previously visited and wherein the agent does not have access to any stored subsets including observations and displacements. In this instance, the agent enters the exploration mode as above, to map out the unknown space in which it resides, and ultimately store a set of observations and displacements to describe the space.

[00288] The above description focuses on an agent making sequential observations and displacements to perform one or more of generating a map, navigating a route through a space, or identifying a feature of the space. Whilst it is possible to perform these methods using observations and displacements alone, additional factors may be incorporated to provide further efficiency and accuracy benefits.

[00289] In particular, low-level features of the space may be identified or detected and used to inform the process of making observations and moving between observations within the space. In particular, observations made by the agent include spatial information indicative of the environment of the space within the vicinity of the agent. It is thus possible to extract features from the observations or the observation data to obtain even more information regarding the vicinity of the agent. For example, environmental cues such as high-contrast lines, colours, edges and shapes may be extracted to determine further information regarding the environment, which can be used to inform decisions and behaviours. In map generation for example, wherein the agent is configured to explore a space by sequentially making observations and displacements, the selection of direction in which to move the agent after each observation may be driven by low-level features. Specifically, after making each observation, the selection of the next direction of movement of the agent may be weighted based on low level features and/or directions previously navigated. For example, a first weighting may be applied to directions that, if traversed by the agent, would move the agent closer to a previous observation. Since the objective in map generation is for the agent to explore and map a space, it is beneficial to encourage the agent to move away from previous observations, and this first weighting achieves this. A second weighting may be applied to directions based on low-level features. For example, if an edge or high-contrast line appears to lead in a specific direction, that direction may be weighted higher than a direction where there are no low-level features. In a physical space, the agent may be a vehicle. The low-level features extracted may include roads (from edge detection or the like). The directions in which the roads appear and/or lead, from the current observation, may be weighted higher than a direction from the current observation with no roads. This second weighting based on low level features thus encourages the agent to follow or move closer to potential features of the environment. By following roads for example, the space is more likely to be explorable and the agent is more likely to make observations that are easily traversed and connected. While roads are artefacts that have been added to the environment by humans, it is understood that in natural environments features that can provide a similar benefit exist, such as the banks of water courses, the edges of woodlands with grasslands, and trails left by foraging animals wearing paths in vegetation. By following such features as part of both the exploration and navigation stages of movement the agent can ensure that there are additional guides that can ensure reliable traversal, even in cases of high environmental difference, such as thick mist. It should also be noted, that such features aid when the agent is recognising an identity for an object, such as a chair. Following the string edges formed by the legs, seat and back of the chair can guide the movement of the point of observation to ensure high robustness in recapitulating an identity, even in the presence of 3D rotations.

[00290] It is to be understood that the first and second direction weightings discussed here may be used separately (without the other) or in combination.

[00291] The low-level features identified or detected in observations or observation data may also be linked to a set of behaviours to be performed by the agent. These behaviours allow the agent to approach features in similar ways when first encountering a new part of space or object to when it reencounters the same part of space or object. For example, when a high-contrast line is identified or detected, the agent may be configured to travel along the high contrast line. The agent may be configured to follow consistent lines in the environment to their vanishing points, such that the agent can move along roads, pavements or paths. These types of structured actions simplify the problem of robust navigation. The agent may move in another predetermined direction with respect to a low-level feature, such as perpendicular, parallel, clockwise or counter-clockwise with respect to the low-level feature.

[00292] Observations may also be made according to the presence of low-level features in the environment. Distinctive low level visual statistics which can include but are not limited to, spatial frequency distribution, luminance distribution, colour distribution may be used to determine when and where the agent should make an initial observation.

[00293] The use of low-level features is not limited to map generation. In particular, low-level features can be used in any of the methods described above. In hypothesis testing for example, according to the method 300 described above, low-level features or cues can be used in the movement function when determining how to move the agent from a current observation to a predicted observation. The movement function is dependent on the predicted displacement required to move the agent to the predicted displacement, but may also be dependent on low level features such as high-contrast lines or edges. In a physical space, the agent may be configured to follow such low level features, such as a road, even if the road is not directly aligned with the direction of the predicted displacement. A road may be identified by, for example, presenting as a single colour extending from the bottom of the field of view, where the agent is located, upwards towards the top of the field of view, which largely contains more distant locations. Alternatively, the road may be identified as a region extending as previously described, but comprising strong vertical edges in the absence of strong horizontal edges. If for example, the road is within a threshold angle from the direction of the predicted displacement, the agent may be configured to follow the road rather than follow the predicted displacement. This can improve the system if the predicted displacement is for whatever reason inaccurate. The agent may then routinely make transitional observations whilst on the road to ensure that the movement of the agent is acceptably towards the predicted observation. The agent may leave the road if the predicted observation is not reached or appears, from the observation action function for example, to be moving further away relative to the agent. The agent may also move to the conclusion of the low level feature (for example the end of the road or the next junction in the road). If the agent does not find the predicted observation at this point, the agent may nevertheless make observations and store them to generate a map or otherwise further populate the map with new knowledge of the space, before rejecting the hypothesis and returning to the previous observation.

[00294] Following low-level features or otherwise using them advantageously simplifies the process of testing a hypothesis and navigating a space, since backtracking from a point in space to a previous observation is easier, and simply requires the following for the low-level feature in a reverse manner. Additionally, robustness to highly visually impactful environmental changes, such as thick fog, is improved as the agent can follow the feature, even in the absence of more distant descriptive information.

[00295] In the embodiments described above, the system or method may be implemented using a server. The server may comprise a single server or network of servers. In some examples, the functionality of the server may be provided by a network of servers distributed across a geographical area, such as a worldwide distributed network of servers, and an agent may be connected to an appropriate one of the network servers based upon, for example, an agent location.

[00296] The above description discusses embodiments of the invention with reference to a single agent for clarity. It will be understood that in practice the system may be shared by a plurality of agents, and possibly by a very large number of agents simultaneously.

[00297] The embodiments described above are fully automatic and may be carried out by an agent autonomously. In some examples a user or operator of the system may manually instruct some steps of the method to be carried out.

[00298] In the described embodiments, the system may be implemented as any form of a computing and/or electronic device. Such a device may comprise one or more processors which may be microprocessors, controllers or any other suitable type of processors for processing computer executable instructions to control the operation of the device in order to gather and record routing information. In some examples, for example where a system on a chip architecture is used, the processors may include one or more fixed function blocks (also referred to as accelerators) which implement a part of the method in hardware (rather than software or firmware). Platform software comprising an operating system or any other suitable platform software may be provided at the computing-based device to enable application software to be executed on the device.

[00299] Various functions described herein can be implemented in hardware, software, or any combination thereof. If implemented in software, the functions can be stored on or transmitted over as one or more instructions or code on a computer- readable medium. Computer-readable media may include, for example, computer- readable storage media. Computer-readable storage media may include volatile or non-volatile, removable or non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. A computer-readable storage media can be any available storage media that may be accessed by a computer. By way of example, and not limitation, such computer-readable storage media may comprise RAM, ROM, EEPROM, flash memory or other memory devices, CD-ROM or other optical disc storage, magnetic disc storage or other magnetic storage devices, or any other medium that can be used to carry or store desired program code in the form of instructions or data structures and that can be accessed by a computer. Disc and disk, as used herein, include compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk, and Blu-ray (RTM) disc (BD). Further, a propagated signal is not included within the scope of computer-readable storage media.

Computer-readable media also includes communication media including any medium that facilitates transfer of a computer program from one place to another. A connection, for instance, can be a communication medium. For example, if the software is transmitted from a website, server, or other remote source using a coaxial cable, fibre optic cable, twisted pair, DSL, or wireless technologies such as infrared, radio, and microwave are included in the definition of communication medium.

Combinations of the above should also be included within the scope of computer- readable media.

[00300] Alternatively, or in addition, the functionality described herein can be performed, at least in part, by one or more hardware logic components. For example, and without limitation, hardware logic components that can be used may include Field-programmable Gate Arrays (FPGAs), Program-specific Integrated Circuits (ASICs), Program-specific Standard Products (ASSPs), System-on-a-chip systems (SOCs). Complex Programmable Logic Devices (CPLDs), etc.

[00301] Although illustrated as a single system, it is to be understood that the computing device may be a distributed system. Thus, for instance, several devices may be in communication by way of a network connection and may collectively perform tasks described as being performed by the computing device.

[00302] Although illustrated as a local device in some embodiments, it will be appreciated that the computing device may be located remotely and accessed via a network or other communication link (for example using a communication interface).

[00303] The term 'computer' is used herein to refer to any device with processing capability such that it can execute instructions. Those skilled in the art will realise that such processing capabilities are incorporated into many different devices and therefore the term 'computer' includes PCs, servers, mobile telephones, personal digital assistants and many other devices. [00304] Those skilled in the art will realise that storage devices utilised to store program instructions can be distributed across a network. For example, a remote computer may store an example of the process described as software. A local or terminal computer may access the remote computer and download a part or all of the software to run the program. Alternatively, the local computer may download pieces of the software as needed, or execute some software instructions at the local terminal and some at the remote computer (or computer network). Those skilled in the art will also realise that by utilising conventional techniques known to those skilled in the art that all, or a portion of the software instructions may be carried out by a dedicated circuit, such as a DSP, programmable logic array, or the like.

[00305] It will be understood that the benefits and advantages described above may relate to one embodiment or may relate to several embodiments. The embodiments are not limited to those that solve any or all of the stated problems or those that have any or all of the stated benefits and advantages.

[00306] Any reference to 'an' item refers to one or more of those items. The term 'comprising' is used herein to mean including the method steps or elements identified, but that such steps or elements do not comprise an exclusive list and a method or apparatus may contain additional steps or elements.

[00307] As used herein, the terms "component" and "system" are intended to encompass computer-readable data storage that is configured with computerexecutable instructions that cause certain functionality to be performed when executed by a processor. The computer-executable instructions may include a routine, a function, or the like. It is also to be understood that a component or system may be localized on a single device or distributed across several devices.

[00308] Further, as used herein, the term "exemplary" is intended to mean "serving as an illustration or example of something".

[00309] Further, to the extent that the term "includes" is used in either the detailed description or the claims, such term is intended to be inclusive in a manner similar to the term "comprising" as "comprising" is interpreted when employed as a transitional word in a claim.

[00310] Moreover, the acts described herein may comprise computer-executable instructions that can be implemented by one or more processors and/or stored on a computer-readable medium or media. The computer-executable instructions can include routines, sub-routines, programs, threads of execution, and/or the like. Still further, results of acts of the methods can be stored in a computer-readable medium, displayed on a display device, and/or the like.

[00311] The order of the steps of the methods described herein is exemplary, but the steps may be carried out in any suitable order, or simultaneously where appropriate. Additionally, steps may be added or substituted in, or individual steps may be deleted from any of the methods without departing from the scope of the subject matter described herein. Aspects of any of the examples described above may be combined with aspects of any of the other examples described to form further examples without losing the effect sought.

[00312] It will be understood that the above description of a preferred embodiment is given by way of example only and that various modifications may be made by those skilled in the art. What has been described above includes examples of one or more embodiments. It is, of course, not possible to describe every conceivable modification and alteration of the above devices or methods for purposes of describing the aforementioned aspects, but one of ordinary skill in the art can recognize that many further modifications and permutations of various aspects are possible. Accordingly, the described aspects are intended to embrace all such alterations, modifications, and variations that fall within the scope of the appended claims.