Recherche de chemin à travers l’algorithme A* en C++ 1/4 : Introduction du problème, concept de modélisation informatique et initiation à la programmation orientée objet

Généralités

Objectifs

L’objectif du cours n’est pas de vous transformer en un professionnel du C++ ou de la Programmation Orientée Objet, l’objectif est de vous initier à 3 concepts : la modélisation de problèmes informatiques par la programmation orientée objet, la programmation orientée objet et l’algorithmie. Nous allons partir d’une problématique complexe de la robotique : la navigation dans un espace inconnu et incertain. Cette problématique sera ensuite simplifiée pour se concentrer sur un aspect de la navigation : la planification de trajectoire dans un environnement statique.

Diapositives utilisées lors de la séance

Présentation du cours et prérequis

  1. Mardi 23 novembre : Introduction du problème, concept de modélisation informatique et programmation orientée objet.
  2. Mardi 30 novembre : Fondamentaux du C++ 💻. ⚠️ Le cours sera potentiellement décalé
  3. Mardi 7 décembre : Algorithmes de recherche de chemin, étude algorithmique de l’A*
  4. Mardi 14 décembre : Implémentation de l’A* 💻

Ce cours nécessite les bases des connaissances de l’algorithmie (savoir ce qu’est un algorithme et les manipulations de ces derniers), un environnement capable de compiler du c++ (sudo apt install gcc sur Ubuntu, ce tutoriel pour Windows).

Il est préférable d’avoir les connaissances de base en compilation et de maîtriser le langage C pour ce cours. Le cas échant, le cours sera adapté.

Programme du cours

  • Présentation du cours (30 minutes)
  • Introduction au problème de navigation en robotique (30 minutes)
  • Initiation à la Programmation Orientée Objet (1 heure)

Introduction à la robotique de navigation

Ce cours part d’une problématique connue de la robotique : comment réussir à faire une navigation autonome dans un environnement.

Un robot est une machine équipée de capacités de perception, de décision et d’action qui lui permettent d’agir de manière autonome dans son environnement en fonction de la perception qu’il en a. L’objectif de cette introduction est de fournir un aperçu des problèmes de la robotique mobile et des solutions actuelles, plus particulièrement des problématiques de navigation. Les stratégies de navigation permettent à un robot mobile de se déplacer pour rejoindre un but, les différentes stratégies de navigation sont extrêmement diverses. Nous allons voir dans cette partie la navigation basée sur des cartes

Les trois problèmes de la navigation par carte

Le processus complet qui permet à un robot de mémoriser son environnement, puis de s’ys déplacer pour rejoindre un but, peut être découpé en trois phases : la cartographie, la localisation et la planification. Ces trois phases permettent de répondre aux trois questions fondamentales de pour la tâche de navigation : Où suis-je ? Où sont les autres lieux par rapport à moi ? Et comment puis-je atteindre mon but ?

  • La cartographie est la phase qui permet la construction d’une carte reflétant la structure spatiale de l’environnement à partir des différentes informations recueillies par le robot.
  • Une telle carte étant disponible, la localisation permet alors de déterminer la position du robot dans la carte qui correspond à sa position dans son environnement réel.
  • La planification, enfin, est la phase qui permet, connaissant la carte de l’environnement et la position actuelle du robot, de décider des mouvements à effectuer afin de rejoindre un but fixé dans l’environnement.

Ces trois phases sont évidemment fortement interdépendantes. L’ordre dans lequel elles sont citées fait directement apparaître le fait que la seconde phase dépend de la première. En effet, estimer sa position au sein d’une carte de l’environnement suppose implicitement que cette carte existe et qu’elle contient la position du robot. De même, la troisième phase dépend des deux premières, car la planification suppose que l’on connaisse sa position et que la carte de l’environnement représente une porte de l’environnement contenant au moins un chemin reliant cette position au but qui doit être atteint.

Mais la relation entre les deux premières phases est plus subtile qu’une simple relation d’antériorité : c’est le même problème que pour l’œuf et la poule. Chacun des deux éléments peut, en effet, être considéré comme préalable à l’autre, mais dépend aussi de l’autre pour sa réalisation. Dans le cas de la cartographie et de la localisation, nous avons déjà vu que la localisation repose sur une phase préalable de cartographie. Mais pour construire une carte, il est nécessaire de savoir où ajouter, dans la carte partiellement déjà existante, toute nouvelle information recueillie par le robot. Cela requiert donc une phase préalable de localisation au sein de la carte partielle déjà existante. Pour un robot complètement autonome, il est donc impossible de ne pas traiter ces deux problèmes simultanément. Pour résoudre ce problème, nous allons utiliser le Simultaneous Localization And Mapping, SLAM.

Localisation

Un robot doit pouvoir se localiser dans l’espace pour se faire il peut compter sur ses capteurs. Souvent il en a minimum deux : l’un sur ses moteurs permettant de réaliser une odométrie et l’autre permet de “voir” son environnement comme un LIDAR permettant de réaliser des algorithmes comme l’algorithme à particule de Monte Carlo.

Odométrie

L’odométrie est une technique permettant d’estimer la position d’un véhicule en mouvement. Cette mesure de bas niveau est présente sur quasiment tous les robots mobiles, grâce à des capteurs embarqués permettant de mesurer le déplacement des roues (deux dans ce cas).

L’odométrie repose sur la mesure individuelle des déplacements des roues pour reconstituer le mouvement global du robot. En partant d’une position initiale connue et en intégrant les déplacements mesurés, on peut ainsi calculer à chaque instant la position courant du véhicule.

Pour calculer le mouvement global du robot à partir des mesures odométriques, il est nécessaire de disposer d’un modèle décrivant le robot. L’exemple le plus courant en robotique est celui d’un robot dont le déplacement est contrôlé par le différentiel de vitesse entre les deux roues motrices. On note

  • \(d_g\) et \(d_d\) les déplacements respectifs des roues gauche et droite
  • \(v_g\) et \(v_d\) les vitesses respectives des roues gauches et droites
  • \(x, y, \theta\) les coordonnées du robot
  • \(d\) le déplacement du robot
  • \(v\) la vitesse du robot
  • \(e\) l’écart entre les deux roues
  • \(x_0, y_0\) et \(R\) les coordonnées du centre \(O\) du cercle trajectoire et le rayon de celui ci.
Modèle direct

Si l’on suppose que la trajectoire du robot est un cercle de rayon \(R\) parcouru à la vitesse angulaire \(\frac{d\theta}{dt}\) (\(R >0\) si le cercle est parcouru dans le sens trigonométrique) alors on a :

$$v = R \frac{d\theta}{dt}$$

Dans ce cas, les vitesses des roues sont données par

$$\begin{cases} v_g = (R – \frac{e}{2}) \frac{d\theta}{dt} = (R – \frac{e}{2}) \frac{v}{R} \\ v_d = (R + \frac{e}{2}) \frac{d\theta}{dt} = (R + \frac{e}{2}) \frac{v}{R}\end{cases}$$

On a donc construit un modèle direct du déplacement du robot.

Modèle inverse

L’odométrie va cependant nécessiter la connaissance du modèle inverse du déplacement du robot : connaissant les mesures odométriques, on cherche à retrouver les paramètres de la trajectoire. Nous pouvons supposer qu’à chaque instant et durant un intervalle de temps très court, la trajectoire du robot s’apparente à un cercle. Il suffit donc d’inverser le modèle direct précédemment construit pour un cercle, et nous pourrons reconstruire le rayon de courbure local de la trajectoire et la vitesse du robot. L’inversion du système précédent donne

$$\begin{cases} v = \frac{v_g + v_d}{2} \\ R = \frac{e}{2} \frac{v_d + v_g}{v_d – v_g} \end{cases}$$

Calcul d’odométrie

Nous sommes maintenant en mesure de mettre à jour la position du robot en temps réel :

  • à chaque instant, les mesures odométriques donnent les déplacements des roues \(d_g\) et \(d_d\) depuis l’instant précédent
  • le modèle inverse (dans lequel l’intervalle de temps a été éliminé et les vitesses remplacées par des déplacements) permet de calculer le déplacement \(d\) du robot et le rayon de courbure instantané \(R\) de la trajectoire
  • nous calculons le changement d’orientation \(d\theta\) du robot et les coordonnées du centre \(O\) du cercle de trajectoire

$$d \theta = \frac{d}{R} \\ \begin{cases} x_0 = x – R \cos{(\theta – \frac{\pi}{2})} \\ y_0 = y – R \sin{(\theta – \frac{\pi}{2})} \end{cases}$$

Nous pouvons mettre à jour la position du robot

$$ \begin{cases} \theta = \theta + d \theta \\  x = x_O + R \cos{(\theta – \frac{\pi}{2})} \\ y = y_O + R \sin{(\theta – \frac{\pi}{2})} \end{cases}$$

Localisation de Monte Carlo

La localisation de Monte Carlo, également connue sous le nom de filtre à particules, est un algorithme permettant aux robots de se localiser à l’aide d’un filtre à particules. Étant donné une carte de l’environnement, l’algorithme estime la position et l’orientation du robot au fur et à mesure qu’il se déplace et détecte l’environnement. L’algorithme utilise un filtre à particules pour représenter la distribution des états probables, c’est-à-dire, chaque particule représentant un état possible. L’algorithme commence généralement par une distribution aléatoire uniforme des particules dans l’espace de configuration, ce qui signifie que le robot ne dispose d’aucune information sur l’endroit où il se trouve et suppose qu’il a la même probabilité de se trouver en tout point de l’espace. Chaque fois que le robot détecte quelque chose, les particules sont rééchantillonnées sur la base d’une estimation bayésienne récursive, c’est-à-dire la corrélation entre les données réellement détectées à l’état prédit. Finalement, les particules doivent converger vers la position réelle du robot.

Les filtres particulaires sont initialisés par un nombre très élevé de particules couvrant l’ensemble de l’espace d’état. Au fur et à mesure que vous obtenez des mesures supplémentaires, vous prédisez et mettez à jour vos mesures, ce qui fait que votre robot a une distribution postérieure multimodale. Il s’agit d’une grande différence par rapport à un filtre de Kalman qui approxime votre distribution postérieure comme étant gaussienne. Après plusieurs itérations, les particules convergent vers une valeur unique dans l’espace d’état.

Filtre à particules en action

Les étapes suivies dans un filtre à particules sont :

  1. Ré-échantillonnage : tirer avec remplacement un échantillon aléatoire de l’ensemble d’échantillons selon la distribution (discrète) définie par les poids d’importance. Cet échantillon peut être considéré comme une instance de l’estimation
  2. Échantillonnage : utiliser l’estimation précédente et les informations de contrôle pour échantillonner la distribution qui décrit la dynamique du système. La croyance actuelle représente maintenant la densité donnée par le produit de la distribution et une instance de l’estimation précédente. Cette densité est la distribution utilisée dans l’étape suivante
  3. Échantillonnage par importance : Pondérer l’échantillon par le poids d’importance, la vraisemblance de l’échantillon \(X\) étant donné la mesure \(Z\).

Chaque itération de ces trois étapes génère un échantillon tiré de l’estimation postérieure. Après \(n\) itérations, les poids d’importance des échantillons sont normalisés pour que leur somme soit égale à 1.

Cartographie et localisation simultanées

Le SLAM (simultaneous localization and mapping, SLAM) consiste pour un robot à simultanément construire ou améliorer une carte de son environnement pour s’y localiser. Le SLAM permet de répondre à 2 questions.

  • À quoi ressemble l’environnement ? : la cartographie est la représentation de l’environnement et l’interprétation des données fournies par les capteurs dans une représentation donnée.
  • Où suis-je ? : la localisation est le problème de l’estimation de l’emplacement du robot par rapport à un plan

Le SLAM est donc défini comme le problème de la construction d’une carte ne même temps que la localisation du robot dans ce plan. Dans la pratique, ces deux problèmes ne peuvent être résolus de manière indépendante. Avant de pouvoir construire une carte de qualité de son environnement à partir d’un ensemble d’observations un robot a besoin de savoir à partir de quels endroits ces observations ont été faites. Dans le même temps, il est difficile d’estimer la position actuelle d’un véhicule sans carte. Le SLAM est souvent considéré comme la paradoxe de la poule et de l’œuf : une carte est nécessaire pour définir la localisation, la localisation est nécessaire pour construire une carte.

Un robot peut s’appuyer sur deux sources d’information : les informations qui lui sont propres et les informations collectées dans son environnement.

Quand il est en mouvement, un robot peut utiliser la navigation à l’estime et les informations renvoyées par ses capteurs (roues codeuses, consommation de courant des moteurs, dynamo tachymétrique, position d’un servomoteur…). Cependant, ce genre d’informations n’est pas complètement fiable (glissement, jeu, frottements…). L’autre source d’informations provient de capteurs et de systèmes dépendant de l’environnement et de sources extérieurs (boussole, accéléromètre, GPS, sonar, télémètre, caméra, microphone, lidar, laser…).

Source : CATIE Robotics

Navigation

La navigation d’un robot se divise en deux planificateur : le planificateur local et le planificateur global

Local planner

Le local planner fournit un contrôleur qui pilote une base mobile dans le plan. Ce contrôleur sert à connecteur le planificateur de trajectoire au robot. À l’aide d’une carte, le planificateur crée une trajectoire cinématique pour que le robot aille d’un point de départ à un point d’arrivée. Tout au long de cette trajectoire, le planificateur crée, au moins localement autour du robot, une fonction de valeur, représentée sous la forme d’une carte à grille. Cette fonction de valeur encode les coûts de traversée des cellules de la grille. Le travail du contrôleur consiste à utiliser cette fonction de valeur pour déterminer les vitesses \(dx\), \(dy\) et \(d \theta\) à envoyer au robot.

L’idée de base des algorithmes est la suivante :

  1. Échantillonnage discret dans l’espace de commande du robot.
  2. Pour chaque vitesse échantillonnée effectuer une simulation à partir de l’état actuel du robot pour prédire ce qui se passerait si la vitesse échantillonnée était appliquée pendant une courte période de temps
  3. Évaluer chaque trajectoire résultant de la simulation en utilisant une métrique qui incorpore des caractéristiques telles que : la proximité des obstacles, la proximité du but, la proximité de la trajectoire globale et la vitesse.
  4. Écarter les trajectoires illégales et choisir la trajectoire la mieux notée et envoyer la vitesse associée à la base mobile.
  5. Recommencer et répéter

Global planner

Le planificateur global s’occupe, en fonction de la carte à sa disposition, de planifier une trajectoire générale du robot. Ce planificateur utilise des algorithmes de pathfinding, les algorithmes sont multiples. Par exemple l’algorithme RRT (rapidly exploring random tree, RRT). La méthode RRT commence à un nœud défini par la position de départ du robot. Ensuite, l’arbre est généré à l’aide d’échantillons aléatoires (états du robot) qui sont connectés (s’ils sont valides) au nœud le plus proche (état du robot sans collision). Cela crée une structure graphique arborescente, où chaque nœud de l’arbre est connecté à un nœud parent unique et la racine de l’arbre se trouve à l’emplacement de départ. Lorsqu’un nœud de l’arbre correspond au nœud d’arrivée, un chemin est trouvé.

Exemple d’algorithme RRT*

Simplification du problème

Dans le cadre de ce cours nous allons très largement simplifier le problème pour se concentrer sur les objectifs du cours :

  1. Discrétisation du monde (la carte et le monde sont des matrices)
  2. Binarisation des obstacles (le robot peut être à la position \((x, y)\) ou ne peut pas y être)
  3. Suppression du planificateur local (le robot peut se déplacer dans toutes les directions quand il veut sans erreurs)
  4. Simulation d’un odométrie idéale (la position \((x, y)\) du robot est toujours connu)
  5. Omniscience du robot (le robot ne découvre rien dans l’environnement, il sait toujours tout)
  6. Réification des obstacles (le monde est statique sauf le robot)

À la fin nous obtenons une sorte de labyrinthe avec des obstacles, le départ se fait en haut à gauche et la sortie en bas à droite. L’objectif est de réussir à sortir du labyrinthe.

Problème que nous allons traiter après simplification

Modéliser le problème : Programmation Orientée Objet

La modélisation informatique des donnés est en réalité un processus de description de la structure, des associations, des relations et des impératifs liés à des données disponibles. Elle permet de fixer les normes, tout en codant des modèles de gestion de données dans une organisation.

En pratique, les avantages liés à une modélisation informatique sont multiples. En effet, l’utilisation d’un modèle de données permet de bien anticiper d’éventuels problèmes de ressources avant même qu’ils ne se manifestent, et d’optimiser les échanges et la compréhension entre les différents acteurs du projet.

Pour développer des applications qui traitent des données de manière performantes, nous allons avoir besoin d’une boîte à outils plus fournie que celle offerte par la programmation informatique classique ou la programmation fonctionnelle. En effet, lorsque nous voulons développer des applications qui combinent les exigences d’un processus métier particulier aux contraintes technologiques du traitement de données, nous avons besoin de concepts, d’outils et de méthodologies qui n’existent que dans le paradigme orienté objet.

Définition et origine du paradigme orienté objet

Le paradigme orientée objet (POO) est un modèle de programmation informatique qui met en œuvre une conception basée sur les objets. Elle se différencie de la programmation procédurale, qui est basée sur l’utilisation de procédures, et de la programmation fonctionnelle, qui elle, repose entièrement sur le concept de fonction.

L’effervescence des langages objet commence en 1980 et atteint son paroxysme dans les années 1990. Avant d’entre dans les caractéristiques de ces langages, il est bon de rappeler les principaux avantages du paradigme orienté objet :

  • La modularité : les objets forment des modules compacts regroupant des données et un ensemble d’opérations
  • L’abstraction : les objets de la POO sont proches de celles du monde réel. Les concepts utilisés sont donc proches des abstractions familières que nous exploitons
  • Productivité et ré-utilisabilité : plus l’application est complexe et plus l’approche POO est intéressante. Le niveau de ré-utilisabilité est supérieur à la programmation procédurale
  • Sûreté : l’encapsulation et le typage des classes offrent une certaine robustesse aux applications

On distingue plusieurs catégories de langage orienté objet, tout dépend du degré d’utilisation des objets et du niveau d’intégration du langage au paradigme orienté objet

  • Les langages dits de POO purs, où tout est traité comme un objet, depuis les primitives telles que les caractères et la ponctuation, jusqu’aux classes, prototypes, blocs, modules. Ils ont été conçus spécifiquement pour faciliter, voire imposer, les méthodes orientés objet. Ex : Ruby, Scala …
  • Les langages conçus principalement pour la POO, mais avec quelques éléments procéduraux. Ex : Java, Python, C++ …
  • Les langages qui sont historiquement des langages procéduraux, mais qui ont été étendus avec certaines caractéristiques orientées objets. Ex : PhP, Perl …

Les concepts fondamentaux de la programmation orientée objet

La programmation orientée objet repose sur 5 concepts fondamentaux : la classe, l’objet, l’encapsulation, l’héritage et le polymorphisme.

Le concept de classe

Le premier concept fondamental de l’orienté objet est la classe. Une classe est une structure abstraite qui décrit des objets du monde réel sous deux angles : ses propriétés (ses caractéristiques) et ses méthodes (les actions qu’elle peut effectuer ou son comportement).

Par exemple, la Classe Véhicule représente un véhicule, couleur est l’une de ses propriétés et accélérer/freiner sont deux de ses méthodes. La classe est finalement une sorte de moule, de modèle. Toutes les instances de classe s’appellent des objets. Les objets sont construits à partir de la classe, par un processus appelé instanciation. De ce fait, tout objet est une instance de classe.

Exemple de classe Voiture. La classe est une structure abstraite qui décrit un objet du monde réel sous 2 angles : ses propriétés et ses méthodes

Dans notre exemple ci-dessus couleur, poids et prix sont les attributs de classe Voiture et demarrer(), accelerer() sont ses méthodes. L’instanciation d’une classe fait appel à 3 méthodes spéciales dont la compréhension est importante :

  • Le constructeur
    • Le constructeur par défaut appelé par défaut lors de la création d’un objet (offert par défaut lors de la compilation s’il n’y a pas de constructeur déclaré)
    • Le constructeur par recopie a un unique argument du même type que l’objet à créer et il recopie les attributs depuis l’objet passé en argument sur l’objet à créer
    • Le constructeur paramétrique appelé si la signature correspond à celle du constructeur
  • Les accesseurs (get) et les mutateurs (set) : ces méthodes spéciales permettent d’appeler les propriétés et modifier les propriétés d’une classe depuis l’extérieur, un peu comme une API. C’est grâce à elles que l’extérieur peut “appeler” les fonctionnalités de la classe. Les accesseurs permettent de récupérer la valeur des propriétés d’une instance de classe depuis l’extérieur sans y accéder directement. Ce faisant, ils sécurisent l’attribut en restreignant sa modification. Les mutateurs quant à eux permettent de modifier la valeur des propriétés tout en vérifiant que la valeur que l’on veut donner à l’attribut respecte les contraintes sémantiques qui ont été imposées à la classe.
  • Le destructeur : est une méthode qui met fin à la vie d’une instance de classe. Il peut être appelé à la suppression de l’objet, explicitement ou implicitement.
#include <string>

class Voiture {
    
private:
    std::string _couleur;
    const double _poids;
    int _prix;
    
public:
    // Constructeur par paramètres
    Voiture(std::string couleur, double poids, int prix);
    // Constructeur par défaut
    Voiture();
    // Constructeur par copie
    Voiture(const Voiture &v);
    // Destructeur
    ~Voiture();
    
    // Accesseurs
    std::string getCouleur() const;
    double getPoids() const;
    int getPrix() const;
    
    // Mutateurs
    void setCouleur(std::string couleur);
    void setPrix(int prix);
    
    // Méthodes
    void demarrer();
    void accelerer();
};

L’identifiant d’une méthode est défini par sa signature. On appelle signature d’une méthode l’ensemble formé par son nom et la liste des types de ses arguments. Deux méthodes peuvent avoir le même nom si elles se distinguent par leurs signatures : c’est la surcharge de méthodes

Le concept d’objet

Le second concept le plus important en programmation objet, c’est l’objet. Techniquement un objet est caractérisé par 3 choses :

  • Une identité : l’identité doit permettre d’identifier sans ambiguïté l’objet (adresse / référence ou nom)
  • Des états : chaque objet a une valeur par défaut (lorsqu’elle est indiqué à l’instanciation) pour chacune de ses propriétés.
  • Des méthodes : chaque objet est capable d’exécuter les actions ou le comportement défini dans la classe. Ces actions sont traduites en POO concrètement sous forme de méthodes. Les actions possibles sur un objet sont déclenchées par des appels de ces méthodes ou par des messages envoyées par d’autres objets.
Un objet est une instance de classe. L’objet, à la différence de la classe qui est abstraite, est concret. Chaque objet a des états (valeur pour chaque propriété) et des méthodes (les actions de la classe)

Les objets ne sont pas des éléments statiques et leur durée de vie ne correspond pas forcément à la durée d’exécution du programme. La durée de vie d’un objet passe par trois étapes :

  1. la déclaration de l’objet et son instanciation
  2. l’utilisation de l’objet en appelant ses méthodes
  3. la suppression de l’objet, en appelant son destructeur ou en arrêtant la machine virtuelle qui exécute le programme,
// Allocation statique
Voiture maVoiture = Voiture(...);
// Allocation dynamique
Voiture* maVoiture = new Voiture(...);

Le concept d’encapsulation

Le troisième concept de la programmation orientée objet, c’est l’encapsulation. Les propriétés des objets ne peuvent être accédées que par ses méthodes. Ainsi, la classe encapsule à la fois les attributs et les méthodes qui permettent de manipuler les objets indépendamment de leurs états.

L’encapsulation permet de restreindre l’accès direct aux états et empêche la modification de l’objet hors de ses méthodes. Par exemple, si vous avez une classe Voiture et que vous voulez définir la valeur de sa propriété couleur à bleu, il vous faut passer par une méthode par exemple definirCouleur, implémentée par le développeur de la classe. Cette méthode peut restreindre les différentes valeurs de couleur.

Ainsi, l’encapsulation est un mécanisme qui empêche donc de modifier ou d’accéder aux objets par un autre moyen que les méthodes proposées, et de ce fait, permet de garantir l’intégrité des objets.

L’utilisateur d’une classe n’a pas forcément à savoir de quelle façon sont structurées les méthodes dans l’objet, ni le processus par lequel l’objet obtient tel ou tel état. En interdisant l’utilisateur de modifier directement les attributs, et en l’obligeant à utiliser les fonctions définies pour les modifier, on est capable de s’assurer de l’intégrité des objets. On pourra donc effectuer des contrôles sémantiques sur les données entrées par l’utilisateur.

L’encapsulation est comme un mécanisme de boîte noire qui empêche l’utilisateur d’utiliser un objet au-delà des méthodes qui lui sont proposées.

Dans le schéma précédent, la boîte noire masque les détails d’implémentation des attributs et des actions de la classe. Elle cache les attributs couleur, poids, prix. Le grand avantage de ce procédé est qu’en tant qu’utilisateur, on n’a plus à se préoccuper de comment est fait l’intérieur de l’objet de classe Voiture. On n’a plus besoin de se préoccuper sur le nombre d’attributs dans la classe Voiture. On se contente de connaître comment manipuler une voiture à l’aide des services offerts par la classe.

L’encapsulation permet de définir des niveaux de visibilité des éléments de la classe. Ces niveaux de visibilité définissent ce qu’on appelle la portée (ou encore le périmètre) de l’attribut/méthode. La portée est ainsi définie par méthode et par attribut et indique les droits à leur accès. Il existe trois niveaux de visibilité :

  • Publique (+) : les attributs publics sont accessibles à tous
  • Protégée (#) : les attributs protégés sont accessibles seulement dans la classe elle-même et aux classes dérivées.
  • Privée (-) : les attributs privés sont accessibles seulement par la classe elle-même

Le concept d’héritage

L’héritage est le quatrième concept clé de la programmation objet. C’est un concept en POO qui désigne le fait qu’une classe peut hériter des caractéristiques (attributs et méthodes) d’une autre classe.

Les objets de classes peuvent hériter des propriétés d’une classe parent. Par exemple on peut définir une classe Employé et une classe Manager qui est une classe spécialisée de Employé, qui hérite de ses propriétés.

Soient deux classes A et B

  • Relation d’héritage : Classe B « étend la  » Classe A
  • A est la superclasse ou classe mère/parent de B
  • B est la sous-classe ou classe fille de A
L’héritage permet de créer des classes spécialisées.

Dans l’exemple ci-dessus la classe Voiture et Avion sont des classes filles de la classe Véhicule. On peut les concevoir comme étant des classes spécialisées de la classe Véhicule. Ainsi tout objet de la classe Voiture ou Avion possédera les attributs et méthodes de la Classe Vehicule en plus de ses propres caractéristiques.

class Voiture : public Vehicule {
    ...
};

Une méthode dans une classe mère peut être redéfinie dans une classe fille : on parle de redéfinition. La nouvelle définition remplace celle héritée pour les objets de la classe dérivée. Le remplacement est effectif même quand l’objet de la classe fille est référencé par une variable typée par la super-classe (polymorphisme). Nous allons y revenir.

L’héritage présente 2 avantages principaux en POO :

  • La spécialisation : une nouvelle classe réutilise les attributs et les méthodes d’une classe en y ajoutant des opérations particulières à la nouvelle classe.
  • La réutilisation : pour chaque classe spécialisée, on n’a pas besoin de recréer à chaque fois la même classe.

Le concept de polymorphisme

Le dernier concept clé de la programmation orientée objet, c’est le polymorphisme. Un langage orienté objet est dit polymorphique, s’il offre la possibilité de percevoir un objet en tant qu’instance de différentes classes selon la situation. Java par exemple, est un langage  polymorphique. Nous allons expliquer ce concept avec des exemples concrets. Supposez le code C++ suivant :

class A {
public:
    void f() {
        ...
    }
};

class B : public A {
public:
    void k() {
        ...
    }
};

class Main{
public: 
    static void main(String [] args){  
        A a1 = new B(...); //upcasting
    }
};

En examinant le code attentivement, vous remarquerez qu’à  une  référence de type A,  on affecte une référence vers un objet de la classe B : on parle de surclassement ou upcasting.

A la compilation a1 est considéré comme un objet de classe A. Ses services sont alors réduits à celles proposées par la classe A.

Prenons un autre exemple.

class Main{
public:
    static void main(int argc, char *argv[]) {
        A a1 = new B(...);
        B b1 = (B) a1; // downcasting
    }
};

Dans le code ci-dessus  nous remarquons qu’à  une  référence de type B  on affecte une référence vers un objet de type A après une conversion : on parle de downcasting.

Le concept de classe abstraite

Le concept de classe abstraite ne fait pas partie des concepts clés de la POO, puisque c’est un type de classe.

En programmation orientée objet, une classe abstraite est une classe dont l’implémentation n’est pas complète et n’est pas instanciable. C’est une classe qui sert de base à d’autres classes dérivées (héritées). 

L’intérêt d’une classe abstraite est que l’on peut y placer toutes les fonctionnalités dont on souhaite disposer pour ses classes dérivées :

  • Soit sous forme d’une implémentation complète de méthodes et de champs dont héritera toute classe dérivée
  • soit alors sous forme d’interface de méthodes abstraites dont on est alors sûr qu’elles existeront dans toute classe dérivée instanciable.

Règles d’utilisation des classes abstraites :

  • Une classe est automatiquement abstraite si  une de ses méthodes est abstraite
  • Une classe abstraite n’est pas instaciable (on ne peut pas utiliser les constructeurs d’une classe abstraite et donc on ne peut pas créer d’objet ou d’instance de cette classe).
  • Une classe qui hérite d’une classe abstraite ne devient concrète que si elle implémente toutes les méthodes abstraites  de la classe dont elle hérite.
  • Une méthode abstraite n’est pas implémentée, mais doit être implémentée dans les sous-classes non abstraites.
  • Une classe abstraite peut contenir des méthodes non abstraites et des déclarations d’attributs ordinaires.
Une classe abstraite est une classe qui sert de base à la construction d’autres classes. A la différence de l’héritage classique, les classes abstraites qui servent de base à l’héritage ne peuvent pas être instanciées.

Le concept d’interface

L’interface, même s’il n’est pas un concept fondamental de l’orienté objet, reste tout de même très important. C’est pourquoi, tout comme les classes abstraites, nous estimons qu’il est indispensable que vous vous familiarisez avec le concept.

Une interface est un ensemble de signatures de méthodes, qui sont par essence abstraite et publiques/constantes.

Les constantes d’une interface sont accessibles à toutes les classes implémentant l’interface.

Une interface ne permet pas d’instancier des objets, mais on peut définir des variables de type interface, qui peuvent référencer des objets d’une classe implémentant une interface.

Exercices

Exercice 1

Modéliser la situation suivante. Deux animaux existent : les chiens et les chats. Les chiens comme les chats mangent et parlent. Le chat miaule alors que le chien aboie.

Bonus : les animaux possèdent des pattes qui ont un nombre de griffes et un nombre de coussinets.

Exercice 2

Une classe Véhicule a été caractérisé par les propriétés suivantes : Numéro de véhicule, date de fabrication du véhicule, pavillon du bateau, nombre de réacteurs, superficie des ailes, puissance fiscale, haut du mat, nombre de torpilles

Quel est le problème de cette classe ?

Permanent link to this article: https://www.eirlab.net/2021/11/20/recherche-de-chemin-a-travers-lalgorithme-a-en-c-1-4-introduction-du-probleme-concept-de-modelisation-informatique-et-initiation-a-la-programmation-orientee-objet/