Unsupervised semantic perception, summarization, and autonomous exploration for robots in unstructured environments

This thesis explores the challenges involved in building autonomous exploration and monitoring systems, and makes contributions on four fronts: describing the semantic context of the collected data, summarizing this information, deciding where to collect this data, and making optimal online irrevocable decisions for physical sample collection. Making high level decisions based on the environmental context of a robot's location requires that we first describe what is being observed in a semantic space with higher level of abstraction than the low level sensor reading. ROST, a realtime online spatiotemporal topic modeling technique that we develop in this thesis solves the problem of obtaining such high level descriptors. Topics in this case represent the latent causes (such as objects and terrains). ROST extends previous work on topic modeling by efficiently taking into account the spatiotemporal context of an observation, and using a novel Gibbs sampling technique to refine the topic label assignment in realtime. Our experiments suggest that taking into account the spatiotemporal context of observations results in better topic labels that have higher mutual information with ground truth labels, compared to topic modeling without taking into account the spatiotemporal context. Moreover we show that the perplexity of the online topic model using the proposed Gibbs sampler is competitive with batch Gibbs sampler. Given a scene descriptor such as bag-of-words, location, or topic distribution, the thesis then proposes a novel online summarization algorithm, which unlike previous techniques focuses on building a navigation summary containing all the surprising scenes observed by the robot. We argue that the summaries produced by the algorithm (called extremum summaries) are ideal for monitoring and inspections tasks, where the goal is to maintain a small set of images that is representative of the diversity of what has been observed. Although computation of an optimal summary, even in the batch case is NP-hard, we empirically show that the approximate online algorithm presented in the thesis produces summaries with cost that is statistically indistinguishable from batch summaries, while running on natural datasets. Cost was measured as the distance of the farthest sample from a sample in the summary. Collecting data from an environment to build a topic model or a summary requires a robot to traverse this environment. If the geographic size of this region of interest is small then we can simply use any space filling curve to plan this path. However, for larger areas this might not be possible, and hence we propose an information theoretic exploration technique which biases the path towards locations with high information gain in topic space. The resulting topic models were empirically shown to perform better than topic models learned with other competing exploration algorithms, such as free space exploration. Performance was measured in terms of mutual information with ground truth labels, and mutual information with topic labels computed in batch mode with complete knowledge of the environment. Many exploration robots are required to collect samples and perform some chemical or physical analysis. Often such a task requires making irrevocable decisions on whether to select the current sample or not. This thesis presents a novel formulation of this task as an instance of the secretaries hiring problem. We examine several existing variants of this problem, and present an optimal solution to a new variant of the secretaries hiring problem, where the goal is to maximize the probability of identifying the top K samples online and irrevocably. Together, the contributions of this thesis are a step towards developing fully autonomous robotic agents that can be used in collaboration with humans to explore dangerous unknown environments.Cette thèse explore les défis rencontrés afin de réaliser des systèmes autonomes d'exploration et de surveillance. Elle apporte des contributions sur quatre fronts : description du context sémantique d'un jeu de donnée, résumé automatique de cette information, décision sur les endroits où collecter ces données et finalement la prise de décision irrévocable liée à la saisie ou le traitement d'échantillons physiques. À fin de prendre des décisions de haut niveau basées sur le contexte du milieu environnant d'un robot, nous devons d'abord décrire les observations dans un espace sémantique d'un niveau d'abstraction plus élevé que celui représenté par l'espace des mesures des capteurs. ROST, un modèle de sujet (topic modeling) d'abstraction spatio-temporel en ligne que nous avons développé dans cette thèse, résout le problème de l'obtention de telle description de haut niveau. Dans le cas qui nous intéresse, les sujets (topics) représentent les causes latentes (telles que les objets ou terrains présents) produisant les observations. ROST étend des travaux antérieurs sur la modélisation de sujet, en tenant compte de manière efficace du contexte spatio-temporel d'une observation, et en utilisant un nouvel échantillonneur Gibbs pour raffiner l'assignation d'étiquette de sujet. Cette approche rend possible le traitement de flux de données en temps-réel, tels que la vidéo et l'audio capturés par un robot. Nos expérimentations suggèrent que tenir compte de ce contexte spatio-temporel donne un étiquetage plus proche de la vérité-terrain (du point de vue de l'information mutuelle), comparativement à ne pas en tenir compte. De plus, nous montrons que la mesure de perplexité de cette modélisation en ligne utilisant note échantillonneur Gibbs est compétitive avec un échantillonneur Gibbs par lot. À partir d'un descripteur de scène tel que sac de mots (bag-of-words), location ou distribution de sujets, nous proposons un nouvel algorithme de résumé en ligne qui, contrairement aux approches précédentes, se concentre sur la construction d'un résumé de navigation contenant les scènes dites surprenantes observées par le robot. Nous soutenons que les résumés produits par cet algorithme (appelés résumés extremums) sont idéaux pour les tâches de surveillance et d'inspection. Pour ces tâches, l'objectif est de conserver un petit ensemble d'images représentatif de la diversité des observations. Bien que la complexité en temps de calcul d'un résumé optimal (même en traitement par lot) soit NP-dur, nous avons démontré de manière empirique que notre algorithme approximatif de résumé en ligne produit des résumés avec des coûts qui sont statistiquement impossibles à distinguer des résumés obtenus par lot, pour des jeux de données naturelles. Ce coût était établi en fonction de la distance de l'échantillon le plus éloigné d'un des échantillons conservés dans le résumé. Afin de construire un modèle de sujet ou un résumé pour un environnement donné, un robot doit le traverser pour effectuer une collecte de données. Si l'étendue géographique de la région d'intérêt est petite, alors il est possible de simplement la couvrir avec une trajectoire basée sur n'importe quelle courbe remplissant l'espace. Cependant, pour des regions plus étendues, cette approche devient peu pratique. Par conséquent, nous proposons une technique d'exploration basée sur la théorie de l'information, qui dirige la trajectoire vers les endroits contenant plus d'information dans l'espace des sujets (topic space). Nous démontrons empiriquement que les modèles de sujets découlant de cette approche performent mieux que les modèles de sujets appris par l'entremise d'autres algorithmes, tel que l'algorithme d'exploration par les espaces libres (free space exploration). Cette performance a été mesurée en terme d'information mutuelle avec la vérité-terrain, et avec les étiquettes de sujets estimées à partir d'un algorithme par lot possédant une connaissance complète de l'environnement. De nombreux robots explorateurs doivent faire la collecte d'échantillons physiques ainsi que certaines analyses chimique ou physique in-situ. Très souvent, ces tâches impliquent la prise de décisions irrévocables à savoir si un tel échantillon doit être sélectionné ou non. Nous présentons une nouvelle formulation de cette tâche comme une du problème de l'embauche de secrétaires (secret aries hiring problem). Nous examinons plusieurs variantes de ce problème, et présentons une solution à la nouvelle variante proposée. Pour cette dernière, l'objectif est de maximiser la probabilité d'identifier les K meilleurs échantillons, de manière irrévocable. Ensemble, les contributions de cette thèse constituent une avance vers le développement d'agents robotisés entièrement automatisés, permettant l'exploration de l'environnements dangereux en collaboration avec les humains