Robotic mapping

Robotic mapping is a discipline related to cartography. The goal for an autonomous robot is to be able to construct (or use) a map (outdoor use) or floor plan (indoor use) and to localize itself and its recharging bases or beacons in it. Robotic mapping is that branch which deals with the study and application of ability to localize itself in a map / plan and sometimes to construct the map or floor plan by the autonomous robot.

Evolutionarily shaped blind action may suffice to keep some animals alive. For some insects for example, the environment is not interpreted as a map, and they survive only with a triggered response. A slightly more elaborated navigation strategy dramatically enhances the capabilities of the robot. Cognitive maps enable planning capacities and use of current perceptions, memorized events, and expected consequences.

The main problems

The key issue with the localization of the robot is the measurement error. They are caused by both signal-level interference and sensor malfunctions. If the errors made during the measurements were statistically independent, then there would be no problem – the robot could make more measurements and errors would recede. Unfortunately, they are statistically dependent, because they accumulate in time and affect how future measurement results are interpreted. This causes a lot of correlating systematic errors. Fulfilling these mistakes is the key to making a card. Many of the existing localization algorithms are complex for both mathematical and implementation reasons for this very reason.

The problem arises from the large dimensional nature of the objects being mapped. A detailed two-dimensional map, which is a routine robotic map, requires thousands of invoices to store data. A three-dimensional map of an object like a house would require millions of billions. From a statistical point of view, each such number can be part of a different dimension and therefore their mapping is very high in dimensionality.

Compliance problem
Compliance is one of the most difficult issues of localization. The problem is how to determine if the results from the sensor at different times correspond to the same object or not. For example, if a robot circles an object, when it reaches the same location, it must determine where it is located in relation to its previously created map. For this moment, the error of the position calculated by the robot’s internal methods can be infinitely high. The robot can set up a hypothesis about its location, but over time its number increases exponentially. Since the problem was so difficult as it was calculating, it was completely ignored until the end of the 1990s.

Changes in the environment
The environment changes over time. The appearance of the tree changes slowly during the year, other changes are faster, such as the location of cars and people or the state of the door. These dynamic environments add another way to interpret the variable data from sensors. Imagine a situation where the robot stands in front of a closed door, which, according to the last card, should be loose. This phenomenon can be described with two hypotheses -Whether the door status has changed or the robot is not where it thinks it is. There are very few algorithms that can create meaningful maps in dynamic environments. Instead, most algorithms proceed from the assumption that the universe is static and the robot is the only moving object and all other moving things are noise. Therefore, they can be used only at small intervals, in which the environment is relatively constant.

Basic methods
Probabilistic methods
Almost all modern localization algorithms are probable. They use probabilistic models for representing both the robot and its environment, and probable interference in order to transform the information received from sensors into charts. Probabilistic methods are popular because the localization of the robot is characterized by vagueness and sensory noise. Probabilistic algorithms simulate specific noise sources and their effects on measurement results. Among the localization algorithms, probabilistic approaches have proved to be most successful, all of which in some way stems from Bayesian theory.

Kalman filters use approaches
The classic approach to creating maps is based on Kalman’s filters. Kalman’s filters are also based on Bayes filters, but they are further developed and use the Gauss model in their derivatives. Kalman filters are the most common solution for many image processing issues. Kalman filters have a number of years, the popularity is based 1985 – in 1990 published scientific articles, which were offered by the Kalman filters in mathematical terms. This wording is in use today.

Expect Maximization Algorithms
Expectancy maximization algorithms (eXpectation maximization algorithms) is a newer alternative to Kalman filters. This is a statistical algorithm that predicts the most likely card according to the expected path of the robot. The prediction is repeated in cycles, and the results obtained so far are supplemented each time. The method of maximizing expectations is a good solution to the problem of compliance and is much more successful than Kalman’s filters. However, the use of Kalman filters is faster and therefore more pragmatic when it comes to getting real-time results.

Hybrid Solutions
Hybrid solutions combine probabilistic methods, such as Kalman’s filters, and the expectation maximization algorithm, using both of the better features. Probable solutions are very precise and achieve results that were not possible before they were put into operation. However, due to their complex and iterative design, they require large computing power, which can be both money and time consuming. It’s not practical to create a lifeboat for hours or days to map your surroundings. The solution is to optimize probabilistic methods using expectation maximization algorithms. The result is a system with a significantly lower power requirement, which focuses on maximizing expectations in the designated areas and analyzing them with probabilistic methods.

Mapping dynamic environments
Real physical environments are changing over time. As mentioned earlier, there are not many algorithms that can handle this problem. Most algorithms are based on the assumption of a static world, and thus unable to accept the situation where a known object has changed its location. The conclusion would be to change the location of yourself. However, there are algorithms that can be modified to cope with certain types of environmental changes. For example, Kalman’s filters can be roughly modified so that they can map the situation where objects known to them move slowly and their movement is similar to Brown’s movement in the trajectory.

The robot has two sources of information: the idiothetic and the allothetic sources. When in motion, a robot can use dead reckoning methods such as tracking the number of revolutions of its wheels; this corresponds to the idiothetic source and can give the absolute position of the robot, but it is subject to cumulative error which can grow quickly.

The allothetic source corresponds the sensors of the robot, like a camera, a microphone, laser, lidar or sonar. The problem here is “perceptual aliasing”. This means that two different places can be perceived as the same. For example, in a building, it is nearly impossible to determine a location solely with the visual information, because all the corridors may look the same. 3-dimensional models of a robot’s environment can be generated using 3D scanners.

Map representation
The internal representation of the map can be “metric” or “topological”:

The metric framework is the most common for humans and considers a two-dimensional space in which it places the objects. The objects are placed with precise coordinates. This representation is very useful, but is sensitive to noise and it is difficult to calculate the distances precisely.
The topological framework only considers places and relations between them. Often, the distances between places are stored. The map is then a graph, in which the nodes corresponds to places and arcs correspond to the paths.
Many techniques use probabilistic representations of the map, in order to handle uncertainty.

There are three main methods of map representations, i.e., free space maps, object maps, and composite maps. These employ the notion of a grid, but permit the resolution of the grid to vary so that it can become finer where more accuracy is needed and more coarse where the map is uniform.

Map learning
Map learning cannot be separated from the localization process, and a difficulty arises when errors in localization are incorporated into the map. This problem is commonly referred to as Simultaneous localization and mapping (SLAM).

An important additional problem is to determine whether the robot is in a part of environment already stored or never visited. One way to solve this problem is by using electric beacons, Near field communication (NFC), WiFi, Visible light communication (VLC) and Li-Fi and Bluetooth.

Path planning
Path planning is an important issue as it allows a robot to get from point A to point B. Path planning algorithms are measured by their computational complexity. The feasibility of real-time motion planning is dependent on the accuracy of the map (or floorplan), on robot localization and on the number of obstacles. Topologically, the problem of path planning is related to the shortest path problem of finding a route between two nodes in a graph.

Robot navigation
Outdoor robots can use GPS in a similar way to automotive navigation systems.

Alternative systems can be used with floor plan and beacons instead of maps for indoor robots, combined with localization wireless hardware. Electric beacons can help for cheap robot navigational systems.

Map submission
Internally, the robots do not represent data as people do, so they do not store the map in image format. Map representation is divided into geometric and topological:

A geometric representation represents objects in two-dimensional space at definite coordinates.
The topological representation represents only the interconnections between the objects.

Historically, a different breakdown has also been used:

The world-centered map represents objects in the global coordinate space.
The robotic map represents objects as they are with the robot.

Source from Wikipedia