Localization and Energy-aware path planning of mobile autonomous robots

(1)

Phd Course:

Emerging Digital Technologies Curriculum: Embedded Systems

Accademic Year

2016/2017

Localization and energy-aware path

planning of mobile autonomous robots

Author

Carmelo Di Franco

Supervisor

Giorgio C. Buttazzo

Tutor

Mauro Marinoni

(2)

Supervisor: Committees:

Giorgio C. Buttazzo Marco Caccamo

Scuola Superiore Sant’Anna University of Illinois Urbana-Champaign

Marko Bertogna

University of Modena

Luis Almeida

University of Porto

Arne Hamann

Tutor: Senior Research Engineer at Bosch

Mauro Marinoni Tommaso Cucinotta

(3)

Abstract

Nowadays, robots are being used in a broad number of applications. A team of robots is an effective solution for all those cases in which the primary goal is not achievable by a single unit. For instance, applications such as search-and-rescue and agriculture can benefit from a team for increasing the rate of coverage or allowing differentiating the capabilities of a single unit by carrying different sensors. The objective of this thesis is to provide instruments necessary for developing such team-based applications. In particular, it focuses on localization and energy-aware path planning techniques.

In the first part of this work, the problem of localizing a group of nodes in indoor environ-ments will be addressed. In this context, where GPS is not a viable solution, it is possible to locate a group of nodes by measuring inter-nodes distances with radio transceivers and thus deriving their coordinates. However, this is not an easy task for two main reasons. First, dis-tance measurements suffer from the presence of obstacles that alter the actual measured value. Whatever the sensor used, objects around the nodes affect the power of the message transmitted and create the so-called multi-path phenomenon, where multiple copies of the same signal are being reflected and arrive at the receiver. Errors in the distance measurements lead to wrong estimates of the coordinates. Secondly, even without errors, finding the coordinates from rela-tive distances is not trivial, and there exist cases in which a unique solution of the problem does not exist. Distance measurement errors then exacerbate the problem. In this work, both these issues are addressed, separately and in conjunction. Multiple sensor measurements are fused to increase the accuracy of distance estimation. A modified version of the Multidimensional Scaling (MDS), called enhanced MDS (eMDS) is proposed for reducing the ambiguities that come when the robot positions are measured with respect to a relative reference system. A novel algorithm to solve both problems is proposed, in which Non-line-of-sight measurements errors are modeled with a Gaussian mixture distribution. The parameters of such distributions are estimated and used to improve the accuracy of the coordinates that will act as a feedback for further refining the estimated distributions.

The second part of the thesis focuses on energy-aware path finding for unmanned aerial vehicles (UAV). In particular, many applications that involve the use of flying vehicles suffer from the problem of correctly estimating the energy consumed by the robot during their operations. Some path-planning algorithms could benefit from the knowledge of the energy consumption of the vehicle to adapt and produce energy-aware trajectories that are i) safe to fly, b) cost-effective regarding energy, c) and prone to dynamic changes due to disturbances such as high wind. In this context, an energy model for a quadrotor is designed. The energy cost of all the possible trajectories (acceleration, constant speed, landing, etc.) is characterized by using actual

(8)

measurements. Then this model is used to provide safety guarantees both offline (estimating the expected energy required for a pre-selected path) and online (checking whether if the remaining energy is enough to perform a safe return-to-home). The effects of the wind on the energy model have been studied and a run-time re-planning algorithm that changes the trajectory of the vehicle according to the actual disturbance is proposed.

(9)

Chapter 1

Introduction

1.1 Team of robots today

The use of robotic units to perform tasks autonomously is becoming widespread due to both technological and scientific advances, for example, the miniaturization of electromechanical systems and new sensing and control paradigms. It is natural to imagine that soon, teams of robots will be fully autonomous and capable of carrying out challenging tasks.

In recent years we have witnessed an increasing interest in using unmanned aerial vehicles (UAVs) for both military and civilian operations. From longstanding research areas such as homeland security, search and rescue missions, disaster relief operations, surveillance, to more recent applications such as hobby photography and transportation (e.g., Amazon Prime Air,

FAA-approved drone for medicine delivery1), UAVs have demonstrated significant technological

advantages and the myriad ways in which they can be applied are only increasing. Device minia-turization reduces dimensions and costs and thus enables the use of UAVs in new application fields. Agriculture is one of the emerging sectors in which UAVs are currently being adopted for detecting the state of vegetation and the growth of weeds, to plan for a timely and proper

intervention [GET08, ZTBSF08, KBGR+_{11]. In other applications, UAVs are used to inspect}

industrial plants [NBR+13], wooded survey area for fire prevention [CKBM06], or quickly reach

and monitor hazardous environments to support disasters interventions and rescuing. In every-day life, there are examples of robots that are becoming pervasive such as vacuum cleaner robots and quadrotors for video and image capturing. The latter ones, thanks to their stability and easiness of use, are becoming one of the most attractive gadgets both for children and adults. Their spreading in the last years was so extensive that nowadays the term drone is associated to a quadrotor. Thanks to an easy user interface, movie makers and photographers can plan trajectories that the quadrotor will follow, allowing to record scenes that were impossible before or highly expensive.

Another excellent example of an autonomous robot is Aquila, a large unmanned aerial vehicle developed by Facebook, that will beam internet signal to people in remote, underserved regions within a 60-mile diameter. Aquila, whose first successful flight test was completed on June 28th, 2016, is a solar-powered plane that is designed to fly for up to 90 days at a time. Figure 1.1 shows

(10)

a working Aquila drone whose wingspan are bigger than a Boeing 737 airplane. More complex systems are used in industry to perform different tasks such as transportation. Amazon, for example, is using fleets of Kiva robots in its warehouses to carry shelves of products to human workers, who then pick the items to be shipped. Figure 1.2 shows the Kiva robots at work while moving under the shelves and lifting them. In the future, Amazon is planning to use picking robots to automate the process of picking items from shelves.

Figure 1.1: Facebook Aquila

Figure 1.2: Team of industrial robots - Amazon

All these systems, whatever the simplicity of their task, have to localize themselves in the environment in which they are and perform some actions according to their plan strategy. For example, the vacuum robot has to understand its position inside the building and then plan a trajectory to cover the entire space. To perform this task, these robots are equipped with laser-ranges used to detect the obstacles around and reconstruct the map of the environment in which they are as long as they move.

(11)

1.1. Team of robots today

Figure 1.3: Drones in Agriculture

If single autonomous robots are already in commerce and can perform complex tasks, it is clear that many difficult tasks will be carried out by teams of robots in the future. The use of a team of autonomous robots requires coordination and cooperation strategies that are essential to perform tasks that one vehicle alone could not accomplish due to both its partial knowledge about the task and limited resources.

In one hand, a robotic team can avoid the human presence in risky situations, on the con-trary, it can represent the most convenient solution concerning performance, costs, and efficiency. For example, when someone is lost during a snowstorm or under a snow avalanche, improving the rate of coverage is fundamental in search and rescue operations since the survival rate of a person beneath the snow drastically drops after 15 minutes. In mine sweeping applications, it is advisable to spread a team of robots with mine detecting capability and equip only a small portion of them with sweeping ability, thus reducing the cost of equipment. In agriculture, drones will be used on a large scale to inspect the crops and warn about infected areas, thus allowing ground robots to spray herbicide only on that small amount of space, reducing the cost of herbicide significantly and avoiding to an unnecessary abuse. Figure 1.3 shows a Hexacopter flying over a vineyard and taking pictures of the field.

There exist infinite possibilities for applications of a team of robots. They can range from military to entertainment. Some examples of applications are the following:

• environmental and health-care, e.g., fire prevention, tracking of toxic clouds, search-and-rescue, inspection of areas in catastrophic situations.

• military, e.g., surveillance, demining areas, ...

• Logistic, manufacturing, large volume transportation, cleaning of buildings • Agriculture, monitoring, spraying herbicides, ...

(12)

1.2 Localization is underneath everything

Such coordination and cooperation of a team require solving different problems, such as nodes localization, data communication, tasks allocation, and planning of trajectories. Localization, in particular, is the core of many systems. It provides the position of one or more objects in a relative or absolute coordinate system. Depending on the particular application, there exist different localization techniques. In a system of a team of robots, for example, each robot is interested in knowing its position in a reference system, and at the same time, it may be interested in knowing the locations of the other team members. In sensor network applications, instead, we may be interested in tracking the locations of targets of interest, such as human workers operating in dangerous areas [FBVS10], people or items that need to be monitored, or sensors providing spatial information. Even if the scope is to find the locations of some elements, the two cases have different problem formulations, and various sensors and techniques can be used to reach the goal.

Some examples of applications in which localization is used include [DOK98] in which each team member can measure the relative position with respect to its closest neighbors allowing the team be controlled in a formation. In [CBF04], the robots have to maintain connectivity while moving; hence the robot path is computed to ensure that the network partition never occurs during the robot’s motion. The work in [WCLPZ05] explores the sensor relocation in order to deal with sensor failure or respond to new events.

1.2.1 Challenges in indoor localization

An infrastructure is usually built to provide an absolute reference system and to help in localizing nodes. An example of such as an infrastructure is the Global Positioning System (GPS) which is a very common solution used for outdoor scenarios. It is widely used to provide an absolute position in many fields, from the most famous car navigator to mobile phone applications that require the knowledge of the physical location of the user. Nevertheless, GPS is not a feasible solution in indoor environments or in particular places where the signal is not available. An alternative solution is to build a dedicated infrastructure which is very common in structured environments such as hospitals or industries where you have access to power supply, and sites do not change. In this case, we can refer to infrastructure-based or absolute localization.

However, to build an infrastructure is often costly and not feasible in emergency situa-tions. For example, a search-and-rescue robot may have to visit unknown and unstructured environments and cannot rely on an existing infrastructure. Moreover, a team of robots may be interested in knowing the relative position of each member with respect to its location. In this cases, it is possible to use relative localization techniques by exploiting visual cameras or laser-ranges, which require high computation, or ranging-sensors which measure the distance between nodes. The latter ones are very attractive since they do not need expensive hardware, do not require much computation and power, and hence can be used in embedded systems. In this case, we refer to infrastructure-free or relative localization.

Despite the presence of an infrastructure, indoor localization techniques rely on radio transceivers that can measure the distance between neighbors. Such distances are then used to estimate the

(13)

1.2. Localization is underneath everything node coordinates. The approach that derives node coordinates from inter-nodes distances is called range-based localization, and it is composed of two phases. In the first, distance mea-surements between the nodes are collected and spread through the network. In some cases, other measurements are obtained such as odometry, images, or acceleration from inertial units. In the second phase, these measurements are used to derive the coordinates of the nodes.

The inter-node distances are usually obtained with techniques such as RSSI, Time of Flight (ToF), and Time Difference of Arrival (TDoA). The choice strongly depends on from the accuracy we want to achieve in the particular application we have. For example, RSSI, which uses the correlation between the distance and the intensity of a radio signal, is suitable for WSN composed of a huge number of nodes since it requires inexpensive hardware and minimum power. However, it is very noisy and not suitable for precise localization, while ToF is very accurate (in the order of centimeters) but it requires a ultra-wideband (UWB) transceiver. All these ranging techniques are sensitive to the presence of walls, obstacles, liquids, and electromagnetic devices.

In indoor localization, there exist several challenging problems that, if solved, can improve the distance estimation and hence provide a better localization. Some of them, specific to the first phase (ranging phase), are the following:

• distinguish between Line-Of-Sight (LOS) and NLOS is crucial to reduce significantly the error in distance measurements. UWB techniques such as ToF have a high accuracy when in LOS, however, if there are some obstacles the delay introduced by the radio signal passing an obstacle results in a positive bias in error.

• An intelligent data fusion between different measurements is needed to overcome the weakness of the measures we are collecting. For example, RSSI is fast, scalable, and inexpensive but is not very accurate. ToF is reliable but slower than RSSI and not scalable since it is possible to measure a single distance-pair at a time. If the node is equipped with a IMU, it is possible to derive its dynamic and use other sensors such as ToF to avoid the drift caused by the noise.

• Many systems pre-calibrate the environment to improve the error of sensors such as RSSI. However, if a node is moving, the overall calibration is not always correct. Adapting and re-calibrating the system according to node dynamics and changes in the environment can be crucial in improving the accuracy.

However, an accurate Data & Sensor fusion is not enough. The problem of deriving the node coordinates from distance measurements is not trivial. Due to geometric ambiguities, it is not always possible to find a unique solution. A lot of research has been done to determine the conditions for a unique realization. The problem is strongly connected both to the network topology, the particular geometry, and the measurement errors. Many other challenges arise in the second phase (estimation phase ):

• In relative localization, the lack of an absolute reference system can lead to location ambiguities. Moreover, it is hard to have a correlation between time instants when nodes

(14)

are moving. Some path planning or formation control algorithms may benefit from a reference system that is coherent over time.

• The distribution error of ranging measurements can be modeled to distinguish between LOS and NLOS. An algorithm that takes into account general noise models will result in a better accuracy. Moreover, it may be possible to exploit the estimated coordinates to improve the error distribution.

1.3 Autonomous robots: path planning

Once a node (or a team) is located in a reference system, we want it to perform some actions. There are different path planning algorithms according to the behavior we are implementing. For example, we might want to visit a set of points or visit only a subset of them. In robotics, the issues related to mobile nodes motions are so broad that it is important to distinguish between some terminology. In general, as described in [LaV06], Path planning can be defined as a sequence of logical operators or actions that transform an initial world state into a desired goal state.

Depending on the field of interest, Path planning assumes different meanings. Within robotics, the term is meant to design algorithms that generate useful motions under some uncertainties. It means determining what actions are appropriate for the robot so that it reaches a goal state without colliding into obstacles. It can also involve algorithms for fleets of robots that have a common goal and have to be coordinated. Within artificial intelligence, path planning means to design decisions-theoretic models to compute appropriate actions. The primary problem in this field is that a node may take a decision in the presence of other policy makers that may interfere with the outcome. Within control theory, the focus is on algorithms that compute possible trajectories knowing the kinematics and dynamic of a robot. While in robotics, the path planning algorithms have some global constraints such as obstacles in the sense that they are external to the robot, in control theory there exist some local constraints to take into account such as the allowable velocities that a robot can have at each instant.

In this work, we will focus only on the field of robotics. The path planning algorithms will produce high-level trajectories, in term of points on the plane called waypoints, according to specific planning strategies.

1.3.1 Challenges in Path Planning algorithms

Even though the control performance and operation of UAVs has become very sophisticated, a big challenge remains on how to guarantee at runtime that they can safely coordinate and achieve the desired goal (e.g., reaching a target and return to a base station). In fact, most control strategies usually assume one of the following limiting conditions: either i) there are no disturbances, and the system is not compromised, operating in perfect conditions (e.g., battery fully charged, no environment disturbances) or ii) worst-case scenarios are considered (e.g., maximum energy consumption, strong disturbance), which in most cases is an unnecessary over-constrained condition that results in bad performance and under-use of resources.

(15)

1.4. Scope of this thesis Coverage path planning, which is the operation of finding a path that covers all the points of a given area, has been addressed by several authors from a geometrical point of view. However, other issues such as energy, speed, acceleration, and image resolution are not often taken into account. Path planning algorithms usually try to minimize the distance or the time, since they are proportional to the energy. However, in some cases, this correspondence is not so linear, and a more accurate method should be used. For instance, a quadrotor consumes energy when it is hovering, or the wind and the air can impact on the energy consumed. Considering such cases results in additional challenging problems that are related to energy issues. For example: • An effective energy model for a quadrotor is needed, to be able of estimating the energy consumed by the robot during different motion trajectories. Path planning algorithms could exploit such energy model to plan trajectories that are aware of the energy consumed during the motion. Moreover, Such information on the energy consumption could lead to the definition of some safe techniques that will guarantee that the overall energy required to perform some actions will not exceed the energy of the battery, or in more complex scenarios it could provide some online fail-safe mechanisms that may prevent possible crashes.

• many control strategies do not consider disturbances or add too many constraints being too pessimistic. It could be useful to see how the disturbances such as wind, impact in the energy consumption of a UAV. In this way, it could be possible to take on-line re-planning decisions that may prevent crashes or unexpected situations. For example, during a planned trajectory a strong wind may lead to high-cost trajectories regarding energy that could compromise the current operation.

1.4 Scope of this thesis

1.4.1 Contribution of this work

The overall scope of this work is to provide localization and navigation techniques useful to build applications based on a system composed of one or more autonomous robots. However, as stated above, range-based localization algorithms suffer from issues both in the ranging phase, where the problem is to collect and provide accurate measurements through Data & Sensor fusion, and in the estimation phase. For this reason, the work is conceptually divided into three sections that will focus the three different aspects highlighted before. The outline of the thesis is represented by a ”V” diagram in Figure 1.4 that helps to visualize both the chapter order and the level of abstraction of the addressed problem.

In the first part of this work, the effects of the error in distance measurements are studied. In particular, RSSI and UWB ranges suffer from the problem of multipath effect inside buildings due to the presence of objects and walls. Such a problem is addressed in two different ways: by using data fusion techniques to improve the accuracy in RSSI-based localization applica-tions (Chapter 3) and estimating the position of the nodes and the error distribution of UWB measurements jointly (Chapter 4).

(16)

Figure 1.4: Graphical plot of the outline of this work

In the second part of the work, issues related to the computation of the node positions (estimation phase) are addressed and two localization algorithms are proposed: GM-MDS in Chapter 4 and eMDS in Chapter 5. The first, to handle measurements with multi-modal distribution error while the latter to provide a correlation between successive discrete time instants in relative-localization applications.

Finally, in the third part of the work, a energy model for a quadrotor is proposed (Chap-ter 6 and Chap(Chap-ter 7). Such a model has been used i) to implement an energy-aware coverage path planning algorithm with resolution constraints and ii) to provide offline and online safety guarantees.

1.4.2 Outline

In this chapter, an introduction of the main localization and path planning challenges is pro-vided. Chapter 2 will provide an overview of the current state of the art in Data & Sensor fusion, localization techniques, and path planning algorithms.

Chapter 3 will focus on the fusion of different measurements. More specifically, the high noise and poor accuracy of RSSI will be improved by creating an adaptive channel estimation algorithm that will adapt its behavior according to the changes in the environment. It will merge the data from IMU, odometry, and RSSI,ToF resulting in an accuracy comparable to the one of the ToF but with the advantages of having a fast and scalable system.

Chapter 4, will focus on the problem of exploiting more complex error distributions to improve the coordinate estimation also trying to estimate if a link is in LOS or NLOS. A localization algorithm that jointly estimates the node coordinates and the distribution error of the measurements are proposed. Thus, the distribution error will be used to determine the LOS-NLOS links and further improve the accuracy of the localization. In this context, a novel formulation of Multidimensional Scaling (MDS) that is general for any noise with a Mixture of Gaussian (MoG) distribution will be presented.

Chapter 5 will focus on the problem of having a correlation over the time of the node coordinates in a relative reference system. Understanding where the other nodes are facing inside a relative reference system from the point of view of each robot is needed in many applications, such as formation control. More specifically, a modified version of MDS is introduced in this

(17)

1.5. Notation used in this thesis chapter that exploits the exchanged information on the velocities of the team members.

Chapter 6 will propose an energy model for a quadrotor and an energy-aware coverage path planning algorithm. The energy model is hence used to provide offline and online guarantees for ensuring the success of the mission.

Chapter 7 will present the case in which some disturbances, such as the wind, impact in the energy required to perform some trajectories, and the energy model proposed in the previous chapter is formalized to take into account the wind. Finally, Chapter 8 will state the conclusions emphasizing the pros and cons of our contribution, discussing the limitations, and illustrating future works.

1.5 Notation used in this thesis

Since the work will cover topics at different levels of abstraction (measurements, data fusion, localization algorithm, energy models and path planning strategies), it is not possible to have a unique definition of the variables along with all the chapters. For example, variables such as α, β, n, m, k will assume a particular meaning depending on the context in in which they are used. However, we will try to keep the notation as consistent as possible.

Summary

In this chapter, we introduced the general outline of the thesis starting from a general overview of the current and future applications for a team of autonomous robots. Among the huge number of possible challenges present today in robotics, we highlight the im-portance of localization as a key characteristic of any robotic or sensors system. On top of that, we scratched the surface of another challenging topic, i.e., Path planning. We described the challenges in both areas and shortly summarized our contribution.

(18)

Background and Related Work

2.1 Localization in WSN

With the term Wireless Sensor Networks (WSN) we refer to a group of sensors that can be de-ployed in any environment and that communicate with each other through a wireless network. Such sensors (also called nodes) can be static or mobile and have some capabilities according to the particular application they are designed for. Robots, instead are nodes that can perform specific activities such as moving, planning trajectories, do some actions. Both robots (also re-ferred as mobile nodes, sometimes) and sensors can be localized using the same techniques. They usually have a transceiver for communication, and some additional hardware. Inside a building, where GPS is not an option, localization is achieved by measuring the distances between nodes or by inferring some information from the network. In this context, we can distinguish between two different type of localization techniques: Range-free and Range-based (or Distance-based) localization. Figure 2.1 shows a diagram that summarizes the main localization techniques in WSN.

Localization in WSN

Range-Based Localization

Time based Toa, TdoA, ToF

Signal Property

based RSSI

Direction based AoA

Range-free Localization

Pattern matching localization Hop-count based

localization DV-Hop, etc.

Figure 2.1: Localization in Wireless Sensor Network

In Range-Free Localization, the coordinates are computed in a coarse way using the network topology and provide comparative information about where the node could be. It is mainly

(19)

2.1. Localization in WSN utilized in those applications in which you need an overall information about the location of the nodes to give a spatial information to other collected information. Nodes do not have to perform additional actions actively. In Range-Based Localization, nodes measure the distance between each other and then derive the node coordinates. This type of localization is much more precise (even in the order of centimeters), but it requires additional hardware, computation, and communication.

Even if in this work we will focus only on Range-based localization, in the next section we will give an overview of both localization techniques.

2.1.1 Range-Free localization

Range-Free Localization algorithms are mainly used for applications with a large number of cheap sensors with limited battery and small computation. In such cases, hundred of sensors are deployed to cover an area of interest and collect some data (e.g., temperature, humidity, etc.) which you want some spatial information. The data gathering is usually needed for months (or even years) without changing the battery. Range-based solutions often require extra hardware whose cost may be too high with the location precision necessary for the application. Moreover, it will introduce waste of energy due to increased communication, computation, and hardware. Hence, in such cases, Range-free localization is it is a perfect solution since it exploits the pre-existent radio communication between the nodes (used to collect the aggregated data) to derive the node coordinates without the need for any additional hardware. We briefly summarize the state of the art range-free localization algorithms.

• Centroid Scheme [BHE00] by N. Bulusu and J. Heidemann • DV-Hop Scheme [NN03b] by D. Niculescu and B. Nath • Amorphous Scheme [Nag99, NSB03] by R. Nagpal

• APIT [HHB+_{05] by Tian He et Al.}

All these algorithms have in common the fact that they do not need to measure the distance between nodes actively. Instead, they use the number of hops in the network to derive an average distance between the nodes. In the Centroid Scheme, the location of some anchors and the number of hops are combined in a simple formula that estimates each node coordinate. In DV-Hop each node records the minimal number of hops that separate it from the other nodes and ignore longer paths. Then, an average hop-distance is computed using the anchor coordinates and the number of hops in between them. The Amorphous Scheme is similar to DV-hop but calculates the average hop distance differently. APIT tries to narrow down the possible area in which a target node resides by performing a Point-In-Triangulation Test (PIT), i.e., a node chooses three anchors from all audible anchors (anchors from which a beacon was received) and tests whether it is inside the triangle formed by connecting these three anchors. After repeating this PIT test with all the different audible anchor combinations (or a subset of them) the center of gravity of the intersection of all of the triangles in which a node resides its estimated and will correspond to the node coordinate. A comprehensive comparison of these

(20)

Another Range-free approach is based on Pattern matching methods, also called map-based

or fingerprint [CWZ+12]. The fingerprint localization involves two phases. In the first step, the

map is divided into blocks, and for each location, the signal strength of received radio messages is collected offline and recorded in a database called radio map. In the second phase, the node locations are found by matching the currently observed signal with the prerecorded value on the database [LOJ11, SCST11].

2.1.2 Range-based localization

In Range-based techniques, the nodes coordinates are derived from distance measurements. Nodes actively measure the distance between pairs and exchange this information in the net-work. An algorithm that runs on each node (distributed) or on a particular unit (centralized) then derives the node coordinates from the measurements. Hence, Distance based localization consists of two phases:

• Ranging phase: The nodes collect distance measurements, and spread the information to the other nodes (or a central unit)

• Estimation phase: The localization algorithm (centralized or distributed) takes as input the measurements and derives the node coordinates.

Sometimes, there are nodes which position is available. Such nodes are usually referred as anchors, or beacons. If there are anchors in the network, their coordinates act as an absolute reference system. If there are no anchors, the estimated coordinates will be inside a relative reference system. In this case, the problem of finding the coordinates from distance-only mea-surements will give a unique solution (under certain assumptions) up to a rotation, translation, and reflection. According to the presence of anchors, we will refer to Absolute and Relative Localization, respectively.

Measuring distances between wireless nodes is a topic that has been widely explored by many authors. The most common time based techniques rely on one-way Time-of-Arrival

(ToA) measurements [CSMC04,STK05,GTG+05], Time Difference of Arrival (TDoA) [PCB00,

ZLC10, GG03], and Round-Trip Time-of-Flight (RT ToF) measurements [NWR09, AHK13]. A detailed description of time-based tecniques is given in Section 2.2.2.

The Angle of Arrival (AoA) based methods compute the angle between neighbors instead of calculating the distances. To get the angle, they require directional antennas or antenna arrays and no time synchronization between nodes is needed. In literature, some works that rely on

AoA include [NN03a, KVAEL+10].

Signal strength based techniques, as the name implies, obtain range estimations from the strength of the received RF signal [JKK12]. In open space and without interference, there is a predictable relation between RSSI and distance, however, in the presence of interference, reflec-tion, and refracreflec-tion, this relationship is no longer accurate. Despite that, most of the modern wireless transceivers possess the capability of measuring the RSSI intrinsically. Therefore, if the application only requires a coarse localization, either for navigation or topology estimation purposes, the RSSI can still be very useful.

(21)

2.2. Distance measuring techniques 2.1.3 Technologies used in localization

Positioning systems rely on different technologies according to the context of interest [FNI13]. Figure 2.2 shows a diagram containing the technologies used in localization.

GPS is the most popular and worldwide radio navigation system that provides geo-localization and time information to any GPS receiver anywhere on or near the Earth by using a system of satellites orbiting around the earth. To get a coordinate, The GPS receiver has to be in Line-of-Sight with at least four satellites. The position error is in the order of meters and decreases if the receiver is connected with more satellites. It is mainly used for navigation applications where you want to track a user/object/vehicle. However, it does not work indoor, and it is attenuated by surrounding buildings and outdoor obstacles. Hence, it is not a valid option for accurate localization and indoor localization.

Radio Frequency (RF) technologies are commonly used in indoor location systems because of the high penetration of radio waves through walls and obstacles. There exist different RF based technologies that differ depending on the electromagnetic band in which the radio works. They can be divided into narrowband (RFID, Bluetooth, WLAN, and FM) and ultra-wideband (UWB).

Also Infrared Radiation (IR) based technologies have been investigated too. However, they have some disadvantages like security, privacy issues and suffer from the interference from fluorescent light and sunlight.

Ultrasound technologies operate at very low frequencies. The advantages of using ultrasound are in the cost compared to the level of accuracy. However, they are unable to penetrate walls. Finally, many works developed hybrid positioning systems composed of 2 or more technolo-gies. In this way, it is possible to mitigate the limitation of some technologies and increase the location accuracy. For example, Google Maps reduces the GPS error in between buildings by using RF technologies such as WLAN whose location is known (shops, universities) or the radio infrastructure for mobile communication. As the work on [LYAU11] shows, hybrid tech-niques significantly improve localization results, namely the authors simulated positioning using combinations of ToA, TDoA, and RSSI, showing that RSSI has limited usefulness where time-based techniques are available. More efficient solutions usually combine different measurements types to overcome their limitations. For example, ToF ranging is precise but requires a long time to range one robot [OAS12], while RSSI allows several receivers to range one transmitter simultaneously but suffers from high noise.

A comparison of typical positioning systems used for localization is given in [FNI13].

2.2 Distance measuring techniques

As previously described, Range-based techniques are composed of two phases. In the first one, nodes measure the distances between their neighbors and spread this information around the network. In this section, we will describe in detail the two most critical distance measuring techniques used in this work, i.e., RSSI and ToF. In particular, the latter one will be compared to the other time-based techniques.

(22)

Figure 2.2: Diagram of positioning system tecnologies.

2.2.1 Received Signal Strength Indicator (RSSI)

The Received Signal Strength Indicator (RSSI) is a measurement of the power of a received radio signal. When a transmitter sends a packet, one or more receivers can derive the distance from the transmitter by measuring the power of such radio signal. The correlation between the power received by the antenna and the distance from the transmitted is expressed by the Friis equation [Sey05]. Given two antennas, the ratio of the power available at the receiving antenna,

PR, to the output power to the transmitting antenna, PT, is given by:

PR

PT

= GTGRλ

2

(4π)2_dα

where GR and GT are the antenna gains of the receiving and transmitting antennas, λ is

the wavelength, d is the distance between the antennas, and α is the path loss exponent. RSSI is measured by the transceiver, and its value is stored in dBm inside a register of the microcontroller. Hence, we can convert the previous equation in dBm as

RSSI = 10 log(PR·103) = 10 log

PT GTGRλ2 (4π)2_dα · 10 3 = 10 log PT GTGRλ2 (4π)2 · 10 3 −10 log(dα) .

Assuming GT = GR = 1 and knowing that λ = c/f , where c is the speed of light and f

is the frequency of the transceiver (e.g., 2.4 GHz), we can express RSSI as a function of the distance.

Definition: The power of a received radio signal decreases logarithmically as the distance between the two antennas increases:

RSSI = ρd= ρ0− 10α log(d) (2.1)

where ρ0 and α are two constants that characterize the propagation model. The first is

defined as the RSSI value when the distance between the two antennas is 1 meter and depends on the specific hardware, while the second is known as the path loss exponent.

(23)

2.2. Distance measuring techniques

d = 10(ρ0−ρd)/10·α _(2.2)

The accuracy of RSSI strongly depends on the two parameters ρ0 and α that describe the

path-loss model (also named channel model ). The presence of obstacles and walls profoundly impacts on the strength of a received packet and hence on these two parameters. For example, a barrier will reduce the received power while obstacles produce multipath and increase the signal strength. Hence, an accurate choice of these two parameters results in more accurate

measure-ments. Table 2.1 shows some values of the path loss exponent α in specific environments1).

Environment α

Free space 2.0

Retail store 2.2

Grocery store 1.8

Office, hard partitions 3.0

Office, soft partitions 2.6

Metalworking factory, line of sight 1.6

Metalworking factory, obstructed line of sight 3.3

Table 2.1: Some values of α in specific environments

Some researchers pre-estimate the channel model of the area of interest with some a priori

channel measurements [APB+_11,BHA+_{13] in order to estimate distances with RSSI only.}

Oth-ers perform online channel estimation, either based on anchor nodes [CR13, BLCF12] or based

on external sensors [BHA+_{13]. However, a priori data may be unavailable or unreliable, i.e.,}

ei-ther ei-there is no previous knowledge or ei-there were severe changes to the environment. Moreover, estimations based on measurements between anchor nodes are not compatible with unknown environments and estimations performed with external sensors require extra equipment.

In other cases, when only a coarse localization is needed, some researchers [LAWS07, OLAA13] avoid estimating the distance from the RSSI measurement using any propagation model and all localization is performed considering the ”distance in the RSSI space”, i.e., not an estimate of relative physical distance.

2.2.2 Time-based measurements

In time-based localization systems, accurately determining signal arrival time is crucial for accurately estimating position. The Time of Arrival (ToA) of a radio packet directly depends on the distance between transmitter and receiver. Measuring this time is challenging, however,

as the propagation of radio waves in air is extremely fast, 3.0_{· 10}8 _{m/s. With the speed-of-light}

propagation of radio frequency signals, even 1 ns of error in estimating a signal’s arrival time can result in up to 30 cm of ranging error. While ToA measures the absolute time of arrival at a certain node, Time Difference of Arrival (TDoA) measures the time difference between two receiving signals. However, both techniques require synchronization of the network since the measurement is unilateral that is not always possible (e.g., unknown environments, anchor-free applications), or it is too expensive.

(24)

Roundtrip Time of Flight (ToF), instead, eliminates the need for global clock synchroniza-tion. For simplicity, we will refer to the RT ToF, simply as ToF. In order to derive the distance, instead of measuring the time of one-way trip, the transmitting node measures the time that a message needs to go to the receiver and return. Despite that, since some local processing needs to be done on the receiver before sending the reply, the processing time has to be very well known. Thus it is usually done in hardware. ToF technique alleviates the problem of clock synchronization but is burdened by the difficulty of determining the response delay of the target. Adding to that, since the ranging operation is between two units, it needs a long time to range several units. Thus it may not accommodate fast-moving robots.

Time-based techniques are usually performed with UWB devices. In fact, the main difference between UWB and other radio frequency signals is that UWB transmits its signal over multiple bands of frequencies simultaneously, in the interval of 3.1 to 10.6 GHz, exceeding a bandwidth of 500 MHz or 20% of the center frequency. In the time-domain, this is typically achieved through the transmission of short pulses (with a duration on the order of nanoseconds) which have high characteristics. Additionally, UWB systems typically run on very low duty cycles, and, thus, are very low power. In the context of localization, UWB features high positioning accuracy (due to the fine time resolution of the emitted signals) and excellent material penetrability (due to the large bandwidth).

Nanoloc Device

The nanoLOC TRX transceiver shown in Figure 2.3 is a highly integrated mixed signal chip offering robust wireless communication and ranging capabilities. It utilizes Chirp Spread Spec-trum (CSS), a unique wireless communication technology developed by nanotron for the 2.4

GHz ISM Band 2. It performs a patented messaging scheme called Symmetrical Double-Sided

two-way ranging which allows ranging between two devices. First, a message is sent from the TX to the RX node, processed and sent back to the TX. Hence, The first node can estimate distance by computing the propagation delay through the air and knowing the hardware pro-cessing delay of the transceiver. Then, a message is sent from the second node to the first one, similarly. The distance is computed by the second node and sent back to the first node. Both nodes estimate the distance, and this is why the scheme is called double-sided two-way ranging. SurePoint localization Device

SurePoint[KPCD16] is a system for drop-in, high-fidelity indoor localization. It is built on the recently available commercial ultrawideband radio DecaWave DW1000 UWB transceiver that

uses the recent 802.15.4a standard [G+11]. SurePoint 2.4 achieves its high accuracy by

lever-aging the high-fidelity time-of-arrival primitive commonly provided by ultra-wideband radios. It mitigates the problem of frequency and spatial diversity by exploiting multiple communica-tion channels and multiple antennas. Each node features three physically separated antennas providing modest spatial diversity placed at 120 degrees offset to help combat nulls from cross-polarization of antennas. Each antenna uses a largely non-overlapping channel provided by

(25)

2.3. Estimation phase: localization algorithms

Figure 2.3: A nanonPAN device, developed by Nanotron, offering robust wireless communication and ranging capabilities.

Figure 2.4: SurePoint Hardware includes a DW1000 UWB transceiver and 3 antennas. It is composed of a TriPoint module (that implements the SurePoint system) and a Tritag Carrier Board that includes a BLE interface.

802.15.4a. All of the permutations of three antennas of the sender, three antennas of the re-ceiver, and three channels results in 27 independent measurements of the UWB channel. These measurements are then averaged in a single range estimate with decimeter accuracy.

2.3 Estimation phase: localization algorithms

The problem of finding Euclidean positions starting from distance measurements only is not trivial. This is a complicated issue for two main reasons: (i) the existence of a unique realization depends on the topology of the graph [Hen92], and (ii) noise on the distance measurements compounds the difficulty of finding a correct realization.

Consider a collection of n sensors with positions X = [x1,· · · , xn]> ∈ Rn×r. Suppose that

(26)

undirected graph G = (_{V, E) with vertices V := {1, . . . , n} and |E| = m edges. An edge (i, j) ∈ E} from sensor i to sensor j is an ordered pair and exists if the two sensors can communicate and thus measure their distance. We consider the problem of estimating X using range-only

measurements ˆdij between pairs (i, j) of nodes that are in communication. This problem is

known as the graph realization problem. Even with no error in the distance measurements, this is a complex problem and depends on the topology of the network. Two types of ambiguities lead to multiple possible graph realizations, i.e., flex and flips ambiguities. In the first case, one or more vertices can pivot freely since they are under-constrained. A flip (or reflection) happens instead when a part of the graph can be reflected across two vertices. Figure 2.5 shows an example of flex and flip ambiguities in 2D.

Figure 2.5: a) the graph suffers from a flex ambiguity since nodes 3 and 4 can be freely moved by respecting the distance between the other neighbours. Hence there exist infinite solutions. b) the graph suffers from a flip ambiguity of node 3 that can have two possible coordinates.

Aspen et al. [AEG+06] provide a theoretical foundation for network localization regarding

graph rigidity theory. The authors show that the network has a unique localization if and only

if it is generically globally rigid. A graph G with n_{≥ 4 vertices is generically globally rigid in}

R2 if and only if it is 3-connected and redundantly rigid (which means rigid after removal of

any one edge) in R2_{. Various tests for 3-connectivity are known. Tests for redundant rigidity}

in R2 have also been derived (See [AEG+06]).

However, under the presence of noise in the range measurements, there is a new type of am-biguity that is introduced, which means that even when the graph is rigid, alternative incorrect realizations may result. Figure 2.6 shows an example in which the uncertainties introduced by distance measurements produces a flip around an axis. It is worth noting that this type of flips happens around an axis created by three nodes that are almost collinear.

Moore et al. [MLRT04] propose an algorithm that addresses this problem, and is capa-ble of localizing a sensor network in the presence of range measurement noise. The authors assume an unbiased Gaussian noise distribution with known variance that is uniform among all links in the network. They introduce the probabilistic notion of robust quadrilaterals as a way to avoid ambiguities that would otherwise corrupt localization computations. Simi-larly, several works present methods that exploit geometric relations between node-to-node distances [CAM06, KKM09, KKM10, DLF14].

(27)

Figure 2.6: The figure shows a graph that is affected by a flip even if it is rigid. The flip results

from a wrong estimation of the distance d23. This type of ambiguities are more likely to happen

when the nodes to which the affected node is connected(in this case node 3) are almost collinear. nodes in the network. If the algorithm is computed by a unit only, then the algorithm is centralized. If the computation is distributed among all the nodes, we refer to distributed algorithms. If the number of nodes inside the network is small, e.g. a small team of robots, using a centralized approach does not affect the performances. Usually, each team member acts as a centralized unit and perform its local computation. In networks with a large number of nodes, using distributed algorithms is preferred since centralized approaches will require a lot of communication overhead, latency, and high computation on the central unit. Distributed localization algorithms can be classified into two general schemes: multi lateration and successive refinements. In [KKM09], Khan et al. introduce a distributed localization algorithm, which uses the barycentric coordinates of a node with respect to its neighbors. They show the convergence of the localization algorithm by associating with it an absorbing Markov chain whose absorbing states are the anchor nodes. Diao et al. [DLF14] relax the assumption that all nodes must be inside the convex hull of the anchors. More recent results include [LSRB16]. Kar et al. [KMR12] study distributed static parameter estimation with nonlinear observation models and noisy inter-sensor communication.

2.3.1 Multidimensional Scaling

An alternative centralized distance-based approach builds on the theory of Multidimensional Scaling (MDS) [Kru64] and formulates network localization as a least-squares problem. MDS is a general technique that represents a set of elements ”in a r-dimensional space” using a similarity measure between pairs of elements. Initially, it was used to provide a spatial visualization of a set of elements in a 2D or 3D space. Applications of the MDS algorithm include scientific visualization and data mining in several fields [BG05]. When used for localization, similarity

(28)

is measured via the Euclidean distance [BG05]. There exist several implementations of MDS, such as classical MDS, metric MDS, non-metric MDS, depending on the characteristics of the distance information. Variations consider a weighted version of distributed MDS, termed distributed weighted Multidimensional Scaling (dwMDS) [CPHI06], and a version that accounts for missing distances and local information [SR04, SRZF04].

In classical metric MDS, proximities are treated as distances in a Euclidean space. The algorithm recovers the coordinates of the elements by minimizing the mismatch of the following function: min X S(X) = minX n X i=1 n X j=1,j<i wij( ˆdij − dij(X))2 (2.3)

wij are weights that assign a value in [0, 1] to the goodness of the measurement ˆdij and dij(X) =

kxi− xjk. Equation (2.3) is also called stress function. The weights and the distances are stored

in two matrix W, D called respectively Weight matrix and Distance matrix. Both matrices are symmetric and have zeros on the diagonal.

The objective function (2.3) can be minimized in various ways, such as steepest descent approach [Kru64]. However, a significantly better method for minimizing it (in terms of guar-antees and convergence rate) is an iterative method called Scaling by MAjorizing a COmplicated

Function (SMACOF) [DL05] that instead of minimizing a complex function_{S(X), at each step}

minimizes a simple convex function T (X, Z) which majorizes S (T bounds S from above and

touches its surface at point Z). The iterative procedure is the following:

Algorithm 1 SMACOF

input: initial position estimate X(0)

stress function _S majorizing functionT repeat Xk_{← min} X T (X, X k−1₎ until S(Xk−1₎_{− S(X}k_{) <}

Figure 2.7 shows an example of the SMACOF algorithm in an unidimensional case. SMACOF implementation

The stress function σ can be expanded as follows:

S(X) = X i<j≤n wij( ˆdij− dij(X))2 = X i<j wijdˆ2ij+ X i<j wijd2ij(X)− 2 X i<j wijdˆijdij(X) (2.4)

Note that the first term is a constant and the second term is quadratic in X and therefore relatively easily solved. The third term is bounded using the Cauchy-Schwarz inequality using the fact that:

dij(X) =kxi− xjk = kxi− xjkkzi− zjk

kzi− zjk ≥

(xi− xj)T(zi− zj)

kzi− zjk

(29)

Figure 2.7: SMACOF algorithm (uni-dimensional illustration).

Hence, the third term can be bounded by: X i<j wijdˆijdij(X)≥ X i<j wijdˆij (xi− xj)T(zi− zj) kzi− zjk (2.6)

Thus, we have a simple quadratic function τ (X, Z) that majorizes stress:

S(X) ≤ T (X, Z) =X i<j wijdˆ2ij + X i<j wijd2ij(X)− 2 X i<j wijδij (xi− xj)T(zi− zj) kzi− zjk (2.7)

2.3.2 MDS with limited range and communication errors

The MDS algorithm requires a symmetric distance Matrix D (and eventually, a weight matrix W ) as input. However, since the estimated distances are subject to errors, the measured

distance bdij may be different from bdji, leading to a non-symmetrical matrix. In this case, D

must be converted into a symmetrical form. Possible solutions which are commonly adopted

in the literature [OLAA13] are to calculate the mean value of bdij and bdji, or to just select one

of the two as a unique value. If instead a reliability weight is associated with each distance information (e.g., an indicator of the link quality), another possible solution could be to select that which has the highest weight. Moreover, due to limited range, it may happen that not all pairwise distances are known. However, a fully connected matrix is required as an input to MDS. To handle the so-called ”missing distance” problem, several approaches have been

proposed. For instance, it is possible to set wij = 0 and do not care about the missing distance

ˆ

dij. Another possibility is to complete the Distance matrix with a rough estimate, i.e., by using

the topology of the network, the number of hops, etc.[SRZF04], or use a modified version of MDS for partially connected matrices [AWL10]. More complex approaches use map stitching techniques. In [SR04, SRZF04] , for example, the main idea is to build a local map at each node of the immediate vicinity and then merge the maps together to form a global map. Other algorithms such as dwMDS [CPHI06] do not face the problem because of their distributed approach.

(30)

The distributed weighted Multidimensional Scaling (dwMDS)

The distributed weighted Multidimensional Scaling (dwMDS) is a modified version of MDS that has the following characteristics: a) it is distributed, i.e., meant to be used for very large wireless sensor networks, b) it handles multiple distance measurements, and c) it considers anchor nodes in the stress function. Given n nodes, m anchors, and K measurements for each distance pair, the global stress function is the following:

min X S(X) = minX 2 n X i=1 n+m X j=1,j<i K X k=1 w_ij(k)( ˆd(k)_ij _{− d}ij(X))2+ n X i=1 kxi− ¯xik2 (2.8)

Then, the stress function is decomposed, and each node computes only a part of it considering its neighbors only. Thanks to its distributed approach, distributed weighted Multidimensional Scaling (dwMDS) is suitable for large wireless sensor networks. However, the drawback results in an increase of the communication between nodes to accomplish the minimization. Moreover, it also increases the time needed to find the minimum of the function making it inefficient for applications that include nodes mobility.

The dynamic Multidimensional Scaling (dMDS)

The dynamic Multidimensional Scaling (dMDS) is another version of MDS that aims at visu-alizing sets of objects where dissimilarities are measured at each of T successive time periods.

Let these dissimilarities be denoted by _{{ ˆ}d(t)_ij , (i, j = 1,_{· · · , n; t = 1, · · · , T )}. The aim is to}

produce a configuration of nT points in a space where each object is represented T times. A super-distance matrix D, is filled with the T sets of dissimilarities/distances, as follow:

D =     D11 D12 · · · D1T .. . ... . .. ... DT 1 DT 2 · · · DT T     (2.9)

where Dtt is the Distance matrix at the tth time instant. The matrix Dtt0, instead, contains the

dissimilarities ˆd(tt_ij0) between an object i at time t and another object j at time t0, with t_{6= t}0.

This cross-time information may be available in some scenarios. However, In other applications such as in localization, this information is not always available. A possibility is then to assume such distances as missing and assign a zero weight to that values. It is worth noting that the super distance matrix has to be symmetric.

Cabero et al. [CSA07] used dMDS for indoor people tracking. Thanks to a large number of anchors, they filled the super distance matrix knowing that the distance between anchors

is constant over the time, i.e, ˆd(tt_ij0) = ˆdij ∀ t = 1, · · · , T . Similarly, Beck and Baxley [BB14]

proposed an anchor-free node tracking technique that uses dMDS and odometry. However, the drawback of this approach is that the computational complexity proportionally grows with the number of nodes and instants.

(31)

2.4. Impact of Non-Line-Of-Sight (NLOS) measurements in indoor Localization

2.4 Impact of Non-Line-Of-Sight (NLOS) measurements in

in-door Localization

In indoor scenarios, RF distance measurements suffer from the presence of obstacles and walls between the transmitting and the receiving node. The radio signal can be either reflected and produce multiple paths or attenuated. Such phenomenon is called multipath effect.

Since RSSI measures the power of a received packet, multiple paths from the transmitter to the receiver may increase the estimated receiver power resulting in a wrong estimate (the receiver think that the transmitter is at a closer distance than in reality). Obstacles such as walls, instead, attenuate the signal strength hence the receiver will believe that the node is further.

As previously described, Time-based techniques rely on the estimation of the time of flight of a packet. A reflected signal will travel more distance than one that is flying in LOS. Moreover, substantial occlusions such as water can alter the flight speed of the packet and at the same time attenuate the signal. The radio transceiver of a node chooses the signal that has the highest receiving power among multiple reflected ones since it is more likely that is the one that flew in LOS. There exist four different scenarios which provoke multi-path signals [Pro13] in Time-based measurements.

Figure 2.8: The figures shows four different cases in wich a transmitter (TX) send a RF signal to a receiver (RX). For each case, the power and the time at wich the signal arrives to the receiver is shown. a) the true signal has higher power than the delayed. b) an occlusion reduces the strength of the LOS signal. c) due to a not-omnidirectional pattern of the antenna the true signal suffers from a reduced power. d) a strong occlusion delay the time of arrival and reduces the strength of the true signal.

(32)

Figure 2.8.A shows the case in which a reflective object produces a second path to the receiver. Since it travels for a longer time, the estimated distance is bigger. However, the LOS signal has a higher peak. In this case, the correct distance is chosen. In Figure 2.8.B an obstacle produces an occlusion to the LOS path leading to an attenuation of the signal strength. In this case, the distance will be over-estimated since the delayed signal has a higher peak. In some cases, such as in Figure 2.8.C where the receiver is partially rotated, the reflected signal has a stronger power than the actual one. In this case, the distance will also be miscomputed. Finally, in Figure 2.8.D, a substantial occlusion may also cause a delay in the straight path causing a completely NLOS scenario in which the correct distance is never experienced.

Despite sophisticated signal processing methods, the resolution of multi-path signals is still a hard problem [SGG08]. As a result, first signal paths may not be detected and overestimated (positively biased) distance measures are returned. Consequently, in order to compute accurate and precise localization estimates, we must take NLOS measurements into account.

Methods that handle NLOS measurements can be classified into two groups: those that detect and discard NLOS measurements, using only LOS measurements [CTSC06, CZ05], and

those that use NLOS measurements in addition to the LOS measurements [CWW+12, VCY04].

The approaches in the second group employ means of identifying which measurements are NLOS, and adapt the computations accordingly, e.g. by weighting or scaling those measurements. Finally, Venkatraman et al. [VCY04] assume knowledge of the geometric layout of certain base station nodes, to infer bounds on the NLOS range errors that are obtained. This can be troublesome when the material properties of the nearby environment have non-negligible effects on the signal propagation.

2.5 Inertial Measurement Unit (IMU) in range-based

localiza-tion

In addition to radio signals, the position of a mobile unit can be estimated by IMU sensors. An IMU is a device usually composed by accelerometers, gyroscopes and, sometimes, a magne-tometer. By an IMU it is possible to measure velocity, orientation, and gravitational forces on a body. IMU are equipped with all new smartphones and are widely used to provide many ap-plications in which the orientation of the phone is needed or for counting the every-day number of steps of a person. They were also the driving factor in the spreading of quadrotors making them much easier to control.

An IMU allows deriving the speed and position of the object in which it is placed on by integrating the acceleration with respect to time. Unfortunately, the acceleration values provided by an IMU suffer a small bias that, together with the integration process, causes drift errors to the position measures. When controlling a quadrotor, an IMU is also associated with other sensors (GPS outdoor, or optical flow smart cameras) that, thanks to an accurate sensor fusion, can block its drift.

Recent works proposed hybrid methods that combine different types of data, e.g RSSI and IMU data, to improve the accuracy of position measures. The main techniques used for data

(33)

2.6. Ambiguities in relative-localization al. [MKW13] considered the localization problem of indoor mobile robots. They proposed a localization method based on the fusion of RSSI data, coming from WiFi access points, and data coming from onboard IMU sensors. The sensor data fusion is obtained by an Extended Kalman Filter (EKF). Schmid et al. [SGSMG11] presented an experimental study on the pedestrian localization problem, which analyzes the improvements that can be achieved by fusing inertial data and RSSI data. This work compared the accuracy of a RSSI-only localization approach with respect to the RSSI and IMU data fusion approach. The authors concluded that the improvements obtained by fusing IMU and RSSI information reduces the positioning error to a certain amount, but the resulting accuracy is not significantly improved. However, they also concluded that the achievable localization accuracies suffices for the person localization scenarios considered in the experiments. Woodman and Harle [WH08] described a tracking system for pedestrian localization inside buildings. The proposed system uses a model of the building, a foot mounted IMU and a particle filter to deal with the typical drift problems of inertial sensors. The initial position of the tracked person is obtained by exploiting RSSI data obtained from a set of WiFi access points. The system is able to track the position of people in buildings with multiple floors and stairs. The experimental results showed that, by using an ultrasonic localization system as ground truth, the resulting position accuracy is 0.5 meters for 75% of the time, and 0.73 meters for 95% of the time. Fink et al. [FBVS10] presented a localization system based on sensor fusion of RSSI data and positioning data obtained by an Inertial Navigation System (INS) composed by two accelerometers and one gyroscopic sensor. The precision of distance measures obtained by RSSI data was increased by adopting a diversity scheme based on antenna and frequency diversity and a Kalman Filter (KF) to estimate and correct the drift errors of the INS. The proposed system has been evaluated in a testbed composed by eight anchor nodes, called reference nodes, evenly distributed in an overground longwall mining. The node to be tracked is carried by a person that moves linearly among the reference nodes. The experiments highlighted that the localization system shows an average estimation error of 1.68 metres. Li et al. [LIW13] presented a method to track mobile nodes that fuses WiFi RSSI data and inertial data from a smartphone. The proposed solution is composed by a Sequential Monte Carlo Kalman Filter (SMC-KF), which elaborates the navigation data coming from the smartphone IMU, and a Steepest Descent Random Start (SDRS) algorithm that elaborates the RSSI data. The performance of the proposed approach has been assessed by simulation experiments an compared with solutions based on IMU data elaborated by an EKF, and solutions based on UWB radio-location devices.

2.6 Ambiguities in relative-localization

In absolute localization, anchors are used to provide a reference system to all the unknown nodes. The coordinates of a set of nodes can be called a ”frame” or sometimes ”map”. A frame is global if there are anchors that provide a reference system. In this case, given the pairwise distances between all the nodes, there exists only a unique realization. A Relative frame, instead, has a unique solution up to some degrees of freedom (i.e., rotations, translations, and reflections). When comparing a relative frame with a global frame or another relative frame, the problem of