Immobilisation de polygones par des ensembles donnés de points

Arbone, Ion (2015). Immobilisation de polygones par des ensembles donnés de points. Mémoire. Gatineau, Université du Québec en Outaouais, Département d'informatique et d'ingénierie, 94 p.

Prévisualisation

PDF Télécharger (110MB) | Prévisualisation

Résumé

La plupart des robots d'aujourd'hui sont programmés en vue d'accomplir certaines actions prédéfinies, comme celle de maintenir un objet dans une position fixe pour pouvoir le manipuler. Ainsi, le domaine de l'immobilisation est devenu un champ important de la robotique qui joue un rôle primordial dans la construction d'un produit de qualité.

Dans cette étude, nous sommes intéressés à l'analyse du problème d'immobilisation de figures lorsque l'ensemble de positions à partir duquel on peut choisir les points d'immobilisation est imposé au départ. Plus précisément, notre attention porte sur le problème de l'immobilisation de figures dans le cas où l'ensemble de points d'obstacle est restreint à un ensemble fini de positions sur le bord de figures. L'objectif principal de cette recherche a deux volets. Le premier est fondé sur la recherche d'un algorithme qui vérifie si un ensemble donné de points immobilise un objet, tandis que le second est basé sur la recherche d'un algorithme qui trouve un petit sous-ensemble de points d'immobilisation. Nous proposons une approche géométrique, car nous allons analyser l'ensemble de positions valides induites dans l'espace des configurations par les points obstacles. Nous donnons trois algorithmes pour vérifier si un ensemble de points sur le bord d'un objet immobilise ou non l'objet. Le premier algorithme est optimal, mais il fonctionne quand les données sont en position générale. Les deux autres algorithmes, l'algorithme glouton, s'exécutant en temps O(n3), et l'algorithme plus élaboré, marchant en temps O(n log n), fonctionnent pour des données quelconques. A notre connaissance, aucune autre algorithme pour ce problème d'immobilisation n'est connu dans la littérature.

Type de document:	Thèse (Mémoire)
Directeur de mémoire/thèse:	Czyzowicz, Jurek
Informations complémentaires:	Localisation : Bibliothèque L.-Brault TJ 211 A73 2015
Mots-clés libres:	Algorithmes; Ensemble de points (Mathématiques); Robotique; Théorème de Helly
Départements et école, unités de recherche et services:	Informatique et ingénierie
Date de dépôt:	14 déc. 2015 14:20
Dernière modification:	04 nov. 2016 16:10
URI:	https://di.uqo.ca/id/eprint/786

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt