A multiple hypothesis tracking for activity monitoring: a constraint-based approach

Advancements in ubiquitous sensing and actuation devices offer new possibilities in the realization of physical and cognitive support services. The services provided by enabling components can be combined to obtain overall functionalities with high added value. In this thesis we describe an on-line, model-based approach to support service planning aimed at bridging the gap between sensing and support service planning. We focus on the context recognition capabilities of the service planning system, proposing a constraint-based reasoning solution. In particular, we focus on the need of dealing with ambiguous models, i.e., models in which the infrastructure can concurrently support different indications about the current context of the monitored system. We show that the cost of tracking multiple hypotheses with this approach increases more than exponentially as sensor readings are accumulated, how this worst case cost can be made exponential by imposing a partial form of the Markov assumption, and that the approach becomes practically feasible in a real context through the use of heuristics.

Negli ultimi anni, notevoli miglioramenti nel campo dell’intelligenza artificiale e della robotica hanno portato a una crescente domanda per servizi sempre più sofisticati negli ambienti domestici; ed è verosimile pensare che le case stesse, presto, saranno pronte ad accogliere infrastrutture standardizzate che permettano il funzionamento e la cooperazione di strumenti robotici. In particolare, sistemi che automaticamente riconoscono le attività dell’utente osservato potrebbero fornire servizi di supporto fisico o cognitivo, come ad esempio accade nei sistemi per l’assistenza di malati o anziani. Il tema centrale di questa tesi, sviluppata presso il Mobile Robotics Lab dell’università di Örebro, in Svezia, è proprio quello di realizzare un’infrastruttura che fornisce i mezzi per monitorare le attività dell’utente osservato. Il tema Activity Recognition è molto studiato e ricerche interessanti si sono focalizzate, finora, sul riconoscere semplici attività umane; invece, riconoscere attività complesse rimane ancora un’area molto attiva della ricerca. Per questa ragione, nella presente tesi, vogliamo soffermarci sul bisogno di gestire modelli ambigui di Activity Recognition, cioè modelli in cui l’infrastruttura può, parallelamente, supportare indicazioni differenti riguardanti il contesto attuale del sistema monitorato. Potremmo voler analizzare e supportare modelli ambigui per vari motivi. Ad esempio, per riconoscere attività parallele dell’utente, per gestire ambiguità nell’interpretazione di attività apparentemente simili, o per risolvere l’incertezza data dai sensori usati nel monitoraggio. Il nostro punto di partenza è stato l’analisi del software preesistente di Activity Recognition SAM. SAM è un’architettura software a componenti per planning e scheduling. SAM realizza un processo temporale di reasoning su pattern di osservazioni sensoriali fornite dall’ambiente, ed è anche in grado di sintetizzare piani di azione per gli attuatori d’ambiente, in reazione alle attività umane riconosciute. Uno dei limiti di SAM consiste però nel fatto di seguire un approccio sequenziale nel processo di Activity Recognition; per ogni iterazione del processo, infatti, non tiene traccia di più attività contemporaneamente. Da questa inabilità nel supportare modelli ambigui nasce il bisogno di estendere il framework, in modo da avere una strategia di pianificazione più sofisticata, che tenga conto di tutte le possibili ipotesi sul contesto del sistema monitorato, e che porti quindi, se necessario, a spiegazioni differenti sul comportamento dei componenti controllati. Allo scopo di estendere SAM, introducendo un Multiple Hypothesis Approach, abbiamo effettuato dei cambiamenti sostanziali nel precedente codice del software. In particolare, è stato necessario modificare ed estendere tutte quelle classi riguardanti il processo di generazione e gestione delle ipotesi. Naturalmente, il fatto di tener traccia di più ipotesi contemporaneamente comporta un incremento nella complessità dell’algoritmo. Per questo, abbiamo realizzato uno studio formale atto a valutare la complessità dell’algoritmo e ad individuare delle euristiche per migliorarne l’efficienza. In particolare, abbiamo proposto una formalizzazione per il numero totale di ipotesi trovate dall’algoritmo, a ogni iterazione, e notato come queste ipotesi si basino non solo sullo stato attuale, ma anche sugli stati passati, costruiti su letture sensoriali che si riferiscono a iterazioni precedenti. Si può dimostrare la completezza dell’algoritmo in quanto quest’ultimo, con la nuova procedura a più ipotesi di Activity Recognition, riesce a costruire un albero completo di decisioni. Per quantificare la dimensione dello spazio degli stati, abbiamo considerato il caso peggiore in termini di complessità algoritmica e mostrato che la complessità è più che esponenziale. Per ridurre la complessità, ma al tempo stesso mantenere la completezza, abbiamo introdotto nell’algoritmo un’assunzione markoviana parziale di indipendenza dagli stati passati, che ha reso la complessità esponenziale. Per ridurre ulteriormente il numero di ipotesi mantenute a ogni iterazione abbiamo sviluppato due euristiche che permettono di eliminare gli stati inattivi e gli stati simili tra loro. Infine, per testare e dimostrare l’applicabilità del nuovo sistema in un contesto reale, abbiamo effettuato un test sperimentale in un ambiente intelligente come la PEIS Home. La PEIS Home è un ambiente sperimentale costruito, nell’università svedese di Örebro, come un piccolo appartamento contenente un soggiorno, una cucina e una camera da letto, ed è provvisto di un’infrastruttura di comunicazione e computazione, e di vari sensori e attuatori. L’esperimento, quindi, intende mostrare come, con l’estensione di SAM, è possibile riconoscere attività domestiche reali compiute da un umano in un contesto reale,utilizzando il Multiple Hypothesis Approach. Il test è stato effettuato con successo su un intervallo temporale di esecuzione di quattro ore, e tutti gli obiettivi dell’esperimento sono stati raggiunti; infatti, il sistema ha tenuto traccia di ogni ipotesi che poteva essere dedotta dalle letture sensoriali, fino a quattro ipotesi contemporaneamente. La buona performance del sistema ci ha mostrato anche come il ruolo delle euristiche implementate sia fondamentale. Ripetendo infatti il test senza le euristiche, si può notare come, già dopo qualche decina di iterazioni, il costo per mantenere attive tutte le possibili ipotesi sia elevatissimo e, come il sistema diventi lento e predisposto agli errori.