Encore une fois recherche opérationnelle ou simplement les algo de résolution de problème NP-complet. aptitude n'a pas besoin d'IA pour résoudre un SAT-3.
Les problèmes de dépendances ne sont pas forcément les problèmes les plus compliqués qu’on puisse générer avec SAT donc ils ne nécessitent pas forcément de mettre en œuvre les algorithmes les plus malins pour résoudre les formules. Faudrait mettre aptitude sur les problèmes de https://satcompetition.github.io/2023/ pour voir comment il s’en sort ! Dans mon souvenir son solveur s’en sortait pas bien déjà dans certains cas de résolution de dépendance dans le temps. L’opposition avec la recherche opérationnelle, je dirai que ça a pas spécialement de sens vu qu’il n’y a aucun obstacle a utiliser des méthodes d’IA en RO. Il faut chercher la définition ailleurs.
Un des trucs que perso j’utiliserai pour caractériser une IA, c’est qu’elle a besoin de mémoire pour se faire "sa propre" représentation du problème, non établie à l’avance. Par exemple un robot qui doit agir dans un environnement peut avoir à se fabriquer un plan interne de cet environnement, un modèle, il a besoin de mémoire pour ça. Ensuite si on lui fait effectuer un parcours dans cet environnement il pourra l’utiliser pour planifier ce parcours, et prévoir des éventuelles difficultés le cas échéant ...
Une IA doit être capable de résoudre un problème qu’on peut considérer comme non trivial sans avoir été spécifiquement conçue pour résoudre ce problème.
Par extension, vu qu’on peut exprimer n’importe quel problème NP-complet sous la forme de SAT, mais qu’il n’est pas évident qu’un algorithme générique de SAT soit bon pour résoudre les instances spécifiques générées pour résoudre un autre problème, un solveur SAT "intelligent" devrait être capable d’exploiter la structure spécifique générée par ce problème sans qu’on la lui ait expliqué ou conçu pour. Donc, plus que "générer un algorithme"
On ne veut pas détailler l'algorithme donc on tente de le générer.
Ou alors c’est trop pénible de détailler l’algorithme donc on tente de généraliser en en concevant un qui permettra de résoudre ce problème et aussi une vaste classe de problème similaires au lieu de juste "reconnaître super bien une vache". Après oui, il faut que le résultat soit "opérationnel", en ce sens on peut parler d’algorithme. Ton histoire me fait un peu penser à l’extraction de programme en preuve automatique de théorème : https://www.fing.edu.uy/~amiquel/publis/hdr.pdf une fois qu’on a démontré un théorème on peut, mais c’est pas nécessairement obligé je crois, ça dépend des système de preuve (il faut que ce soit "constructif", en extraire un programme qui pourrait résoudre des problèmes correspondant au théorème. Mais je suis pas certain que dans le cas général de l’IA, ce soit vraiment nécessaire d’extraire un algorithme spécifique de la procédure de résolution. Notamment parce qu’en imaginant un processus évolutif ce soit potentiellement plus efficace d’être dynamique et de suivre un certain algorithme dans certains cas, genre au début de procédure, mais de réagir à certains autre moment ou cet "algorithme" montre son inefficacité et de faire évoluer la procédure vers autre chose.
[^] # Re: Simulation
Posté par thoasm . En réponse au journal Une simulation de drone de combat qui tourne mal. Évalué à 4.
Les problèmes de dépendances ne sont pas forcément les problèmes les plus compliqués qu’on puisse générer avec SAT donc ils ne nécessitent pas forcément de mettre en œuvre les algorithmes les plus malins pour résoudre les formules. Faudrait mettre aptitude sur les problèmes de https://satcompetition.github.io/2023/ pour voir comment il s’en sort ! Dans mon souvenir son solveur s’en sortait pas bien déjà dans certains cas de résolution de dépendance dans le temps. L’opposition avec la recherche opérationnelle, je dirai que ça a pas spécialement de sens vu qu’il n’y a aucun obstacle a utiliser des méthodes d’IA en RO. Il faut chercher la définition ailleurs.
Un des trucs que perso j’utiliserai pour caractériser une IA, c’est qu’elle a besoin de mémoire pour se faire "sa propre" représentation du problème, non établie à l’avance. Par exemple un robot qui doit agir dans un environnement peut avoir à se fabriquer un plan interne de cet environnement, un modèle, il a besoin de mémoire pour ça. Ensuite si on lui fait effectuer un parcours dans cet environnement il pourra l’utiliser pour planifier ce parcours, et prévoir des éventuelles difficultés le cas échéant ...
Une IA doit être capable de résoudre un problème qu’on peut considérer comme non trivial sans avoir été spécifiquement conçue pour résoudre ce problème.
Par extension, vu qu’on peut exprimer n’importe quel problème NP-complet sous la forme de SAT, mais qu’il n’est pas évident qu’un algorithme générique de SAT soit bon pour résoudre les instances spécifiques générées pour résoudre un autre problème, un solveur SAT "intelligent" devrait être capable d’exploiter la structure spécifique générée par ce problème sans qu’on la lui ait expliqué ou conçu pour. Donc, plus que "générer un algorithme"
Ou alors c’est trop pénible de détailler l’algorithme donc on tente de généraliser en en concevant un qui permettra de résoudre ce problème et aussi une vaste classe de problème similaires au lieu de juste "reconnaître super bien une vache". Après oui, il faut que le résultat soit "opérationnel", en ce sens on peut parler d’algorithme. Ton histoire me fait un peu penser à l’extraction de programme en preuve automatique de théorème : https://www.fing.edu.uy/~amiquel/publis/hdr.pdf une fois qu’on a démontré un théorème on peut, mais c’est pas nécessairement obligé je crois, ça dépend des système de preuve (il faut que ce soit "constructif", en extraire un programme qui pourrait résoudre des problèmes correspondant au théorème. Mais je suis pas certain que dans le cas général de l’IA, ce soit vraiment nécessaire d’extraire un algorithme spécifique de la procédure de résolution. Notamment parce qu’en imaginant un processus évolutif ce soit potentiellement plus efficace d’être dynamique et de suivre un certain algorithme dans certains cas, genre au début de procédure, mais de réagir à certains autre moment ou cet "algorithme" montre son inefficacité et de faire évoluer la procédure vers autre chose.