Indoor position estimation constitutes a central task in home-based assisted living environments. Such environments often rely on a heterogeneous collection of low-cost sensors whose diversity and lack of precision has to be compensated by advanced techniques for localization and tracking. Although there are well established quantitative methods in robotics and neighboring elds for addressing these problems, they lack advanced knowledge representation and reasoning capacities. Such capabilities are not only useful in dealing with heterogeneous and lacking information but moreover they allow for a better inclusion of semantic information and more general homecare and patient-related knowledge. We address this problem and investigate how state-of-theart localization and tracking methods can be combined with answer set programming, as a popular knowledge representation and reasoning formalism. We report upon a case-study and provide a rst experimental evaluation of knowledge-based position estimation.
The continuous progress of computing and communication technology is leading towards the realization of living environments pervaded by a high number of invisible devices a ecting and improving all aspects of our lives. A crucial issue in these scenarios is to know the physical location of users, since it represents the basis for context-aware and user-centered systems. The problem of indoor position estimation includes two aspects: localization and tracking.
Localization (also referred to as position estimation) is commonly addressed by acquiring the distance from three or more points of known positions and then applying trilateration. The distance can be computed by measuring variations of signal intensity or by timing the latency from transmission to reception. The precision of positioning systems varies from a few meters in 2D to a few decimeters in 3D. Given the low cost of infrastructure and their exibility, localization system based on Wireless Sensor Networks (WSN) are a good starting point for tackling the localization problem in home environments. However, when data are noisy and incomplete due to delays, breakdowns, errors in transmission, and alike, their lack of precision in position estimation needs to be supported and compensated.
Tracking is more concerned with how the position of moving objects changes in time; it takes into account knowledge about previous positions and a model of movement to estimate the expected (more plausible) position.
Di erent estimation methods can be used to tackle the problem of node
localization, such as Maximum Likelihood, Maximum A Posteriori, Least
Squares, Moving Average lter, Kalman lter, and Particle lter [
Particle Filters discretize the probability distribution function of the position of the mobile object instead of controlling the whole position space. Unlike Kalman Filters, they do not approximate the probabilities using only gaussian distributions, thus we have to impose less conditions to be able to apply the algorithm. The possible positions of the mobile object are represented as a set of particles, each of which has an associated weight. The distribution of these particles in space gives the most likely positions. Probabilistic approaches to tracking such as PF strongly depend on the speci c sensors used and they are mainly based on quantitative cost functions for computing weights. One of the main limitations of these methods is the difculty to identify within the same model the right global cost function combining heterogeneous sensor data with other criteria like movement, speed, and alike. Another aspect is that the introduction of new sensor information is not straightforward and requires a lot of customization to properly extend the model.
In order to address these limitations, we propose an alternative and innovative approach to support indoor localization and tracking. Our solution is based on Answer Set Programming (ASP), a declarative logic programming framework, combining a compact, exible, and expressive modeling language with high computational performance. The knowledge representation and reasoning capacities of ASP provide us with the following advantages: a knowledge-based level of multi-sensor fusion for position estimation, de nition of qualitative criteria to combine sensor data and commonsense knowledge for tracking, and easy customization and extensibility of existing solutions in a more exible way whenever new technology or new sensor-data becomes available. The main advantage of using ASP is to deal with incomplete information, stemming from faulty or diverging sensors, and thus to improve the scalability of the whole system. ASP does not only deal with missing sensor data but moreover it allows us to exploit semantic information for distinguishing the most plausible among varied sensor data.
Our approach is based on a low-cost and energy-aware localization infrastructure. The data collected by each speci c type of sensor is processed by traditional algorithms for feature extraction and aggregation.
For validating our approach we collected a considerable amount of sensor data by appeal to a simulation tool generating large sets of sensor data re ecting entire days of a person's household activities, matching real sensors installed in our lab. On top of the aggregation phase, a further level of knowledge-based sensor fusion is in charge of combining heterogeneous sensor data to associate it to speci c properties or semantic information. The ASP based reasoning process follows the common generate and test methodology in (i) generating the space of possible positions according to semantic data aggregation criteria and (ii) exploring the search space by applying e cient solving techniques to compensate for the lack of information and to enforce constraint satisfaction and optimization.
The simulation environment and properties of generated data are described in Section 2. Section 3 introduces the ASP formalism and investigates our modeling and reasoning strategies, while preliminary results are presented in Section 4. A short discussion follows in Section 5. 2
To position an object or a device, the basic step is to use a reference point to determine the distance and angle between the device and the reference point itself. To do so we use the Receiver Signal Strength Indicator (RSSI), based on the degradation of radio signal while traveling in a space.
In addition to RSSI, we use Passive Infrared (PIR) and Range Finders (RF). PIR is used to catch the movements of a person (or object) that has a di erent temperature with respect to the surroundings while RF uses sonar to provide the distance of an object from the sensor.
In order to generate RSSI, RF, PIR, and environmental sensor data, we implemented an agent-based data-generation tool using the Recursive Porous Agent Simulation Toolkit (Repast Simphony or Repast)1.
Following a taxonomy of selected Agent-Based Modeling Tools
illustrated in [
The simulation scenario is represented by a Repast model that describes three grid-based projections and one network-based projection. The three N M grid projections are used to de ne (i) the oor plan (walls, rooms and areas), (ii) the position of localization sensors and (iii) the position of environmental sensors together with the way they propagate to adjacent cells. The network-based projection de nes two undirected weighted graphs having FloorCell agents as nodes. The rst graph is mainly used for the movement of the Person agent computed using Dijkstra's shortest path algorithm where weights are also used to avoid movements across wall cells.
The second grid projection is mainly used during the RSSI-data generation to verify if a direct line-of-sight between the person and the localization sensors exists. This information is useful in order to better simulate the RSSI propagation model. For this, the weights of graph in the second grid projection are computed without considering walls. The line-of-sight information is computed comparing the results of the shortest path algorithm obtained using the two graphs. These results di er only if there is a wall between the localization sensor and the person.
The simulation scenario is speci ed in an XML-based scenario-de nition
le2. This scenario le is used to dynamically populate projections during
the initialization phase of the Repast simulator, and it de nes the following
aspects of the simulation context:
environment: according to what speci ed in this le, a FloorCell agent
can be a wall, part of a room-area or a passage (a cell connecting two
areas of di erent rooms); the division of the environment into rooms
and areas is speci ed so that an area can be associated to one room
and a room can contain di erent (disjoint3) areas;
localization sensors: in addition to the sensor position on the grid and its
orientation, the de nition speci es the behavior of the passive-infrared
and movement sensors in terms of cells covered;
environmental sensors: during the data-generation phase, these sensors
can read the temperature, humidity and brightness values;
light and heat sources: these elements de ne the properties of the
objects that are used to manage and propagate the state of light and
heat throughout the simulation scenario using a controlled ooding
algorithm [
2Note that Repast can load the required initialization data in several ways (e.g. using agent de nitions directly stored in a relational database or in text les). 3The spatial inclusion of areas A1; : : : ; An in a room R is such that Sin=1 Ai R.
In addition, we provide an XML le containing a detailed list of actions we want the agent Person to perform. The actual version of the simulation tool include three types of elementary actions: going to a speci c position in the grid, changing the state of lights and opening/closing doors and windows.
The data-generation is driven by two di erent event schedulers that are used to: (i) simulate the behaviour of the person and generate according RSSI, PIR, and RF sensor data, (ii) simulate light, temperature, and humidity evolution during the day.
During every simulation tick, the LocalizationSensor agents compute the RSSI, PIR, and RF considering the position of the agent Person in the oor plan. The measurement computation takes into account the model of every sensor: the radio propagation model for RSSI values and the presence of the person in a cell covered by the sensor for PIR and RF. EnvironmentalSensor agents generate temperature, humidity and light measurements periodically examining the state of the associated EnvironmentCell agent. All measurements are stored in a relational database.
The DayManager and HeatManager agents are used to manage the evolution of daylight and external temperature and humidity during the datageneration. Using the schedule we mentioned before, they modify the state of LightSources and HeatSources objects, which in turn modify the state of the associated LightCells and HeatCells objects.
Figure 1 shows the Repast toolkit executing di erent projection displays: the left side shows the main projection, walls (squares) and the person (dot); the right side gives the projection of sensor data, showing the light sources (circles), environmental sensors (crosses) and oor cells (squares). 3
All RSSI values produced in the simulation process are further processed using PF algorithms and they represent a starting point for the subsequent reasoning phase. Other (homogeneous) sensor values are aggregated with ad-hoc algorithms for features analysis and used to support position estimation. The knowledge-based support to localization and tracking tackles the problem that data gathered by sensors may be noisy even after aggregation, but their combination may yield a more reliable interpretation. The expressive power of ASP is used to disambiguate unclear situations (e.g., where the person is) by combining heterogeneous data sources and using defaults and qualitative optimization to select the best candidates.
To do this, the simulation scenario and the generated data are rst parsed in form of logic predicates and qualitative criteria are speci ed and combined to reason about localization and tracking. 3.1
We assume the reader to be familiar with the terminology and basic de
nitions of ASP (see [
The logical description of the localization scenario is provided in terms of interesting properties of the sensed information. The space is a grid where each cell (or location) is identi ed by coordinates X, Y . Each cell has some static properties that are mapped into a set of logic predicates as detailed in Table 1.
Locations are also associated to dynamic sensor information, according to available sensor data at each time step T . Such information can be derived by (i) processed RSSI values with associated percentage of likelihood P and (ii) PIR or RF signals. Logic predicates representing dynamic sensor data are listed in Table 2.
The available signals are treated di erently in the de nition of optimization criteria: processed RSSI signals are used as a starting point, that is, whenever a set of candidate positions is provided by the PF algorithm based on RSSI, PIR and RF are used to validate the most plausible position(s). Predicate Description cell(X,Y,Room,Area) association of a cell to an area of a room passage(X,Y,R1,A1,R2,A2) association of a cell to a passage wall(X,Y) description of a cell as part of a wall loc(X,Y) a location L is described by two coordinates invalid(loc(X,Y)) speci cation of invalid cells dataExpected(pir,loc(X,Y)) locations covered by PIR sensors dataExpected(rf,loc(X,Y)) locations covered by RF sensors Predicate Description sensed(rssi,P,L,T) processed RSSI signal with likelihood P received at time T for location L sensed(pir,L,T) PIR signal received at time T for location L sensed(rf,L,T) RF signal received at time T for location L
At any time step, a location becomes a candidate position when a processed RSSI, PIR or RF signal has been received for that location and the location is valid (e.g. it is not a wall). This allows us to immediately reduce the space of solutions to the positions for which at least one signal is available. The corresponding ASP code is as follows: location(L,T) :- sensed(rssi,P,L,T). location(L,T) :- sensed(S,L,T). location(L) :- location(L,T), not invalid(L).
Besides the information about received sensor data at a given time step T for a location L, we also describe two additional dynamic properties for a localization and tracking problem: the distance measure between two consequent admissible moves and the support for a location as a candidate position at a give time step.
Distance between two locations l1 = loc(x1; y1) and l2 = loc(x2; x2) is represented by the propositional variable dist(l1; l2; d) that is true for where d = jx1 x2j + jy1 y2j Support for a location L is the number of sensor data collected at location L at a given time T and it is represented by predicate support(L; N; T ) where
N = jfsensed(S; L; T )gj where S 2 dataExpected(S; L)
Discrete time is in seconds and sensor data are opportunely aggregated and provided when values change beyond a given threshold.
Earlier in this section we mentioned that ltered candidate positions obtained by PF by processing RSSI signals represent starting points to estimate the actual position. Our reasoning process is exible enough to deal with noisy and even missing sensor values. Since we reduce the set of possible solutions to the ones for which results of PF are availabe, when this information is missing tracking the person on the grid becomes more di cult and the solution space can be huge, since the model of movement may produce a higher number of possibilities. This happens not only in case of malfunctioning sensors, but also when the PF cannot provide acceptable candidate positions for several sequential time steps. In this case, the qualitative analysis of the available information can still help, as detailed in the next subsection. 3.3
The interpretation of heterogeneous sensor data used to support localization and tracking is based on the de nition of properties of sensed information that can be meaningful according to available sensor data. In our solution, we identi ed three properties which combination can originate several optimization criteria.
Best PF property considers positions with the highest likelihood P , that are provided as a result of the PF algorithm; unfortunately it is not always true that the higher the likelihood obtained by the PF, the closer the candidate position is to the real one; for this reason we dene additional criteria to validate positions; when results of PF are not available, a di erent reward function is used, which is closely related to the notion of support for a location L de ned in the previous subsection: the higher the support for L, the better L is as a candidate position.
Best Coherence maximizes the value of the coherence property, which identi es a percentage indicating how many of the sensor signals expected from a given location L are e ectively captured for that location at time T ; this property is represented by predicate coherence(L; C; T ); if no additional sensor signals (excluded results of Particle Filter) are expected for a location L, its coherence C will always be 100% for all time step; in the same way, C is 0 at time T if we expect at least one additional sensor value for a location L and we do not have any of them; otherwise, we have that, for a location L, where M = jfdataExpected(S; Lgj and N is the support.
C = (100
M )=N Best Move property identi es the best location at any time step T as the location L for which the distance between L and the location at time step T 1 is minimum; the associated property is represented by predicate bestM ove(L; T ).
When new sensor information is introduced, we can easily re-de ne or extend the list of properties. An example can be the introduction of environmental data in the de nition of coherence: to take such data into account, we just have to introduce it in the notion of support.
Once we have the list of properties, they can be combined into optimization criteria. The preference relation between two criteria is de ned by their numbering such as Ci is preferred to Cj (Ci >pref Cj ) when i > j.
In our prototype, we identi ed four criteria Ci; i = 1::4, combining properties on sensor information as follows:
C1 is satis ed for a location L at time T when L satis es both the best move and the best coherence property; C2 is satis ed for a location L at time T when L veri es the best coherence property; C3 is satis ed for a location L at time T when L veri es the best move property; C4 is satis ed for a location L at time T when at least one of the predicates in Table 2 is true on L at time T , and L has the highest likelyhood or the highest support; this is the weakest criterion and it is applied only when no better solution can be found by applying the other criteria.
This ordering is motivated by the fact that we want to obtain the solution satisfying all criteria as the best option, but if it does not exist, we prefer to give up the movement model and consider coherence as more reliable4. Alternative combinations are also possible and this can be useful to compare them in order to understand which property seems to be stronger or which sensor data appears to be more reliable.
In order to implement optimization on ordered criteria, we introduce the concept of best value B for a criterion Ci at time T , BCi (T ). The best value is determined in two di erent ways according to the fact that (a) we have L as a candidate position at time T as a result of Particle Filter or (b) no candidate position is produced by Particle Filter at time T but we have other sensed data supporting a location L as a candidate position. The de nition is as follows: a) BCi (T ) = maxfP : sensed(rssi; P; L; T ); 9= BCj (T ) with Cj < Cig 4Note that this is one of the possible choices. We can change the ordering between criteria to see how reliable our sensors are.
The best location L represented by predicate best location(L; T ) can
now be identi ed by selecting the best value returned by the application of
the most preferred criterion. The actual implementation of this optimization
technique is evaluated using the Clasp solver [
Our speci cation of the problem needs a way to generate the space of solutions and then select the best one via optimization. This is done by applying the generate and test approach: a cardinality constraint speci es that for each time step T , exactly one location is selected (generating phase) and an integrity constraint speci es that a selected location L for a time step T has to be the best location for T (testing phase) as follows: 1 { at(L,T) : location(L) } 1 :- time(T). :- at(L,T), not best_location(L,T). 4
In this section, we provide a rst experimental evaluation of our knowledgebased approach to position estimation.
Our experiments are based on the generation of several test instances of di erent size. Each instance has been generated using the agent-based simulation toolkit Repast Simphony. According to the size of the instance we want to generate, we simulate movements of a person across one or more rooms of the house through one or more midpoints. Repast applies a simple shortest-path algorithm for simulation, based on the map of the environment and realistic motion model. The instance size is determined by the number of time steps which corresponds to the number of moves, given that each move is associated to a new time step. In our analysis, we make the assumption that the number of sensors (thus the amount of sensor data received at each time step) is xed according to a given sampling rate, and it is linear in the number of rooms and doors in the environment (we consider putting four to six sensors per room plus one sensor for each passage). For this reason, we did not consider the amount of data produced by sensors at each time step as a factor that may impact performance.
We focus our attention on the following aspects of our approach: the overall accuracy of results (Mean Absolute Error); the fault tolerance expressed as the impact of missing data on the accuracy; the e ectiveness of optimization criteria in ltering results.
We determine the overall accuracy of our results via the Mean Absolute
Error (MAE), proposed in [
Pin=1 p(xi xi)2 + (yi
yi)2 n where (xi; yi) are the coordinates of the target's estimated positions and (xi; yi) the true ground ones. Note that in our simulation environment, the dimension of each cell is 20cm, which means that an MAE of 5 indicates an average error of one meter which is fully acceptable.
We compare the MAE indexes obtained through Particle Filters (PF) based on the RSSI signals only, with the MAE index obtained by ASP combining results of PF based on RSSI signals with Range Finder (RF) and Passive Infrared (PIR) measurements.
If we observe the rst row of each instance (with no missing data), we see that the introduction of additional (noisy) sensor data gives us an MAE that is slightly higher with the ASP-enhanced approach or very close (as in the last instance). The only real exception is the MAE of the smallest instance of size 30. This can be explained by the fact that the PF algorithm re-allocates the particles used for position estimation at each time step; as a consequence, it is common that on small instances the particles are still a bit sparse and the precision of the algorithm is lower.
For a similar reason, MAE index slightly decreases as size rises: on bigger instances, particles tends to converge on the more plausible positions, resulting in higher accuracy. This increased accuracy propagates on ASP results, since the ASP approach itself uses PF results as a starting point, and it is not furher a ected by the size of the instance in terms of MAE.
Another aspect we took into account is how the accuracy can be a ected by missing data. A lack of data can either be caused by sensors not properly transmitting or by a too sparse set of particles, so that the PF algorithm cannot provide candidate positions. Considering missing data scenarios is interesting in view of the fact that we want our approach to be robust and able to provide candidate solutions even in case of malfunctioning sensors or weak PF results.
The second column in Table 3 indicates the amount of sensor data we removed from the input given to ASP. We observe that in general we obtain lower MAE values by removing data, probably due to the fact that our knowledge-based approach makes it possible to estimate a position by using the model of movement or additional domain-related knowledge to reduce the search space and propose plausible estimations even when the PF algorithm is not able to provide some. Another consideration is that removing data could also remove noise, thus giving better global results.
If we consider the last instance in Table 3, we notice that removing 5% of PF data gives us an initial reduction of MAE, which then increases when we get to removing 15% of PF data. In further analysis it would be interesting to estimate a threshold telling us how far we can go in removing data before MAE starts to increase. Intuitively, it depends on how many di erent kinds of sensor signals we have, and how noisy are the data they produce: the higher the number of sensors or the noise, the higher the threshold, while if we have lots of reliable sensor data, we would expect this threshold to be lower.
Although we need more tests to validate our intuitions, the main idea is that if we have a higher number of sensors, missing data can be better compensated by the knowledge-based approach, as long as the noisiness of data does not grow signi cantly with the number of sensors. Time steps with no data do not determine a redistribution of the particles as in the PF algorithm: in our approach, the position in a time step for which no data have been collected, are guessed according to the knowledge-based optimization criteria applied to tracking in previous and following time steps. Preliminary tests show that this approach makes accuracy robust against incomplete information, but we need more accurate tests to support this statement. One may argue that if data are not available for several time steps, the combinatorial explosion of possible solutions can make the search process ine cient. Even in this case, optimization criteria can help selecting the best candidate positions in the search space.
The e ectiveness of our approach can be validated by observing that changing the order of criteria could help evaluating the reliability of sensor data or the soundness of the properties we de ned according to commonsense knowledge. As an example, we found out that values provided by PIR and RF sensors are very reliable, thus if we switch criteria C2 and C3 giving higher preference to the movement model than the coherence property, the MAE increases.
In addition, our approach makes it easier to add new domain-knowledge in form of constraints or optimization measures, which can be used to strengthen the choice of some candidate positions over others going beyond what sensor data tells us.
A more general, though very important issue, is the trade-o between exibility and accuracy of the model. In order to investigate this aspect, we should make further experiments on how additional sensor data as well as new criteria or di erent optimizations may a ect accuracy. 5
We presented a hybrid approach to indoor position estimation by combining and extending quasi-standard quantitative methods in a knowledge-based yet qualitative framework. To this end, we took advantage of the knowledge representation and reasoning capacities of ASP for providing a rich model combining various disconnected sensor models with further semantic information, like a movement model and sensor dependencies. The resulting ASP encoding combines the available heterogeneous sensor data in a transparent and easily modi able way and o ers an impressive robustness in dealing with noisy and (partially) absent sensor data, as indicated by our preliminary experiments. Although we have not discussed the encoding in detail, it allows for easy customization and extensibility. All in all, the elaboration tolerance of the high-level ASP speci cation makes the major di erence of our approach to potential alternatives, and it seems hard to envisage in a purely quantitative settings.
This preliminary work is only a starting point. Future work will have
to address more extensive and systematic experiments in various simulated
as well as real scenarios. More sensor and semantic information needs to be
taken into account in order to evaluate the true scalability of our approach.
Finally, our current implementation accumulates data in hourly intervals.
We plan to re ne this to use the incremental ASP solver iClingo [