Mickael Danancher
email: danancher@lurpa.ens-cachan.fr.

Member, IEEE Jean-Jacques Lesage
email: lesage@lurpa.ens-cachan.fr.

Lothar Litz
email: litz@eit.uni-kl.de.

J.-J Lesage

Model-Based Location Tracking of an a priori Unknown Number of Inhabitants in Smart Homes

Keywords: Discrete Event Systems, Finite Automata, Smart Home, Location Tracking

In this paper we propose an approach for online model-based location tracking of inhabitants in Smart Homes. Based on our previous solution for a fixed and predefined number of inhabitants using finite automata we generalize the approach to handle an a priori unknown number of inhabitants. The online-algorithms to detect the number of inhabitants and to track their location are given and a comprehensive evaluation method is defined. It consists of an analytical and a simulation-based procedure as well and is able to predict the tracking performance for real Smart Homes by a normalized measure. Throughout the paper, previous and new results are illustrated by a realistic case study and illustrative scenarios are given.

Note to Practitioners-Tracking the location of several inhabitants in a Smart Home using only ambient, non-invasive, low-cost sensors is a challenge. In this paper, we propose specific evaluation approaches as well as an expert-in-the-loop improvement procedure to help the expert setting up a satisfying instrumentation using only such sensors. We also detail the algorithm for online Location Tracking of any inhabitants in a Smart Home and explain this algorithm with an illustrative scenario.

I. INTRODUCTION

S MART Home technologies are aiming to help people to live in a comfortable and safe environment. A Smart Home can be defined as a home equipped with sensors, actuators and communication devices; based on the information given by the sensors, the actuators can be controlled in order to improve comfort (heating or air conditioning for instance) or to guarantee the safety of the inhabitants (automatic shutdown of dangerous devices or health problem detection for instance) [START_REF] Robles | Applications, Systems and Methods in Smart Home Technology: A Review[END_REF].

Indoor Location Tracking (LT) of the inhabitants is often required for these approaches (comfort, safety and health). For instance, it has been proved that some approaches aiming at the recognition of Activities of Daily Living (ADL) show better performances when exploiting the result of a LT algorithm [START_REF] Chen | Does Location Help Daily Activity Recognition[END_REF]- [START_REF] Liao | Location-Based Activity Recognition using Relational Markov Networks[END_REF]. Health problem detection by monitoring the inactivity of the inhabitants also performs better when tracking online the location of the inhabitants and monitoring their inactivity level in each zone of the house [START_REF] Poujaud | Identification of inactivity behavior in Smart Home[END_REF], [START_REF] Floeck | Activity Monitoring and Automatic Alarm Generation in AAL-enabled Homes[END_REF].

LT consists in finding in real time the location of one or several inhabitants, based on the observation of the signals generated by different sensors of the house [START_REF] Rahal | Location Estimation in a Smart Home: System Implementation and Evaluation Using Experimental Data[END_REF]. In most approaches, LT is performed by using data mining techniques [START_REF] Rahal | Location Estimation in a Smart Home: System Implementation and Evaluation Using Experimental Data[END_REF]- [START_REF] Liau | Inhabitants Tracking System in a Cluttered Home Environment Via Floor Load Sensors[END_REF]. Consequently, a more or less long learning phase is required before the LT becomes operational. Furthermore, this phase has to be performed again as soon as the instrumentation is modified (i.e. if new sensors are added or if existing sensors are removed or if their placement is modified). Last but not least, such learning techniques lead to the lack of a formal and explicit model of the location, what does not facilitate the use of this information.

For these reasons, we proposed in previous work [START_REF] Danancher | A Discrete Event Approach for Model-Based Location Tracking of Inhabitants in Smart Homes[END_REF] an approach aiming at the systematic construction of a Finite Automaton describing the detectable motion of a single inhabitant [START_REF] Danancher | Online Location Tracking of a Single Inhabitant based on a State Estimator[END_REF] or of a fixed and predefined number N of inhabitants [START_REF]A Discrete Event Model for Multiple Inhabitants Location Tracking[END_REF]. Based on these models, we also defined algorithms for LT [START_REF] Danancher | Online Location Tracking of a Single Inhabitant based on a State Estimator[END_REF], [START_REF]A Discrete Event Model for Multiple Inhabitants Location Tracking[END_REF] and we developed two procedures (one analytical approach [START_REF] Danancher | Online Location Tracking of a Single Inhabitant based on a State Estimator[END_REF] and one simulation-based method [START_REF] Danancher | A DES Simulator for Location Tracking of Inhabitants in Smart Home[END_REF]) to evaluate the relevance of an instrumentation and of the designed model for the LT purpose.

Based on these previous results, we propose in this paper a new algorithm for online LT of an a priori unknown number of inhabitants based on the online estimation of the number of inhabitants. New criteria for the performance evaluation are also defined and a procedure to simultaneously build and evaluate the Finite Automata required for a priori unknown number of inhabitants' LT is given. Moreover, a global approach for evaluation-aided improvement of an instrumentation is proposed. This improvement loop relies on the expert knowledge and therefore is not an automatic optimization approach. Moreover, the inhabitant is deliberately put outside the improvement loop, in order for our approach to be more general. These new results are applied and illustrated using an example of Smart Home. The complexity of the models and of the LT algorithm is also discussed. The whole procedure we are proposing in this paper is summarized in Fig. 1. In a first step, the expert splits the considered home into zones and defines the sensors he wants to install in this home. Then, he automatically get a model of the detectable motion of 1 or N inhabitants. Those model are then used to evaluate the ability of the smart home to perform LT. Finally, if the result is satisfying, it is possible to setup the LT in the smart home. On the contrary, if the results are unsatisfying, the expert gets a feedback on the issues to solve and can define a new zone partition or instrumentation.

It as to be noted that in this work we are interested in applications that only require the knowledge of the location of the inhabitants in the dwelling but not their identity. For example, for reducing energy consumption by optimizing the temperature regulation and the lighting management, it is only necessary to know if somebody is present (and eventually the number of inhabitants which are present) in the different zones of a smart home but not who they are. For applications which require to know the identity of the inhabitants additionally to their location, it would be necessary to use additional sensors like wearable sensors that directly give the identity of inhabitants, or to couple our approach with data association techniques [START_REF] Meissner | Multipath-Assisted Single-Anchor Indoor Localization in an Office Environment[END_REF], [START_REF] Chen | Multitarget-Multisensor Data Association Using the Tree-Reweighted Max-Product Algorithm[END_REF]. The paper is organized as follow. In the next section, some assumptions on instrumentation of Smart Homes and inhabitants' behavior as well as the problem statement are detailed. The case study is also described and the previously published results are briefly recalled by being applied to this case study. In the third section, the new algorithm for LT of an a priori unknown number of inhabitants and an illustrative scenario are presented. In the fourth section, two procedures (analytical and simulation-based) for performance evaluation are presented and an improvement loop involving the expert is proposed. The evaluation and improvement results are illustrated on the case study.

II. PROBLEM STATEMENT, CASE STUDY AND PREVIOUS

RESULTS

A. Problem statement

Reviewing the existing smart home approaches reveals the very different specifications underlying these approaches. In our context the following assumptions concerning the inhabitants expectations and behavior as well as the kind and the behavior of the sensors are made.

To reach a high degree of inhabitants' acceptance only nonintrusive ambient sensors are considered, i.e. motion detectors, but no wearable sensors nor cameras. This also meets a financial constraint because these sensors are mostly low-cost sensors. These three considerations (non-intrusive, ambient and low cost) advise to consider only binary sensors or sensors delivering a signal that can be interpreted as being binary with slight preprocessing, e.g. using thresholds. It is also supposed that all the sensors function in a fault-free manner.

Furthermore, it is also considered that information given by the sensors does not depend on the ability or the willingness of the inhabitant to provide this information. For instance, if a door is equipped with a door barrier sensor and a door contact sensor, the inhabitant crossing the door will systematically be detected by the barrier sensor but will be detected by the contact sensor only if the inhabitant opens or closes the door in addition to crossing it. Consequently, in our approach, door contact sensors will not be used. For similar reasons, switch sensors are also not considered because while entering a room the inhabitant may or not switch the light on, depending on the sun light or his life habits.

On the other hand, there can be a lack of instrumentation (too small number of sensors or misplaced sensors). This leads to the assumption of a partial observation of the inhabitants' behavior.

It is also assumed that each inhabitant has a totally free behavior which is arbitrary and potentially irrational. Moreover, each inhabitant is assumed to behave independently from the others. Consequently, the inhabitants in an instrumented Smart Home are considered as being spontaneous event generators. The observed events are the rising edges and falling edges of the sensors. The rising edge of a sensor s is denoted s 1, its falling edge is denoted s 0. Moreover, the inhabitants are assumed to be non-distinguishable by the sensors i.e. whatever the inhabitant or the inhabitants being observed by a sensor, the sensor event will be the same.

In addition, it is considered that no model of this free behavior of the inhabitants is available. The aim of this approach is not to propose a model of the human behavior because it is assumed to be overly depending on particular inhabitants. The aim is thus to propose an approach being usable whoever the inhabitants are and whatever their behavior.

It is assumed that the number of inhabitants inside the house can vary at each time (inhabitants or visitors coming in or going out). Furthermore, it is assumed that a maximal number of inhabitants in the Smart Home cannot be given a priori.

Finally, since the aim of LT is to provide the location of the inhabitants, zones of interest have to be defined. More precisely, the environment (the Smart Home and its outside) should be covered by non-overlapping zones. It is believed that this zone partition should be done by an expert familiar with the final application like location-based inactivity monitoring, ADL recognition, automatic shutdown of dangerous devices and so on. More important, the zone partition is not depending on the instrumentation, it should be done without considering the instrumentation or the different rooms but only the needs of the expected application. For instance, for health problem detection, we may consider that the bathroom is divided in two zones, the shower and the rest of the bathroom, the shower being a critical zone for potential falls of the inhabitant. Note that in a general case, one room in not equal to one zone. Moreover, one zone is not equal to one sensor, there may be more than one sensor in each zone and one sensor may observe several zones, since the zone partition is chosen independently from the instrumentation but adequately for a given application.

Based on these considerations, the problem of online modelbased LT can be reformulated in terms of a Discrete Event System (DES) problem: how to estimate in real time the current location of an unknown number of inhabitants, considered as spontaneous event generators, based on a sequence of partially observed sensor events?

B. Case study

Throughout this paper, the proposed results will be applied to a case study shown in Fig. 2. The considered house has two bedrooms, a bathroom, toilets, a shower and an open-space composed of the kitchen, living room and dining room. Considering this house, we suppose that an expert decided to split the environment into 8 non-overlapping zones as shown in Fig. 3 (a). Each bedroom (Z 1 and Z 3 ), the bathroom (Z 4 ), the shower (Z 5 ), the toilets (Z 6 ), the corridor (Z 2 ) are each represented by one zone. In addition, zone Z 7 represents the open-space and zone Z 8 represents outside of the home. Such a zone partition is well adapted for location-based inactivity monitoring (as in [START_REF] Floeck | Activity Monitoring and Automatic Alarm Generation in AAL-enabled Homes[END_REF] for health problem detection).

This home is instrumented with some sensors as shown in Fig. 3 (b). There are 5 Motion Detectors (one in each bedroom, one in the bathroom, one in the corridor and one in the open-space) and 2 Door Barrier Sensors (one on the door between the first bedroom and the corridor and one on the door between the toilets and the corridor). Note that other types of sensors can be integrated, for instance floor pressure sensors, bed sensors, etc... even if we do not consider such sensors for this case study. C. Brief recall of the previous results

In previous work [START_REF] Danancher | Online Location Tracking of a Single Inhabitant based on a State Estimator[END_REF], we proposed an approach to systematically build a model for LT of a single inhabitant in a Smart Home. This approach is briefly recalled and illustrated on the case study.

The home is divided into eight zones, the topology of this zone partition (i.e. the direct paths between zones) and the description of the zones observed by each sensor are used to systematically generate a Finite Automaton model representing the detectable motion of a single inhabitant. The definition of this model is given below. This DM A is defined as DM A = (Q, Σ, δ, Q 0 ) with:

• Q a set of states (one state for each zone of the house),

• Σ an alphabet of events (the rising and falling edges generated by the sensors),

• δ : Q × Σ → 2 Q the transition function, • Q 0 ⊆ Q the set of initial states.
Such a DM A can be manually built by an expert or systematically obtained using one of the algorithms proposed in [START_REF] Danancher | A Discrete Event Approach for Model-Based Location Tracking of Inhabitants in Smart Homes[END_REF]. A possible DM A for the case study is represented in Fig. 4. A strong semantics is associated to the states of this automaton since each state represents the possible location of the inhabitant in a zone of the house. Transitions and associated events represent observable motion between two zones or within a zone in case of a self-loop. For instance on Fig. 4, there are three transitions from state Z 2 to state Z 1 , one labeled with the event DB2 0, one labeled with the event DB2 1 and the last one labeled with the event M D1 1. Each one of these transitions represents one way to observe the change of location from zone Z 2 to zone Z 1 .

Note that, as explained in [START_REF] Danancher | Online Location Tracking of a Single Inhabitant based on a State Estimator[END_REF], falling edges of motion detectors are not representative of a change of location because it can just be symptomatic of someone staying motionless in a zone. Consequently, only rising edges are considered in the models we propose.

It is assumed that the initial location of the inhabitant is unknown. This can be seen in the model where each state is initial. Knowing accurately the initial location is not necessary to perform online LT because the current estimation of the location of the inhabitant does not strongly depends on his initial location. If for some smart home applications it is mandatory to know the initial location of the inhabitant, some techniques (for instance in [START_REF] Shu | I-Detectability of Discrete-Event Systems[END_REF]) can be used to determine the initial state of an automaton after observing a more or less long sequence of observed events. Some sensors are observing more than one zone. This can be seen in the model: DM A is a non-deterministic Finite Automaton (e.g. two transitions labeled with the same event DB2 1, having Z 1 as source state, one reaching state Z 2 and one reaching Z 1 ).

Based on this DM A for a single inhabitant, we proposed in [START_REF]A Discrete Event Model for Multiple Inhabitants Location Tracking[END_REF] an approach to create a model of the detectable motion of a given number N of inhabitants (N ∈ N * ). This model is a Finite Automaton called M IDM A red N . For obtaining this model, we perform first a synchronous composition of N DM A and then a reduction of the result, based on the assumption of non-distinguishable inhabitants. For instance, considering the case study and 2 inhabitants, a partial representation of M IDM A red 2 is given in Fig. 5. The whole Automaton has 36 states, each of them is representing the location of the 2 inhabitants in the home. For instance, the state Z 2 .Z 1 means that there is one inhabitant in Z 2 and one in Z 1 . Since the inhabitants are non-distinguishable by the sensors, it is not possible to know which inhabitant is in Z 2 and which one is in Z 1 . Based on the proposed models M IDM A red N (∀N ∈ N * , with M IDM A red 1 = DM A), the aim of LT of a fixed and known number N of inhabitants is to estimate the reached state from an observed sequence of events. Since M IDM A red N is not deterministic, there are two possible procedures to perform online LT:

• The estimated current location (set of current states of M IDM A red N ) is directly computed online based on this non-deterministic model [START_REF]A Discrete Event Model for Multiple Inhabitants Location Tracking[END_REF].

• A state estimator is built offline in a first step and then the LT is performed online using this state estimator [START_REF] Danancher | Online Location Tracking of a Single Inhabitant based on a State Estimator[END_REF]. Both of these approaches are giving exactly the same LT result and any of them can be used as a basis for the LT of an a priori unknown number of inhabitants as detailed later in the paper (Fig. 6).

The complexities of modeling and tracking have been discussed in details in [START_REF] Danancher | A Discrete Event Approach for Model-Based Location Tracking of Inhabitants in Smart Homes[END_REF]. The number of states of M IDM A red N can be determined using the notion of multiset (see [START_REF] Stanley | Enumerative Combinatorics[END_REF] for more details about multisets and other enumerative problems). M IDM A red N has exactly Z N states, where Z N is the number of multisets of cardinality N (the number of inhabitants), with elements taken from a finite set of cardinality Z (the number of zones).

Z N is equal to the binomial coefficient Z+N -1 N = (Z + N -1)! N !(Z -1)! . The complexity of online LT is either O(|Q N | × 2S) where |Q N | is the number of states of M IDM A red
N and S is the number of sensors if the first approach (direct estimation) is used or the complexity is linear in the number of sensors O(2S) if the second approach (estimator-based) is used. Note that in the second case, the estimator is computed offline and the complexity is

O(2 |Q N | ).
Despite its apparent complexity, the proposed modeling and LT approaches remain scalable since we consider only instrumented apartments or houses and not a whole smart building (like for instance in [START_REF] Boyer | Privacy Sensitive Location Information Systems in Smart Buildings[END_REF]). Consequently, the number of zones Z, the number of sensors S and the number of inhabitants N remain small, thus, in practice there is no problem of state space explosion.

These previous results allowed us to deal with the case of a constant and known number of inhabitants. However, in real life, this number is neither constant nor known. Thus, we propose in the next section an approach for LT of an a priori unknown number of inhabitants.

III. LOCATION TRACKING OF AN A PRIORI UNKNOWN NUMBER OF INHABITANTS

It has been recalled in the previous section that a model of the detectable motion of N inhabitants (N ∈ N * ) can be built. Assuming there is a maximal number of inhabitants to be tracked in the Smart Home N max ∈ N * , the models M IDM A red 1 , M IDM A red 2 , ... M IDM A red Nmax can be built. These models are the basis of the proposed algorithm for the LT of an a priori unknown number of inhabitants. This algorithm is given in Fig. 6) and explained in the following.

The maximal number of inhabitants N max is supposed to be known and guaranteed in a first time. This parameter will be discussed in details in the next section. The proposed algorithm performs in the following way. At the beginning, the number of inhabitants N is assumed to be equal to 1. It is a conservative assumption since the case of an inhabitant being alone at home is considered as being the most critical. Indeed, health problem detection and automatic call to the emergency services are the most important when an inhabitant is alone at home. Then, previously introduced LT of a fixed number of inhabitants is performed using the different models. L Est1 is the estimated location obtained using Est(M IDM A red 1 ), L Est2 is the estimated location obtained using Est(M IDM A red 2 ), ..., L Est Nmax is the estimated location obtained using Est(M IDM A red Nmax ). When a new event e occurs, if the event is related to the zones being outside of the house, then it is symptomatic of a change of the current number of inhabitants in the house and thus there are three possible cases:

• The event e is representative of an augmentation of n of the number of inhabitants (for instance specific door barrier sensors giving the information of the direction of the inhabitant leading to n = 1 inhabitant entering the house), thus N = N + n. • The event e is representative of a diminution of n of the number of inhabitants, thus N = Nn and the models from N to N should be initialized again, • The event e gives no information about one or several inhabitants entering or leaving the house, it is just symptomatic of a change of the number of inhabitants, thus N = 1 in order to be back in the conservative case. If the observed event is not related to the zones being outside of the house, the new number of inhabitants N is estimated by trying to reproduce the event e with the different models Est(M IDM A red N ), ..., Est(M IDM A red Nmax ) where N is the previously determined number of inhabitants. It is assumed that the sensors have a fault-free behavior and thus, an event not being reproducible by a model Est(M IDM A red i ) is symptomatic of the presence of strictly more than i inhabitants. Consequently, the first automaton among Est(M IDM A red N ), ..., Est(M IDM A red Nmax ) which is able to reproduce the event is the one representing the current number of inhabitants.

Once the number N is calculated (either when the event is out-related or not), N is updated as being equal to N and L Est N , ..., L Est Nmax are calculated using the previously proposed LT algorithms. At this time, the current number of inhabitants is estimated by N and the location of these inhabitants is given by L Est N . Finally, the algorithm waits for a new event e and starts again.

This algorithm is illustrated on the case study for the following scenario (see Fig. 7). Two inhabitants are inside the house and it is considered that a maximal number of 3 inhabitants is guaranteed.

Step 0. At the beginning of the scenario one inhabitant is in the living room and one in the bathroom. The algorithm is initialized, the estimated number of inhabitants N is equal to 1 and the estimated location is

L Est1 = {Z 1 , Z 2 , Z 3 , Z 4 , Z 5 , Z 6 , Z 7 , Z 8 } (which is the initial state of M IDM A red 1 )
. This location is very ambiguous because the inhabitant may be in any of the eight zones. Moreover, this estimation is incorrect because the real number of inhabitants is equal to 2 and the real location is L Real = (Z 7 .Z 4 ).

Step 1. The first inhabitant is moving within the living room. A rising edge of the sensor M D 5 is observed and the estimated number of inhabitants and the estimated location are updated: N is still equal to 1 because the observed event is reproducible by M IDM A red 1 and L Est1 = {Z 7 }. This estimation is unique because there is only one zone in L Est1 , however, this estimation is incorrect because the real number of inhabitants is still 2 and the real location is L Real = (Z 7 .Z 4 ).

Step 2. The first inhabitant continues to move and enters the corridor. A rising edge of the sensor M D 2 is observed, N is still equal to 1 and L Est1 is now equal to {Z 2 }. Since the real location is L Real = (Z 4 .Z 2 ), the estimation is incorrect.

Step 3. Since there is no longer someone in the living room, a falling edge of the sensor M D 5 is observed. As explained previously, falling edges of motion detectors are not considered in any of the models, the estimated location is not updated and is still incorrect.

Step 4. The first inhabitant enters the shower. Since there is no sensor in this zone, no new sensor event is observed and the estimated location remains the same. The real location is now L Real = (Z 5 .Z 4 ) but the estimated location (Z 2 ) is still incorrect. Step 5. Since there is no longer someone in the corridor, a falling edge of the sensor M D 2 is observed. As for step 3, this event is not considered in any of the models and thus the estimated location is not updated and is still incorrect.

Step 6. The first inhabitant enters in the corridor again. He is detected through the rising edge of M D 2 . The estimated location is updated but is still equal to {Z 2 }. L Real is equal to (Z 4 .Z 2 ) again and the estimation is incorrect.

Step 7. The second inhabitant starts moving in the bathroom. A rising edge of the sensor M D 4 is observed. Since this event is not reproducible by M IDM A red 1 but by M IDM A red 2 , the estimated number of inhabitants is now N = 2 and their estimated location is given by M IDM A red 2 , L Est2 = {(Z 4 .Z 2 )} which is a unique estimation. The real location is L Real = (Z 4 .Z 2 ), consequently the estimation is correct.

Thanks to the results of this illustrative scenario, we can highlight the two following points.

First, the estimated location is a set of combinations of N zones (a set of zones if N = 1). Thus this estimation is either

unique if the cardinal |L Est | = 1 or ambiguous if |L Est | > 1.
Moreover, it is possible to define a Degree of Ambiguity DoA with the following formula.

DoA =    0 if |L Est | = 1 |L Est | |Q N | if |L Est | > 1
where |L Est | is the cardinal of the estimated location and |Q N | the number of states of the model M IDM A red N . Its meaning is the following:

• DoA = 0 means full information (unique estimation).

• 0 < DoA < 1 means partial information.

• DoA = 1 means no information at all (totally ambiguous estimation), this is the case for the initial estimation for instance.

Second, when comparing the estimated and the real Location, the estimated location can be either

correct if L Real ∈ L Est or incorrect if L Real / ∈ L Est .
Of course, in the case where the estimated number of inhabitants is not equal to the real number, the estimated location is also incorrect even if the location of some of the inhabitants is correctly estimated.

Based on these considerations on the LT result, the relevance of a chosen zone partition and instrumentation for LT should be evaluated. Moreover, in a general case, N max is unknown. Therefore, a procedure is needed in order to determine the intrinsic ability of a combination (Zone Partition -Instrumentation) to track N max inhabitants. Such evaluation procedures are proposed in the next section.

IV. PERFORMANCE EVALUATION

The evaluation is performed in two complementary steps: first a static analytical evaluation based only on the models, and second a dynamic evaluation based on the simulation of particular or critical scenarios.

A. Analytical evaluation

Several analytical performance criteria are proposed in this paper. They provide the designer with guarantees of locationability in the different zones and of the intrinsic maximal number of trackable inhabitants. These criteria are defined below and applied on the case study in a second time.

The first criterion is relative to the unlocationable zones as proposed in the following definition [START_REF] Danancher | Online Location Tracking of a Single Inhabitant based on a State Estimator[END_REF].

Definition 2 (Unlocationable Zones). Unlocationable zones are particular zones of the home (elements of Z) where the inhabitants are never estimated to be in. Each time the inhabitant is really in this zone, his estimated location is incorrect.

Based on this definition, a proposition to compute these unlocationable zones is given and proved below.

Proposition 1. The number of unlocationable zones (if they exist) can be quantified by the cardinal of Q U Z with:

Q U Z = {q ∈ Q | (q, σ) ∈ Q × Σ, δ(q, σ) = q } with Q the states of the DM A.
Since Q U Z ⊆ Q, each state q of Q U Z is related to a zone of Z according to Definition 1. Thus Q U Z represents the unlocationable zones.

Proof: According to the proposition, a state q of Q U Z is a state of the DM A being reachable only by the fact that it is initial. Thus, its related zone is related to the initial state of Est(DM A) but it is not related to any other state of Est(DM A) because there is no transition leading to q in the DM A. Consequently, the estimated location will never contain this zone and the inhabitants will never be estimated to be in this zone (except during the initial location estimation).

Moreover, a zone being unlocationable for single inhabitant is also unlocationable for multiple inhabitants. Consequently the set Q U Z is computed using only the DM A.

In addition to the unlocationable zones, two formulations of the ability to provide an accurate estimation of the location are given. They were first defined in [START_REF] Danancher | Online Location Tracking of a Single Inhabitant based on a State Estimator[END_REF] for the particular case of a single inhabitant. The generalization of these criteria for the case of N inhabitants (N ∈ N) is given below. Definition 3 (Strong N -accurate-location-ability). Considering a zone partition P and an instrumentation I, a combination (P, I) is strongly N -accurate-location-able if after a finite sequence of sensor events the location of the N inhabitants is accurate from now, whatever the inhabitants are doing.

Proposition 2. Considering that the set of states of Est(M IDM A red N ) -called Q Est N -can be divided into two subsets Q a N representing the set of accurate estimated locations and Q i N representing the set of inaccurate estimated locations such that

Q Est N = Q a N Q i N where: • Q a N = {q Est N ∈ Q Est N such that |q Est N | = 1} • Q i N = {q Est N ∈ Q Est N such that |q Est N | > 1}, a combination (P, I) is strongly N -accurate-location-able if Q a N is
not empty and there is no loop between states of Q i N and no transition from a state of Q a N to a state of Q i N . Formally this property is written:

(P, I) is N -strongly accurate-location-able if:            • Q a N = ∅ • ∀σ 1 σ 2 • • • σ m ∈ Σ * | ∃(q 1 , q 2 , • • • , q m , q m+1 ) ∈ Q m+1 i N ; δ Est N (q 1 , σ 1 ) = q 2 , • • • , δ Est N (q m , σ m ) = q m+1 ; ∀(q i , q j ) ∈ (q 1 , q 2 , ..., q m+1 ) 2 q i = q j • (q, σ) ∈ Q a N × Σ | δ Est (q, σ) ∈ Q i N Proof:
The condition of non-emptiness of Q a N and the condition of no transition from Q a N to Q i N guarantee that once a state of Q a N is reached, the subsequent states are also in Q a N and thus the location will be accurate. Moreover, if a state of Q i N is reached, the condition of no loop in Q i N guarantees that, after a sequence of events of maximum length |Q i N |, a state belonging to Q a N will be reached.

Definition 4 (Weak N -accurate-location-ability). A combination (P, I) is weakly N -accurate-location-able if it is possible that the location of the N inhabitants is accurate from now, depending on what the inhabitants are doing. Proposition 3. A combination (P, I) is weakly N -accuratelocation-able if Q a N is not empty and there are loops in Q a N . Formally this property is written:

(P, I) is weakly N -accurate-location-able if:

       • Q a N = ∅ • ∃σ 1 σ 2 • • • σ m ∈ Σ * | ∃(q 1 , q 2 , • • • , q m , q m+1 ) ∈ Q m+1 a N ; δ Est N (q 1 , σ 1 ) = q 2 , • • • , δ Est N (q m ,
σ m ) = q m+1 ; ∃(q i , q j ) ∈ (q 1 , q 2 , ..., q m+1 ) 2 q i = q j Proof: The condition of non-emptiness of Q a N and the fact that each state of Q a N is accessible (by construction of the estimator) guarantees that it is possible to enter at least one loop on Q a N . Thus, a sequence of events exists such that, after a certain number of events, the current location and subsequent locations become accurate.

Dealing with an a priori unknown number of inhabitants leads to define a maximal number of inhabitants. In the previous section, N max was assumed to be known. In fact this criterion is strongly relying on the chosen zone partition and instrumentation and thus can be determined a priori, only based on the models. Therefore, we propose the following definitions and proposition.

Definition 5 (Maximal number of trackable inhabitants N max ). The maximal number of trackable inhabitants is the maximal estimated number of inhabitants that can be given while performing LT of an a priori unknown number of inhabitants.

Definition 6 (Complete Finite Automaton). A Finite Automaton Aut = (Q, Σ, δ, Q 0 ) is said to be complete if, from each state, a transition labeled with each of the events exists. Formally:

Aut is a complete Finite Automaton if ∀(q, σ) ∈ Q × Σ δ(q, σ)! (with the notation δ(q, σ)! means that δ(q, σ) ⊆ Q i.e. at least one transition from state q labeled with the event σ is defined) Proposition 4. The maximal number of trackable inhabitants N max is defined by the first complete finite automaton representing the detectable motion of several inhabitants. Formally:

• if Est(DM A) is complete, N max = 1 • else N max = min i>1 (i) such that Est(M IDM A red i ) is complete and Est(M IDM A red i-1 ) is not complete, as- suming ∃i such that Est(M IDM A red i ) is complete. Proof: Based on Definition 6, if i is such that Est(M IDM A red i
) is a complete finite automaton, it is impossible to observe a behavior not being reproducible by Est(M IDM A red i ). Consequently, based on the algorithm for LT of an a priori unknown number of inhabitants (Fig. 6), it is impossible to increase the number of inhabitants by observing a non-reproducible behavior. Thus, N max is the minimal value of i for which Est(M IDM A red i ) is complete, if i exists.

Let us illustrate these criteria by using the case study. There are 2 unlocationable zones Q U Z = {Z 5 , Z 8 }. Strong Naccurate-location-ability cannot be guaranteed for any N ∈ {1, 2, 3, 4} but weak N -accurate-location-ability is guaranteed ∀N ∈ {1, 2, 3, 4}. Finally, the maximal number of trackable inhabitants N max = 4. Note that the strong and weak Naccurate-location-ability have been calculated only for N ∈ {1, 2, 3, 4} because N max = 4. It is not necessary to compute them for N > N max

Based on this whole analytical approach, a procedure to build and evaluate the models in parallel is proposed. Since N max is not known a priori, the algorithm of Fig. 8 is proposed. It is aimed to build all the models required for the LT of multiple inhabitants without building useless models (M IDM A red N for N > N max ). In a first step, the DM A is built and analytical evaluation is performed for single inhabitant LT (i = 1). Moreover, based on the potential completeness of the model, it is checked if N max = 1 or not. If not, then i is increased, the model for i inhabitants M IDM A red i is built and the evaluation for i-Inhabitants LT is performed. In addition, based on the potential completeness of the model, it is checked if N max = i or not. If not, then i is increased and model building and evaluation continue. If N max = i, then N max is found and the algorithm stops. At the end, all the required models (and no more) are built and the results of the analytical evaluation (unlocationable zones, Acurate-Location-Ability, maximal number of trackable inhabitants) are already obtained.

Once the models have been built and used for analytical evaluation of the performances, a second phase of evaluation based on the simulation can be performed. This simulationbased evaluation is presented in the next subsection.

B. Simulation-based evaluation

A simulation-based approach has been previously introduced in [START_REF] Danancher | A DES Simulator for Location Tracking of Inhabitants in Smart Home[END_REF] for the case of a fixed and known number of inhabitants. In the following we propose the generalization of the results for an a priori unknown number of inhabitants.

The simulation-based approach provides the designer with complementary results compared to the analytical one. Thus, two different instrumentations leading to the same analytical results can be discriminated in order to choose the one that best fits with the designer's needs. An overview of our simulationbased evaluation procedure is given in Fig. 9. The idea behind this evaluation is to emulate the Smart Home (its topology and its sensors) and to allow one or several user(s) to play the role of one or several inhabitant(s) inside the home. Thus, the human behavior is neither modeled nor simulated, it is a real human behavior immersed in the emulated Smart Home through a joystick (as shown in Fig. 10 where a user is playing a human behavior via the joystick). This approach is also useful for the designer to test critical scenarios (e.g. an elderly alone in the house, a young child alone in a dangerous zone, ...). A confusion matrix called CM LT is defined in order to evaluate the accuracy and correctness of the estimated location of inhabitants compared to their real location. Classically, a confusion matrix [START_REF] Kubat | Machine Learning for the Detection of Oil Spills in Satellite Radar Images[END_REF] represents the number of times a prediction corresponds or not to a real situation. It is mainly used to evaluate data-driven learning approaches e.g. Activities of Daily Living recognition in Smart Homes [START_REF] Chikhaoui | Activity Recognition in Smart Environments: An Information Retrieval Problem[END_REF].

Since the proposed approach is based on the DES theory, we propose a discrete formulation of the confusion matrix below.

CM LT (i,j) (E) = 1 |E| |E| k=0 1 {(Li=L Real (k)) ∧ (Lj ∈L Est (k))} |L Est (k)| dt
(1) where: -E is the sequence of changes of real or estimated location during the simulation. Note that this sequence is not the same as the sequence of sensor events, -1 {predicate} = 1 if predicate is true and 0 otherwise, -L i (resp. L j ) represents the i th (resp. the j th Based on this matrix, several performance criteria can be defined. The first one is named accuracy and gives the proportion of events after which the estimated location was the real one during the simulation (e.g. if the estimated location was correct after 35 events among the 50 events generated during a simulation, then the accuracy is equal to 70%). Formally it is the sum of the diagonal elements of the confusion matrix:

accuracy(E) = i CM LT (i,i) (E) ∈ [0, 1] (2)
An example of the evolution of the accuracy for an average scenario is given in Fig. 11. After a sequence of 50 events, the accuracy reaches the value of 58%.

The accuracy gives a global measure of the LT performance. Complementary to this indicator, two criteria concerning each possible location are defined. The precision p is the proportion of events after which the estimated location correctly represents the real location and the recall r is the proportion of time for which a real location is correctly estimated. Formally, for a given location i among the |L| possible locations:

p(i,E) = CM LT (i,i) (E) j CM LT (j,i) (E) ∈ [0, 1] (3)
r(i,E) = CM LT (i,i) (E) j CM LT (i,j) (E) ∈ [0, 1] (4)
The criteria precision and recall can be combined using a geometric mean called gmean:

gmean(i, E) = r(i, E) • p(i, E) ∈ [0, 1] (5)
An example of the evolution of this gmean for each zone of the home for an average scenario is given in Fig. 12. After a sequence of 50 events, gmean(Z 5 ) and gmean(Z 8 ) remain equal to 0%, this confirms the fact that Z 5 and Z 8 are unlocationable zones. This criteria also allows highlighting some other weaknesses in the chosen instrumentation, particularly in zones Z 3 and Z 6 where the gmean is quite low. On the contrary, the result are good for Z 1 where gmean is above 90%.

These results are interesting and complementary to the analytical ones, however they are obviously strongly relying on the simulated scenario. Moreover, note that alternative timebased definitions of this confusion matrix and of the related criteria have been given in [START_REF] Danancher | A DES Simulator for Location Tracking of Inhabitants in Smart Home[END_REF].

C. Improvement loop

Based on the previously described evaluation procedures (analytical and simulation-based), an approach for assisted improvement of Smart Home instrumentation is proposed. This approach is named evaluation-aided improvement of Smart Home instrumentation and an overview is given in Fig. 13. The idea behind is to provide the designer with indications to improve his choice in terms of zone partition and instrumentation in order to finally get a Smart Home and models compliant with his needs. A closed loop of improvement is proposed. First, the designer describes an initial combination zone partition -instrumentation (step 1 of Fig. 13), the models are systematically generated and evaluated using the iterative procedure of Fig. 8 (steps 2 and 3 of Fig. 13). Then, based on these results, the designer can make any changes he wants in the combination zone partition -instrumentation (step 4 of Fig. 13) and compute again the model building and analytical evaluation. Modeling, analytical evaluation and modification constitute the first loop of improvement.

When the analytical results are satisfying or when several possible combinations having the same analytical performances are to be compared, the designer can perform simulation-based evaluation and test some particular or critical scenarios. This is the second loop of improvement, composed of modeling (step 2), simulation-based evaluation (step 5) and modification (step 6). Different combinations can be compared on exactly the same scenario. Thus, either the designer is satisfied with one of the tested combinations and choose this one for real implementation (step 7), or he gets indications to improve again the combination and the loop starts again.

Moreover, since the zone partition is strongly relying on the application (health problem detection, safety ensuring), it is assumed that the zone partition should not be a parameter that can be modified. Consequently, the expert should only modify the instrumentation by changing the number of sensors and/or their position in the Smart Home.

Note that we do not propose an optimization procedure but only two improvement loops relying on the competences of the expert. Solving this problem with a classical optimization approach would require having constant models which is not the case here because these models are changing after each modification of the parameters zone partition -instrumentation. Moreover, the expert is assumed to know the topology of the Smart Home in detail and thus he would consider only realistic instrumentation. This detailed description of the Smart Home is hard to formalize but mandatory for the usage of an optimization approach in order to avoid having non-installable instrumentation as a result.

These improvement loops can be illustrated on the case study. Let us recall the previously given results of the evaluation of the initial zone partition -instrumentation. There was two Unlocationable Zones Z 5 and Z 8 , Weak N -accuratelocation-ability ∀N ∈ {1, 2, 3, 4} and N max = 4.

Since there are two Unlocationable Zones, the expert decided to solve this problem by adding a sensor for each of them i.e. one motion detector was added in the shower and one was added outside the house. By computing the models and the analytical evaluation after this modification, there are no more Unlocationable Zones and N max has been increased to 5. There is still no Strong N -accurate-locationability ∀N ∈ {1, 2, 3, 4, 5} but Weak N -accurate-locationability ∀N ∈ {1, 2, 3, 4, 5}.

To solve the problem of Weak accurate-location-ability, the expert decided to replace the door barrier sensor DB 1 by a motion detector in the toilets and to remove the door barrier sensor DB 2 between the first bedroom and the corridor. By computing the models and the analytical evaluation, there are still no Unlocationable Zones, Strong 1-accurate-locationability, Weak N -accurate-location-ability ∀N ∈ {2, 3, 4, 5, 6} and N max has increased to 6.

Moreover, the simulation-based results are confirming these analytical results. Accuracy (as shown in Fig. 14), precision and recall (not shown here) are better for the same scenario. Finally, the expert wanted to see the impact of adding floor pressure sensors in this Smart Home, he added several of them, mainly in the living room and in the second bedroom. By computing the new models and the analytical evaluation, the performances are exactly the same as with the previous instrumentation (without floor pressure sensors). Thus, the expert played several scenarios with the emulated Smart Home and the results showed an improvement of the performances by adding these new sensors. Simulation-based evaluation allowed the expert to discriminate two analytically equivalent instrumentations.

Note that the proposed improvement approach strongly relies on the expert knowledge and it is not possible to generalize the improvement scenario proposed for this case study (first adding two motion detectors, then replacing and removing sensors and finally adding new ones).

V. CONCLUSION

In this paper, we presented an extension of previous work and proposed a complete approach for model-based LT of an a priori unknown number of inhabitants. The LT algorithm has been given and explained. Moreover, we proposed a whole approach for evaluation-aided improvement of a Smart Home instrumentation based on two different evaluation approaches, one being analytical and the other based on the simulation. This double loop of improvement is involving the expert to define the instrumentation that best fits with his needs.

As written in the problem statement, it is assumed that each sensor is behaving in a fault-free manner. Since it is obviously not the case in a real Smart Home, an outlook for future work is to consider sensor faults and to propose approaches for Fault Detection and Isolation dedicated to Smart Homes and for Fault Tolerant LT. Another outlook consists in putting the patient into the development loop of the Smart Home. We are currently working on a patient-centered approach for health at home, based on the LT results and other information (wearable medical sensors, doctor's diagnosis)

Fig. 1 .

 1 Fig. 1. General overview of the proposed approach

Fig. 2 .

 2 Fig. 2. Description of the case study

Fig. 3 .

 3 Fig. 3. Description of the zone partition (a) and of the instrumentation (b)

Definition 1 (

 1 Detectable Motion Automaton). A Detectable Motion Automaton (DM A) is a Finite Automaton representing the different possible locations of a single inhabitant and the possible observation of his change of location.

Fig. 4 .

 4 Fig. 4. Detectable Motion Automaton DM A

Fig. 5 . 2 (

 52 Fig. 5. Detectable Motion Automaton for 2 inhabitants M IDM A red 2

Fig. 7 .

 7 Fig. 7. Illustrative scenario of two inhabitants in the Smart Home

Fig. 8 .

 8 Fig. 8. Procedure for iterative model-building and evaluation

Fig. 9 .

 9 Fig. 9.Overview of the procedure for simulation-based performance evaluation

Fig. 10 .

 10 Fig. 10. Usage of the developed software

  ) possible location of the inhabitants, -L Real (k) is the real location (each in one zone) of the inhabitants after the k th change of location, -L Est (k) is the estimated location (in a set of zones, possibly containing only one combination of zones) of the inhabitants after the k th change of location, -|L Est (k)| is the number of combination of zones composing the estimated location (for instance, if the estimated location L Est (k 1 ) = (Z 1 , Z 2 ), then |L Est (k 1 )| = 2). For an a priori unknown number of inhabitants between 1 and N max , there are |L| possible locations |L| = Nmax N =1 |Q N | considering every possible number of inhabitants being in the house.An example of this confusion matrix after an average scenario is given below.CM LT (E 1 ) = estimated location Lj Z1 . . . Z8 Z1.Z1 . . . Z8.Z8 . . .

Fig. 11 .

 11 Fig. 11. Accuracy for an average scenario

-Fig. 12 .

 12 Fig. 13. Loops for instrumentation improvement

Fig. 14 .

 14 Fig. 14. Comparison of the accuracy for the same average scenario for the initial instrumentation (1 st ) and for the improved instrumentation (2 nd )

  Initialization of the current 𝐿 𝐸𝐸𝐸 1 , 𝐿 𝐸𝐸𝐸 2 , …, 𝐿 𝐸𝐸𝐸 𝑁𝑁𝑁𝑁 as the initial states of 𝐸𝐸𝐸(𝐷𝐷𝐷), 𝐸𝐸𝐸(𝐷𝑀𝐷𝐷𝐷 2 𝑟𝑟𝑟 ), …, 𝐸𝐸𝐸(𝐷𝑀𝐷𝐷𝐷 𝑁 𝑁𝑁𝑁 𝑟𝑟𝑟 ) 𝟏 and initialization of 𝐿 𝐸𝐸𝐸 1 , 𝐿 𝐸𝐸𝐸 2 , …, 𝐿 𝐸𝐸𝐸 𝑁𝑁𝑁𝑁 if no clue on entering or leaving Current number of inhabitants = 𝑁 Current location of the inhabitants = 𝐿 𝐸𝐸𝐸 𝑁

		start
		Initialization 𝑁 = 1
	Wait for a new event 𝑒
	no	Is 𝑒 an out-	yes
		related event ?
	𝑁𝑁 = min (𝑖) such that 𝑒 is reproducible by	𝑵𝑁 = 𝑵 -𝒏 and initialization of 𝐿 𝐸𝐸𝐸 𝑁′ , …, 𝐿 𝐸𝐸𝐸 𝑁-1
	𝐸𝐸𝐸(𝐷𝑀𝐷𝐷𝐷 𝑖 𝑖 ∈ {𝑁, … , 𝑁 𝑚𝑚𝑚 } 𝑟𝑟𝑟 ) for	if 𝑒 represents 𝑛 inhabitants leaving or 𝑵𝑁 = 𝑵 + 𝒏
		if 𝑒 represents 𝑛 inhabitants entering
		Update 𝑁 = 𝑁𝑁
	Update 𝐿 𝐸𝐸𝐸
	yes	Continue Location
		Tracking ?
		no
		end

or 𝑵𝑁 = 𝑁 , …, 𝐿 𝐸𝐸𝐸 𝑁𝑁𝑁𝑁 using the LT algorithm of a known and fixed number 𝑖 of inhabitants for 𝑖 ∈ {𝑁, … , 𝑁 𝑚𝑚𝑚 } Fig.

6

. Algorithm to track the location of an a priori unknown number N of inhabitants

. . . . . . . . . . . . . . . . . . . . . Z8.Z8 0.0 . . . 0.1 0.0 . . . 0.1 . . . . . . . . . . . . . . . . . . . . . . . . . . .