La recherche

This page is also available in english.

"I consider the most important trend was that computers got considerably faster in these last 50 years. In this process, we found that many things for which we had at best anthropomorphic solutions, which in many cases failed to capture the real gist of a human's method, could be done by more brute-forcish methods that merely enumerated until a satisfactory solution was found. If this is heresy, so be it."
Hans Berliner

Optimization can be likened to a kangaroo searching for the top of Mt. Everest. Everest is the global optimum, but the top of any other really high mountain such as K2 would be nearly as good.
The initial point is usually chosen randomly, which means that the kangaroo may start out anywhere in Asia. If you know something about the problem, you may be able to get the kangaroo to start near the Himalayas. However, if you make a really stupid choice, or if you have really bad luck, the kangaroo may start in South America.
With Newton-type algorithms, the Himalayas are covered with a dense fog, and the kangaroo can only see a little way around his location. Judging from the local terrain, the kangaroo make a guess about where the top of the mountain is, and tries to jump all the way there. In a stabilized Newton algorithm, the kangaroo has an altimeter, and if the jump takes him to a lower point, he backs up to where he was and takes a shorter jump. If the algorithm isn't stabilized, the kangaroo may mistakenly jump to Shanghai and get served for dinner in a Chinese restaurant.
In steepest ascent with line search, the fog is very dense, and the kangaroo can only tell which direction leads up. The kangaroo hops in this direction until the terrain starts going down again, then chooses another direction.
In standard neural nets backprop or stochastic approximation, the kangaroo is blind and has to feel around on the ground to make a guess about which way is up. He may be fooled by rough terrain unless you use batch training. If the kangaroo ever gets near the peak, he may jump back and forth across the peak without ever landing on the peak. If you use a decaying step size, the kangaroo gets tired and makes smaller and smaller hops, so if he ever gets near the peak he has a better chance of actually landing on it before the Himalayas erode away. In backprop with momentum, the kangaroo has poor traction and can't make sharp turns.
Notice that in all the methods discussed so far, the kangaroo can hope at best to find the top of a mountain close to where he starts. There's no guarantee that this mountain will be Everest, or even a very high mountain. Various methods are used to try to find the actual global optimum.
In simulated annealing, the kangaroo is drunk and hops around randomly for a long time. However, he gradually sobers up and tends to hop up hill.
In genetic algorithms, there are lots of kangaroos that are parachuted into the Himalayas (if the pilot didn't get lost) at random places. These kangaroos do not know that they are supposed to be looking for the top of Mt. Everest. However, every few years, you shoot the kangaroos at low altitudes and hope the ones that are left will be fruitful and multiply.
D'après Warren Sarle, posté dans le groupe usenet comp.ai.neural.nets le 27 septembre 1993

Livres publiés

J'ai écrit ou participé à l'édition de trois livres.

Le premier, "Intelligence Artificielle et Informatique théorique", a connu deux versions, en 1993 et 2002. La seconde édition peut toujours être acheté en ligne sur amazon. Pour plus d'information, voir ma page consacré à l'enseignement.

En 1994, j'ai édité les proceedings de la première conférence francophone sur les algorithmes évolutionnaires. Le livre a été publié chez Cepadues (ISBN 2-85428-411-9), et co-édité avec mes amis Marc Schoenauer et Evelyne Lutton. Il est, à ma connaissance, épuisé.

En 1995, la conférence "Evolution Artificielle" avait changé de standing, elle était devenu une conférence européenne et les proceedings dont j'étais également un des éditeurs ont été publiés chez Springer-Verlag. Le livre peut toujours être commandé sur le site de Springer.

Thèmes scientifiques de recherche

J'ai travaillé sur cinq thèmes au cours de ma "carrière" de chercheur.

• En 1986, j'ai fait mon stage de fin d'études à l'X au Lactamme chez Jean-François Colonna. J'ai essentiellement travaillé sur les objets fractaux, dont les ensembles de Mandelbrot. Cette partie est décrite plus en détail sur la page qui lui est consacrée.
• De 1987 à 1992 (mon DEA et mon doctorat), j'ai travaillé sur la résolution automatique dans les logiques non classiques au sein de l'équipe de Luis Farinas à l'IRIT. Une page est consacrée aux logiques non classiques et on peut lire ma thèse pour plus d'informations. C'est aussi une époque où je me suis pas mal intéressé à la philosophie des sciences (à découvrir sur cette page).
• De 1992 à 2013, j'ai travaillé sur les algorithmes d'optimisation globale et les réseaux de neurones. Une page est consacrée aux algorithmes évolutionnaires et une autre page est consacrée aux réseaux de neurones. On peut également lire ma thèse d'habilitation (1996).
  J'ai également travaillé sur les algorithmes d'optimisation utilisant la programmation par intervalle et le branch and bound. On trouvera une description rapide de ces techniques dans le support de cours que j'y consacre. J'ai été non publiant de 2009 à 2012 lorsque j'étais chef du département Recherche et Développement à la DSNA.
• Après mon retour à l'IRIT, je me suis essentiellement ré-investi dans les problèmes liant informatique et biologie, d'abord dans le cadre du projet GBDS, puis en collaboration avec le laboratoire AMIS dans le cadre d'une thèse sur la philogénie chez les primates. Je suis également revenu à mes premières amours scientifiques (la logique), et je m'intéresse ainsi à la modélisation logique des systèmes biologiques, sous le "tutorat" de mon ancien directeur de thèse Luis Farinas, en collaboration avec le Centre de Recherche en Cancérologie de Toulouse.
  Je suis également co-resp. du Labex CIMI depuis 2014.
• Enfin, une forme de fil rouge a été quelques travaux sur la programmation des jeux, avec un programme d'Othello (OTAGE) qui utilisait des techniques d'auto-apprentissage et de "reconnaissance" de formes au milieu des années 90, ainsi que quelques travaux sur l'optimisation des fonctions d'évaluation par des algorithmes stochastiques. Plus récemment, j'ai publié une étude du jeu "Le compte est bon", ainsi qu'un travail sur l'évaluation objective des joueurs d'échecs.

Si vous voulez en savoir encore plus sur ma carrière, mon long CV pourrait vous intéresser...

Thèmes applicatifs

Pendant mes années à la DSNA, toute notre équipe s'est consacrée principalement à l'application des techniques d'optimisation globale aux problèmes de gestion du trafic aérien. Le lecteur intéressé trouvera ci-dessous la liste de mes publications, dont la majorité est consacrée à ce sujet.

Ici, on peut voir l'utilisation de ce type d'algorithmes pour l'optimisation du roulage des aéronefs au sol à Roissy Charles de Gaulle.

Les gens qui s'intéressent à cette grande époque, aujourd'hui défunte avec la fermeture du CENA puis du département Recherche et Développement de la DSNA, peuvent jeter un coup d'oeil sur la page des amis du CENA, avec quelques textes explicatifs et l'ensemble des publications encore disponibles.

Publications

Attention, cette partie n'est plus maintenue depuis 2014. La meilleure solution pour trouver mes dernières publis est de se reporter à la page associée sur ResearchGate, qui est plus ou moins à jour, et plus ou moins exacte...

On ne trouvera ici que (a) les publications dont j'ai conservé les sources, et (b) uniquement les "full papers". Il n'y a ni posters, ni short papers.

• Certified Global Minima for a Benchmark of Difficult Optimization Problems , Charlie Vanaret, Jean-Baptiste Gotteland, Nicolas Durand and Jean-Marc Alliot, Submitted to Gecco 2014 , 2014 .
  We provide the global optimization community with new optimality proofs for 6 deceptive benchmark functions (5 bound-constrained functions and one nonlinearly constrained problem). These highly multimodal nonlinear test problems are among the most challenging benchmark functions for global optimization solvers; some have not been solved even with approximate methods. The global optima that we report have been numerically certied using Charibde (Vanaret et al., 2013), a hybrid algorithm that combines an Evolutionary Algorithm and interval-based methods. While metaheuristics generally solve large problems and provide sufficiently good solutions with limited computation capacity, exact methods are deemed unsuitable for difficult multimodal optimization problems. The achievement of new optimality results by Charibde demonstrates that reconciling stochastic algorithms and numerical analysis methods is a step forward into handling problems that were up to now considered unsolvable. We also provide a comparison with state-of-the-art solvers based on mathematical programming methods and populationbased metaheuristics, and show that Charibde, in addition to being reliable, is highly competitive with the best solvers on the given test functions.
• Wind Mill Pattern Optimization using Evolutionary Algorithms , Charlie Vanaret, Nicolas Durand and Jean-Marc Alliot, Submitted to Gecco 2014 , 2013 .
  When designing a wind farm layout, we can reduce the number of variables by optimizing a pattern instead of considering the position of each turbine. In this paper we show that when reducing the problem to only two variables defining a grid, we can gain up to 3% of energy output on simple examples of wind farms dealing with many turbines (up to 1000) while dramatically reducing computation time. To achieve these results, we compared both a genetic algorithm and a diferential evolution algorithm to previous results from the literature. These preliminary results should be extended to examples involving non-rectangular farm layouts and wind distributions that may require pattern deformation variables in order to increase solution diversity.
• A Fast and Reliable Hybrid Algorithm for Numerical Nonlinear Global Optimization , Charlie Vanaret, Jean-Baptiste Gotteland, Nicolas Durand and Jean-Marc Alliot, Submitted to the 2013 onference of the Association for the Advancement of Artificial Intelligence , 2013 .
  Highly nonlinear and ill-conditioned numerical optimization problems take their toll on the convergence of existing resolution methods. Stochastic methods such as Evolutionary Algorithms carry out an efficient exploration of the search-space at low cost, but get often trapped in local minima and do not prove the optimality of the solution. Deterministic methods such as Interval Branch and Bound algorithms guarantee bounds on the solution, yet struggle to converge within a reasonable time on high-dimensional problems. The contribution of this paper is a hybrid algorithm in which a Differential Evolution algorithm and an Interval Branch and Contract algorithm cooperate. Bounds and solutions are exchanged through shared memory to accelerate the proof of optimality. It prevents premature convergence toward local optima and outperforms both deterministic and stochastic existing approaches. We demonstrate the efficiency of this algorithm on two currently unsolved problems: first by presenting new certified optimal results for the Michalewicz function for up to $75$ dimensions and then by proving that the putative minimum of Lennard-Jones clusters of 5 atoms is optimal.
• Implementing an interval computation library for OCaml on x86/amd64 architectures, Jean-Marc Alliot, Nicolas Durand, David Gianazza, Jean-Baptiste Gotteland, International Conference on Functional Programming (ICFP 2012), Ocaml Users and Developpers Workshop (OUD) , 2012/09/10 .
  Interval arithmetic has been used in computer science and numerical computations for years. Its main goal was to create computing environments where the exact value of a computed result lies with certainty within an interval, which might be paramount for some critical applications.
  In this paper we present two implementations of interval arithmetics for Ocaml, one based on the existing MPFI library, and a much faster native implementation written in assembly language.
• Finding and Proving the Optimum: Cooperative Stochastic and Deterministic Search , Jean-Marc Alliot, Nicolas Durand, David Gianazza, Jean-Baptiste Gotteland, European Conference on Artificial Intelligence , 2012/08/27 .
  In this article, we introduce a global cooperative approach between an Interval Branch and Bound Algorithm and an Evolutionary Algorithm, that takes advantage of both methods to optimize a function for which an inclusion function can be expressed. The Branch and Bound algorithm deletes whole blocks of the search space whereas the Evolutionary Algorithm looks for the optimum in the remaining space and sends to the IBBA the best evaluation found in order to improve its bound. The two algorithms run independently and update common information through shared memory.
  The cooperative algorithm prevents premature and local convergence of the evolutionary algorithm, while speeding up the convergence of the branch and bound algorithm. Moreover, the result found is the proved global optimum.
• Optimisation locale/globale, déterministe/stochastique et applications aux problèmes du trafic aérien disponible en version ppsx (avec gif animés) ou en version pdf (sans gif animés), Jean-Marc Alliot , Séminaire CPGE tenu à l'ISAE (Sup Aéro), 2011/05/19 .
  Présentation de différentes formes d'optimisation (locale et globale, déterministe et stochastique): méthode de la dérivée, du gradient, de Newton, BFGS, simplexe de Nelder-Mead, méthode de Branch and Bound couplée avec l'arithmétique d'intervalles et méthodes évolutionnaires (programmation génétique, algorithmes génétiques). Application aux problèmes du trafic aérien.
• Nouvelles technologies pour l'Air Traffic et l'Airspace Management , Jean-Marc Alliot , 4ème édition des entretiens de Toulouse , 2011/05/03 .
  Les systèmes de contrôle et de gestion de l'espace aérien ont connu une évolution relativement lente au cours des vingt dernières années. Depuis 50 ans l'informatique a été introduite dans ces systèmes. Dès 1980, les traitements "plan de vol", la poursuite multi-radar, l'image radar renseignée, le digitatron, le filet anticollision, etc. existaient dans le système français.
  Mais les possibilités offertes par l'explosion de la puissance informatique au cours des 30 dernières années sont loin d'avoir été complètement exploitées. Le projet SESAR tente aujourd'hui d'unifier au niveau européen les différentes pistes, mais son horizon d'application le limite majoritairement à des concepts déjà éprouvés, même si le Work Package E s'intéresse également à l'horizon 2020+.
  Dans cet Entretien, nous explorerons certaines des pistes qui pourraient être suivies dans les années à venir afin de mieux tirer parti des formidables capacités des calculateurs modernes, que ce soit en terme de représentation (puissance des nouvelles cartes graphiques), de saisie de l'information (nouvelles IHM tactiles), ou de puissance de calcul (algorithmes d'optimisation de routage, ou de détection et résolution de conflit).
• A mathematical analysis of the influence of wind uncertainty on MTCD efficiency , Jean-Marc Alliot, Nicolas Durand , Revue de l'IFATCA ("The controller") , 2011/03/01 .
  A large part of the controller's workload comes from conflict detection and monitoring. The SESAR project aims at giving tools (such as MTCD) to air traffic controller that will lighten this part of their burden and help them to have a more strategic planning activity while letting the computer take into account some of those housekeeping tasks.
  In this article we explain how the conflict detection task can be analyzed mathematically, and what can be learned from this theoretical study. We will also show that, whatever the quality of MTCD tools, because some uncertainties like wind prediction errors are unavoidable, even a perfect MTCD will always detect more conflict that the actual number of conflicts that really occur. A short version is available here.
• Un algorithme de colonie de fourmis pour résoudre des conflits aériens , Nicolas Durand and Jean-Marc Alliot , ROADEF, Toulouse , 2010/02/26 .
  Le problème de résolution de conflits aériens en croisière est un problème très combinatoire impossible à résoudre avec des algorithmes d'optimisation classiques dans un contexte réaliste : d'une part l'évaluation d'une solution ne peut se faire que par une simulation prenant en compte des modèles de prévision de trajectoires complexes ; d'autre part, les variables en jeu sont en général discrètes et leur nombre peut être très élevé. La littérature ne propose que deux approches efficaces pour résoudre de façon centralisée des problèmes de grande taille (plus d'une vingtaine d'avions). L'une utilise la programmation linéaire mixte, mais requiert des hypothèses fortes sur les trajectoires (vitesses constantes, manoeuvres exécutées en même temps). L'approche par algorithme évolutionnaire est plus ancienne et le présent article propose, toujours dans le domaine des métaheuristiques, un algorithme de colonie de fourmis adapté à un problème de résolution de conflits de grande taille.
• Ant Colony Optimization for Air Traffic Conflict Resolution , Nicolas Durand, Jean-Marc Alliot , 8th USA/Europe Air Traffic Management Research and Developpment Seminar , 2009/06/29 .
  The n aircraft conflict resolution problem is highly combinatorial and can be optimally solved using classical mathematical optimisation techniques only for small problems involving less than 5 aircraft. This article applies an Ant Colony Optimization (ACO) algorithm in order to solve large problems involving up to 30 aircraft. In order to limit the number of pheromone trails to update, a $n$ aircraft conflict resolution problem is not modeled by a single ant but by a bunch of $n$ ants choosing their trajectories independantly. A relaxation process is also used in order to be able to handle difficult conflicts for which partial solutions can help finding a path toward the optimal solution. Two different sizes of a toy problem are solved and presented.
• Optimisation par fusion et fission. Application au problème du découpage aérien européen. , Charles-Edmond Bichot, Jean-Marc Alliot, Nicolas Durand, Pascal Brisset , Journal Européen des Systèmes Automatisés, September-October 2004, vol 38, pp 1141-1173 , 2005/10/05 .
  This article presents a new optimization process based on an analogy with nuclear fusion and fission. Originally, this process was intended to resolve an air traffic problem. But through this problem, this process allows to resolve other NP-hard problems. This process is quite new so it is still now difficult to implement. The main idea of this process is to make fusion and fission between "atoms". Atoms are sets of nucleons. Let us consider each nucleon as an unbreakable unit of the problem. Matter who is filled with atoms will be reorganized by the process into more stabilized states. Nous allons présenter dans cet article une nouvelle méthode d'optimisation inspirée de la fusion et de la fission nucléaires. A l'origine, cette méthode a été créée pour résoudre un problème de trafic aérien. Mais elle vise à travers ce problème à résoudre des problèmes plus généraux d'optimisation de la classe NP-difficile. Cette méthode n'en est qu'à ses débuts et est donc encore assez difficile à mettre en oeuvre. L'idée maîtresse de cette méthode est de faire des fusions ou des fissions entre des « atomes ». Ceux-ci sont des ensembles de nucléons, chaque nucléon étant une unité indivisible du problème. L'algorithme va réorganiser la « matière » constituée par les atomes pour atteindre un état plus stable.
• A theoretical approach to defining the European core area , Charles-Edmond Bichot, Jean-Marc Alliot , , 2005/06/28 .
  European studies using air traffic flow are usually restricted to a limited area. This limited area is the area which have the highest volume of traffic in Europe. But limited areas are seldom the same in the different studies. This paper presents three different limited areas validate by a theorical approach. This approach is based on fluid mechanics and in particular Reynolds numbers. This different limited areas correspond to three different types of studies, the core area who is a set of sectors - a sector is a geographical area controlled by an air traffic controller - the country core area who is a set of country and the Air Traffic Control Complexity Area Border who is a set of air traffic control centers.
• Optimisation par colonies de fourmis appliqué au découpage de l'espace aérien européen en zones de qualification. , Charles-Edmond Bichot, Jean-Marc Alliot , RIVF2005 , 2005/02/22 .
  L'espace aérien est décomposé en secteurs géographiques élémentaires nommés secteurs de contrôle. Ces secteurs sont regroupés en zones de qualifications sur lesquels les contrôleurs aériens sont qualifiés à exercer leur métier. Pour accroître la sécurité du transport aérien, nous étudions un redécoupage du ciel européen en zones de qualifications. Le but de cet article est de présenter la méthode d'optimisation par colonies de fourmis et son application au problème du découpage de l'espace aérien. Nous introduirons aussi la percolation qui nous servira en tant que méthode d'initialisation des colonies de fourmis, et nous comparerons les résultats obtenus par ces méthodes avec ceux obtenus par une métaheuristique de référence, le recuit simulé.
• ATM: 20 ans d'effort et perspectives , Jean-Marc Alliot, Dominique Colin de Verdiere , Symposium de l'Academie Nationale de l'Air et de l'Espace: vers l'automatisation du vol et sa gestion , 2003/11/23 .
  Le systeme de gestion de la circulation aerienne est un systeme complexe par bien des aspects: il comporte un grand nombre d'agents humains et techniques, il doit pouvoir traiter des aeronefs ayant des performances et des equipements varies; c'est un systeme ouvert dont l'arret rapide dans un etat securitaire est impossible. Depuis 40 ans l'informatique a ete introduite dans la gestion de la circulation aerienne. L'automatisation a porte sur le traitement plan de vol et radar pour distribuer l'information pertinente aux controleurs sur les secteurs et faciliter les transferts des vols entre secteurs. Dans les 10 prochaines annees des outils d'assistance au controleur et au pilote permettront d'augmenter la securite et la capacite dans une mesure que l'on ne sait pas evaluer. L'automatisation plus poussee a fait l'objet de nombreux projets de recherche (Aera aux USA, Arc2000 a Eurocontrol, Phare,...) L'evolution de l'ATM et de son automatisation sont indissociables. Deux scenarios nous semblent aujourd'hui envisageables: l'un deterministe centralise base sur une gestion des trajectoires 4D destines a des espaces encombres et aux compagniees aeriennes cherchant l'optimisation des vols etr la ponctualite; l'autre base sur l'avion autonome pour des espaces peu denses et l'aviation generale Cette evolution se fera par petites etapes en prenant en compte les opportunites de developpement. La question de la planification de ces evolutions est posee: peut-on definir a priori la voie du changement?
• Handling CFMU slots in busy airports , Jean-Baptiste Gotteland, Nicolas Durand, Jean-Marc Alliot , ATM2003 , 2003/06/22 .
  In busy airports, too many departing flights take off out of the time slot required by the Central Flow Management Unit (CFMU). During ground traffic peaks, taxi out times and runway queuing delays increase, and it seems very hard and maybe unfeasible for ground controllers to organise properly the traffic so that aircraft take off at their scheduled time. In a first part, this paper shows how a ground traffic simulator that includes a conflict resolution module can give accurate predictions of takeoff times. Then, different strategies taking into account these predictions so as to incorporate CFMU slot constraints are compared. The deviation between the required slots and the final takeoff times is measured. The efficiency of the different strategies is compared by the correlation between the number of aircraft and the generated delay.
• Optimization of Air Traffic Control sector configurations using tree search methods and genetic algorithms , David Gianazza, Jean-Marc Alliot , Digital Avionics Systems Conference 2002 , 2002/10/01 .
  This paper introduces several algorithms which build optimal configurations of Air Traffic Control sectors, taking into account traffic prediction, sector capacities and the number of available control positions. The optimal ACC schedule is compared to the filed schedule.
• Optimal combinations of Air Traffic Control sectors using classical and stochastic methods , David Gianazza, Jean-Marc Alliot , The 2002 International Conference on Artificial Intelligence IC-AI'02, Las Vegas , 2002/06/24 .
  This paper introduces several algorithms which build optimal configurations of Air Traffic Control sectors, taking into account traffic prediction, sector capacities and the number of available control positions.
• Arithmetic simulation and performance metrics , Jean-Marc Alliot, Geraud Granger, Jean-Marc Pomeret , Digital Avionics System conference 2002 and Technical Interchange Meeting on Performance 2002 , 2002/05/15 .
  Performance metrics are becoming a strategic issue, and they are getting more and more attention. However, defining such metrics is a difficult problem. In this paper, we show how arithmetic simulations can be used to give performance informations. We also point out that many different metrics can be defined, each of them giving different results regarding efficiency. We conclude that an extreme caution must be applied when interpreting results.
• Token allocation strategy for free-flight conflict solving , Geraud Granger, Nicolas Durand, Jean-Marc Alliot , IJCAI'01 , 2001/08/01 .
  For the last 10 years, airlines have widely supported research on the development of airspaces where aircraft would be free to decide their trajectory: these areas where called Free-flight airspaces. However, as soon as two aircraft are in the same area, their separation must be guaranteed. FACES (Free flight Autonomous and Coordinated Embarked Solver) is an autonomous and coordinated embarked (on board) conflict solver for Free Flight airspace. It solves conflict by computing simple manoeuvres that guarantees conflict free trajectories for the next 5 minutes (min). Coordination is ensured by giving sequential manoeuvres to aircraft with a token allocation strategy. FACES can be implemented with the current positioning, broadcasting and flight management technology. Moreover, it is robust to communication or system failure for time up to one or two minutes. FACES was tested with a traffic simulator on busy traffic days over France. Airspace over flight level 320 was considered as Free Flight.
• A statistical analysis of the influence of vertical and ground speed errors on conflict probe , Jean-Marc Alliot and Nicolas Durand and Geraud Granger , ATM 2001 , 2001/07/01 .
  Conflict probes will be important components of air traffic control tools in the next years. They appear in almost every project (CINCAT, ERATO, HIPS, PHARE, and so on). To be useful, they have to fulfill two goals : reliability (they have to detect all conflicts) and efficiency (they must minimize the number of false alarms). Conflict probes rely on trajectory prediction, and their reliability and efficiency highly depend on the accuracy of trajectory prediction. In this paper, we present a quick mathematical insight of the influence of ground speed errors on trajectory prediction, results of arithmetic simulations on real traffic both on ground and vertical speed errors, and a statistical analysis of these results to model the influence of vertical and ground speed errors on conflict probe.
• Aircraft Ground Traffic Optimization , Jean-Baptiste Gotteland, Nicolas Durand, Jean-Marc Alliot, Erwan Page , ATM2001 , 2001/07/01 .
  Air traffic growth and especially hubs development cause new significant congestion and ground delays on major airports. Accurate models of airport traffic prediction can provide new tools to assist gr ound controllers in choosing the best taxiways and the most adapted holding points for aircraft. Such tools could also be used by airport designers to evaluate possible improvements on airport configurations and airpor t structure. In this paper, a ground traffic simulation tool is proposed and applied to Roissy Charles De Gaulle and Orly airports. A global optimization method using genetic algorithms is compared to a 1-to-n strategy to minimize time spent between gate and runway, while respecting aircraft separation and runway capacity. In order to compare the efficiency of the different optimization methods, simulations are carried out on a one day traffic sample, and ground delay due to holding points or taxiway lengthening is correlated to the traffic density on the airport.
• Optimal resolution of en route conflicts , Geraud Granger and Nicolas Durand and Jean-Marc Alliot , ATM 2001 , 2001/07/01 .
  Designing a Control Simulator involves many difficult problems: modeling conflict detection, trajectory uncertainties, solving conflict inside sectors, respecting military areas constraints, coordinating aircraft between sectors, etc\ldots Moreover, the n-aircraft conflict resolution problem is highly combinatorial and cannot be optimally solved using classical mathematical optimization techniques. The set of admissible solutions is made of many unconnected subsets enclosing different local optima, but the subset enclosing the optimum cannot be found a priori. In this paper, we present a conflict solver and its implementation in an Air Traffic simulator, with statistical results on real traffic in a French Sector. This solver, which takes into account real flight plans, solves every conflict inside a sector or over the French airspace on a loaded day.
• Aircraft Ground Traffic Optimisation using a Genetic Algorithm , Brankica Pesic and Nicolas Durand and Jean-Marc Alliot , GECCO 2001 , 2001/05/01 .
  The development of air traffic during the last years, has greatly increased the density of aircraft in the airspace, and congestion on major airports. Indeed, on many airports, the taxi operation of aircraft between parking positions and runways, causes delays. The problem is increased by the development of hubs. In this article, a taxi optimisation tool using a Genetic Algorithm is introduced and tested on Roissy Charles De Gaulle Airport. The tool can help choosing the best taxiways to reduce the time spent from the gate to the runway or the runway to the gate, respecting the separation with other aircraft. It can also help choosing one way taxiways regarding to traffic and wind, and also measuring the impact of opening a new taxiway or closing an existing taxiway. Simulations are presented on a one day traffic at Paris Roissy. Delays are correlated to the traffic density on the airport.
• FACES: a Free flight Autonomous and Coordinated Embarked Solver , Nicolas Durand, Jean-Marc Alliot, Geraud Granger , ATC Quarterly , 2000/2/1 .
  FACES is an autonomous and coordinated embarked (on board) conflict solver for Free Flight airspace. It solves conflict by computing simple manoeuvres that guarantees conflict free trajectories for the next 5 minutes (min). Coordination is ensured by giving sequential manoeuvres to aircraft with a token allocation strategy. FACES can be implemented with the current positioning, broadcasting and flight management technology. Moreover, it is robust to communication or system failure for time up to one or two minutes. FACES was tested with a traffic simulator on busy traffic days over France. Airspace over level 320 was considered as Free Flight. 638 out of 641 conflicts were solved without using vertical manoeuvres. The 3 remaining conflicts could easily be solved with vertical manoeuvres. The mean delay was less than 30 seconds by aircraft manoeuvred, with a max delay of 150 seconds. An airborne implementation of this algorithm can be seriously considered.
• Neural Nets trained by genetic algorithms for collision avoidance , Nicolas Durand, Jean-Marc Alliot, Frederic Medioni , Applied Artificial Intelligence, Vol13, Number 3 , 2000/10/21 .
  As air traffic keeps increasing, many research programs focus on collision avoidance techniques. For short or medium term avoidance, new headings have to be computed almost on the spot, and feed forward neural nets are susceptible to find solutions in a much shorter amount of time than classical avoidance algorithms ($A^*$, stochastic optimization, etc.) In this article, we show that a neural network can be built with unsupervised learning to compute nearly optimal trajectories to solve two aircraft conflicts with the highest reliability, while computing headings in a few milliseconds.
• Using Neural Networks to predict aircraft trajectories , Yann LeFablec, Jean-Marc Alliot , IC-AI 99 Las Vegas , 1999/7/1 .
  This paper deals with the problem of predicting an aircraft trajectory in the vertical plane. A method depending on a small number of starting parameters is introduced and then used on a wide range of cases. The chosen method is based on neural networks. Neural networks are trained using a set of real trajectories and then used to forecast new ones. Two prediction methods have been developed: the first is able to take real points into account as the aircraft flies to improve precision. The second one predicts trajectories even when the aircraft is not flying. After depicting those prediction methods, the results are compared with other forecasting functions. Neural networks give better results because they only rely on precisely known parameters.
• Peut-on supprimer le contrôle au sol , Nicolas Durand, Jean-Marc Alliot , La Recherche , 1999/04/01 .
  
• A Combined Nelder-Mead Simplex and Genetic Algorithm , Nicolas Durand, Jean-Marc Alliot , GECCO 99 , 1999/01/29 .
  It is usually said that genetic algorithm should be used when nothing else works. In practice, genetic algorithm are very often used for large sized global optimization problems, but are not very efficient for local optimization problems. The Nelder-Mead simplex algorithm has some common characteristics with genetic algorithm, but it can only find a local optimum close to the starting point. In this article, a combined Nelder-Mead Simplex and Genetic algorithm is introduced and tested on classical test functions on which both genetic algorithm or local optimization techniques are not efficient when separately used.
• Turbo codes optimization using genetic algorithms , Nicolas Durand, Jean-Marc Alliot, Boris Bartolomé , CEC 99 , 1999/01/29 .
  Turbo Codes have been an important revolution in the Digital Communications world. Since their discovery, the coding community has been trying to understand, explain and improve Turbo Codes. The floor phenomenon is the Parallely Concatenated Convolutive Turbo Codes main problem. In this paper, Genetic Algorithm are used to lower the Free Distance of such a Code. Results in terms of B.E.R. are compared to the other main methods.
• De nouvelles techniques pour le controle aérien , Nicolas Durand et Jean-Marc Alliot , Revue "La jaune et la rouge". , 1998/6/1 .
  Le trafic aérien a connu une progression très importante pendant les dernières décennies et toutes les prévisions tendent à montrer que cette croissance ne devrait guère se ralentir dans les prochaines années. De 1986 à 1996, le trafic a connu un accroissement de 66% et on prévoit pour 2006 un accroisssement par rapport à 1996 de l ordre de 35% à 70%. Dans ces conditions, la congestion du ciel est en passe de devenir le facteur limitant de la croissance du trafic aérien, du moins en Europe, et la pression des compagnies aériennes se fait de plus en plus forte pour que la gestion du trafic soit à la fois plus souple et plus efficace. Parallèlement, les avions s équipent de moyens sophistiqués qui devraient permettre, à plus ou moins long terme, de changer radicalement les techniques de controle des aéronefs. C est dans ce cadre qu est aujourd hui posé par les compagnies, suivant en cela le RTCA, le concept du Free Flight (vol sans contrainte), un concept qui tendrait, sous certaines conditions, à affranchir les avions du controle aérien tel qu il est pratiqué aujourd hui et permettrait ainsi aux aéronefs de suivre le cheminement de leur choix dans certaines zones de l espace aérien. Comme nous allons cependant le voir, le chemin à parcourir est encore long avant la mise en place d un tel concept.
• FACES: A Free flight Autonomous and Coordinated Embarked Solver , JM Alliot, N Durand , 2nd USA/EUROPE ATM R & D seminar. , 1998/12/1 .
  FACES is an autonomous and coordinated embarked conflict solver for Free Flight airspace. It solves conflict by computing simple manoeuvres that guarantees conflict free trajectories for the next 5 minutes (mns). Coordination is ensured by giving sequential manoeuvres to aircraft with a token allocation strategy. FACES can be implemented with the current positioning, broadcasting and flight management technology. Moreover, it is robust to communication or system failure for time up to one or two minutes. FACES was tested with a traffic simulator on busy traffic days over France. Airspace over level 320 was considered as Free Flight. 638 out of 641 conflicts were solved without using vertical manoeuvres. The mean delay was less than 30 seconds by aircraft manoeuvred, with a max delay of 150 seconds. The remaining conflicts could easily be solved with vertical manoeuvres. An airborne implementation of this algorithm can be seriously considered.
• Genetic crossover operator for partially separable functions , Nicolas Durand, Jean-Marc Alliot , GP98. , 1998/07/22 .
  Partial separation is a mathematical technique that has been used in optimization for the last 15 years. On the other hand, genetic algorithms are widely used as global optimizers. This paper investigates how partial separability can be used in conjunction with GA. In the first part of this paper, a crossover operator designed to solve partially separable global optimization problems involving many variables is introduced. Then, a theoretical analysis is presented on a test case, along with practical experiments on fixed size populations, with different kinds of selection methods.
• Airspace Sectoring by Evolutionary Computation , Daniel Delahaye, Marc Schoenauer, Jean-Marc Alliot , IEEE International Congres on Evolutionary Computation , 1998/05/04 .
  This paper addresses the classical graph partitioning problem applied to the air network: One considers an air transportation network with aircraft inducing a control workload. This network has to be partitioned into K balanced sectors for which the cutting flow is minimized. Evolutionary computation has given very good results and seems to be very well adapted to the air network partitioning problem. It respects the major operational constraints and can generate three dimensional sectors with planar vertical boundaries after applying an algorithm which synthesis spatial envelops from connected components.
• CATS: A complete Air Traffic Simulator , JM Alliot, JF Bosc, N Durand, L Maugis , 16th DASC. , 1997/10/26 .
  In this document, we present the CATS system. The main ideas behind the design of CATS were to have a general purpose simulator able to be a stable basis for the development of other modules, representing different levels of Air Traffic Control and Air Traffic Management. In the first part of this paper, the basic framework and hypothesis of the CATS simulator are introduced. The second part deals with the general mathematical concepts regarding conflict resolution and airborne collision avoidance systems. Different results obtained so far with modules regarding conflict resolution, avoidance, or workload, built on top of the CATS simulator are presented as examples in the last part.
• An experimental study of ATM capacity , J.M. Alliot J.F. Bosc N. Durand and L. Maugis , Symposium Europe/USA , 1997/06/14 .
  We develop in this paper a formalized approach, simulation based planning, to determine the requirements needed to accomplish efficient air traffic services and to assess how well proposed operational scenarios meet those requirements.
• Optimal Resolution of En Route conflicts , Nicolas Durand, Jean-Marc Alliot , Séminaire Europe/USA, Saclay, Juin 1997 , 1997/06/06 .
  Automatic Control has been a subject of studies for the last twenty years. It involves many difficult problems that have to be solved: conflict detection, modelling of uncertainties on trajectories, clustering of 1-to-1 conflict to find unconnected n-aircraft problems, etc... Moreover, the n-aircraft conflict resolution problem is highly combinatorial and cannot be optimally solved using classical mathematical optimization techniques. The set of admissible solutions is made of many unconnected subsets enclosing different local optima, but the subset enclosing the optimum cannot be found a priori. In this paper, we present an automatic conflict solver and its implementation in an Air Traffic simulator, with statistical results on real traffic over France. This solver, which takes into account speed uncertainties and allows aircraft to fly on direct routes, solves every conflict on a loaded day, and gives each aircraft its requested flight level and departure time.
• Résolution de conflits aériens par algorithmes génétiques , Nicolas Durand, Jean-Marc Alliot , Revue de l'Association Aéronautique et Astronautique de France , 1996/6/20 .
  L'amélioration du controle du trafic aérien met en évidence des problèmes d'optimisation très complexes auquels peu de chercheurs se sont attaqués jusqu'à une période récente. Le problème d'optimisation de trajectoires pour la résolution de conflits en route reste aujourd'hui ouvert. Dans cette article, nous posons les fondements mathématiques liés aux problèmes de résolution de conflit et montrons comment des techniques d'optimisation stochastiques peuvent etre appliqués pour résoudre ces problèmes. (Le scan original de l'article est disponible ici).
• Air Traffic Control, chess playing and chess programs: lessons to learn , Jean-Francois Bosc, Jean-Marc Alliot , International conference on tools for Artificial Intelligence (1996) , 1996/10/16 .
  Air traffic control and chess playing are human cognitive activities that share a large number of characteristics. In this paper, we first discuss similarities of these two activitie; then, using the experience gained in the field of games (and chess) programming, which has encountered numerous excellent results, we try to draw some conclusions on how systems could be designed to improve performance of Air Traffic Control.
• Genetic Algorithms for Air Traffic Control System , Daniel Delahaye, Nicolas Durand, Jean-Marc Alliot, Marc Schoenauer , 14th IFORS Triennal Conference , 1996/07/08 .
  The Air Traffic Control system of a country manages all the aircrafts that fly in its airspace, designs control sectors, manages the flows between the different airports and beacons, ensures separation between aircrafts during their flight, take off and landing. Thus, it operates at different levels, each one of them designed to provide control, ensure safety, and limit the traffic passed to the following level. In this paper we show how Genetic Algorithms can improve some of the tasks manually done by the ATC system. After a brief description of GAs, some fo the improvements used (simulated annealing, sharing), we study three applications of GAs to ATC. We first show how GAs can optimize air space sectoring. Then we give an application of GAs to traffic assignment. The last part gives an application of GAs to en-route conflict resolution.
• Collision avoidance using neural networks learned by genetic algorithms , Nicolas Durand, Jean-Marc Alliot, Joseph Noailles , The Ninth International Conference on Industrial & Engineering (IEA-AEI 96 Nagoya,Japan) , 1996/06/01 .
  As Air Traffic keeps increasing, many research programs focus on collision avoidance techniques. In this paper, a neural network learned by genetic algorithm is introduced to solve conflicts between two aircraft. The learned NN is then tested on different conflicts and compared to the optimal solution. Results are very promising.
• Techniques d optimisation stochastique appliquées aux problèmes du controle aérien , Jean-Marc Alliot , Thèse d'habilitation INPT. , 1996/05/28 .
  Ce document décrit diverses applications des méthodes d optimisation stochastique, (algorithmes génétiques en particulier) aux problèmes du trafic aérien. Dans sa première partie, on peut également trouver une description précise des différentes techniques génétiques, ainsi qu une comparaison rapide avec d autres techniques d optimisation sur des problèmes classiques.
• Genetic Algorithms for Air Traffic Control system , Daniel Delahaye, Nicolas Durand, Jean-Marc Alliot, Marc Schoenauer , INFAUTOM'96 , 1996/04/01 .
  The Air Traffic Control system of a country manages all the aircrafts that fly in its airspace, designs control sectors, manages the flows between the different airports and beacons, ensures separation between aircrafts during their flight, take off and landing. Thus, it operates at different levels, each one of them designed to provide control and ensure safety, and limiting the traffic passed to the following level. In this paper we show how Genetic Algorithms can improve some of the tasks manually done by the ATC system. After a brief description of GAs, some fo the improvements used (simulated annealing, sharing), we study three applications of GAs to ATC. First, we show how GAs can optimize Air Space Sectoring .As there are many aircrafts simultaneously in the sky, airspace is partitionned into different sectors, each one inducing a workload for a controller managing the aircrafts inside this sector. We show how well GAs can balance the sectors workloads. Then, we give an application of GAs to traffic assigmnement. As many pilots choose the same routes, some sectors tend to be overloaded. In this part we show how GAs can optimally change aircrafts routes to reduce sector congestions and conflicts. The last part gives an application of GAs to en-route conflict resolution. The three applications we described are completly connected. A project of automating and optimizing the ATC system will follow this initial study. Through this paper, GAs showed that they were completly adapted to this project.
• Genetic operators adapted to partially separable functions , Nicolas Durand, Jean-Marc Alliot, Joseph Noailles , Unpublished , 1996/01/01 .
  In this paper, a crossover operator for genetic algorithms is introduced to solve partially separable global optimization problems involving many variables. The fitness function must be an addition of positive sub-functions involving only a subset of the variables. A ``local fitness'' is associated to each variable and a parameter $\Delta$ controlling the operator's determinism is introduced. Combined with sharing and simulated annealing, this operator improves GAs efficiency to optimize combinational problems involving many variables. A polynomial function is given as an example and the operator is then used to solve a $200$ cities' TSP. The operator becomes necessary for problems such as conflict resolution involving many aircraft for air traffic control.
• A genetic algorithm to improve an Othello program , Jean-Marc Alliot, Nicolas Durand , Evolution Artificielle, Brest , 1995/9/1 .
  
• An optimizing conflict solver for ATC , Nicolas Durand, Jean-Marc Alliot, Olivier Chansou , ATC Quarterly , 1995/10/13 .
  As traffic keeps increasing, En Route capacity, especially in Europe, becomes a serious problem. Aircraft conflict resolution, and resolution monitoring, are still done manually by controllers. Solutions to conflicts are empirical and, whereas aircraft are highly automated and optimized systems, tools provided for ATC control are very basic, even out of date. If we compare the current capacity and the standard separation to the size of controlled space, the conclusion is easy to draw: while ATC is overloaded, the sky is empty. It must be noticed that enhancing En Route capacity does not require optimal resolution of aircraft conflicts. The need for an automatic problem solver is also a serious concern when addressing the issues of free flight. It is still very much unclear how conflicts will be solved in free flight airspace. Human controllers highly rely on standard routes and traffic organization for solving conflicts; they are much quickly overloaded when controlling aircraft flying on direct routes. Free flight traffic, with a completely unorganized structure, might require automated, computer based, solvers. Moreover, one of the aim of free flight is to give aircraft optimal trajectories, whereas using ACAS techniques is certainly not optimal, and should only looked upon as a last issue system. In this paper, we present an optimal problem solver, based on a stochastic optimization technique (genetic algorithms). It builds optimal resolution for complex conflicts and also computes a large number of nearly optimal resolutions that do not violate separation constraints. Part 1 of the paper introduces the problem solver, its constraints and goals. Modelling is discussed in part 2. Part 3 introduces genetic algorithms techniques and the coding of the problem. Part 4 presents different examples of resolution of very complex test problems. In part 5 we present the complete ATC simulator, conflict detector and cluster builder used to benchmark the problem solver on real traffic; we also discuss weaknesses of the system and possible improvements.
• Automatic aircraft conflict resolution using Genetic Algorithms , Nicolas Durand, Jean-Marc Alliot , 11th Annual ACM conference on applied computing (ACM/SAC 96, Philadelphia) , 1995/10/1 .
  Studies on the use of genetic algorithms for conflict resolution and air space sectoring have given promissing results. This paper presents new results for solving conflict between aircraft for En Route Air Traffic Control (ATC) in real time situation. The first part of the paper introduces the problem, its constraints and goals. The choice of the model is discussed in the second part. In the third part, we discuss the complexity of our problem and explain why classical optimization tools such as gradient methods are not adapted to solve it. Part four describes briefly genetic algorithms and the improvements that were used. Part five presents the coding and part six give several numerical applications.
• Genetic algorithms for automatic regroupment of Air Traffic Control sectors , Daniel Delahaye, Jean-Marc Alliot, Marc Schoenauer, Jean-Loup Farges , EP 95 , 1995/03/25 .
  In this paper, we show how genetic algorithms can be used to compute automatically a balanced regroupement of Air Traffic Control sectors to optimally reduce the number of controller teams during daily low flow periods.
• Genetic algorithms for optimal plane conflict resolution , Nicolas Alech, Nicolas Durand, Jean-Marc Alliot, Marc Schoenauer , SPICIS'94 (Second Singapore International Conference on Intelligent Systems) , 1994/11/01 .
  At the dawn of civil aviation, pilots resolved conflicts themselves because they always flew in good weather conditions with low speed aircrafts. Nowadays, pilots must be helped by an air traffic controller on the ground who has a global view of the current traffic distribution in the airspace and can give indications to the pilots to avoid collisions. Solutions to conflicts are empirical, controllers are trained to react to certain types of conflicts and are limited by a workload. It is clear that if the ATC is overloaded, the sky is not. Conflict resolution is a trajectory optimization problem under constraints the complexity of which is so important that it has not been solved yet. Many attempts have been made to solve this problem with classical methods, such as gradient methods, reactive technics, expert systems, but most of them failed. In this paper, we show how genetic algorithms can be used to solve en-route aircrafts conflict automatically to increase Air Traffic Control capacity in high density areas. Our main purpose is to find out the global optimum and not only a suitable solution, in a real time situation, with conflict free trajectories that respect both plane and pilot performances.
• Algorithmes Génétiques et Programmation Linéaire appliqués à la résolution de conflits ATC. , Frédéric Médioni, Nicolas Durand, Jean-Marc Alliot , Evolution Artificielle 94 (Toulouse) , 1994/09/19 .
  La génération de trajectoires optimales d'évitement pour des aéronefs en route est un problème complexe qui n'est pour l'instant résolu que de manière empirique par les controleurs. Nous présentons ici une autre manière d'utiliser les algorithmes génétiques dans ce but, en les couplant à un programme d'optimisation linéaire.
• Algorithmes Génétiques: un croisement pour les problèmes partiellement séparables , Nicolas Durand, Jean-Marc Alliot, Joseph Noailles , Evolution Artificielle 94 (Toulouse) , 1994/09/19 .
  Dans cet article, nous proposons une méthode de croisement pour résoudre des problèmes d'optimisation globale comportant un grand nombre de variables et dont la fonction d'évaluation peut se décomposer en une somme de fonctions ne faisant pas intervenir toutes les variables. Cette méthode de croisement nécessite l'introduction d'une ``fitness locale'' associée à chaque variable et d'un paramètre d'incertitude $\Delta$ qui permet de moduler le déterminisme de l'opérateur. Cet opérateur de croisement, utilisé avec une méthode de sharing et de recuit simulé rend les algorithmes génétiques très efficaces pour minimiser des problèmes comportant beaucoup de variables ou fortement combinatoires, tels que la minimisation d'un polynome de grande taille ou la résolution du problème du voyageur de commerce.
• Genetic algorithms for air traffic assignment , Daniel Delahaye, Jean-Marc Alliot, Marc Schoenauer, Jean-Loup Farges , 1994 European Conference on Artificial Intelligence Applications , 1994/08/10 .
  In this paper, we show how genetic algorithms can be used to compute automatically a traffic assignment of aircraft on the air network to increase Air Traffic Control capacity in high density areas.
• Different paths to automation , Patrick Dujardin, Jean-Marc Alliot, Paul-Henri Mourlon , Conference of the International Federation for Automation and Control , 1994/01/01 .
  Does the future of Air Traffic Management lie in automation? It looks like flying a plane from point A to point B is just a mathematical problem involving optimization under constraints (other planes), flow management on networks, etc. So, it should probably be handled automatically by computers, either on board or on the ground. Moreover, it is also clear that human capacity for information handling and computation is severely limited and that, sooner or later, it will be impossible to increase airspace capacity if we keep human as effective and exclusive actors in the control loop. But, even if we are over-optimistic, we can not expect any automated ATC system before at least twenty or thirty years: the more recent prototypes of automated systems, such as the ARC2000 system, rely heavily on many assumptions that are not met today, such as FMS-4D aboard all planes, etc. Moreover, these assumptions will not be met for quite a long time: there are many different types of airplanes (commercial, private, etc.) and fitting out each and every of them with such expensive and complex equipment is not to be expected on short terms. There are also some technical questions about automation that have to be answered: there have been no serious theoretical studies on the capacities of automated systems, and there is still no clear design of what will be the automated system of years 2020--2040: many different alternatives exist (4D tubes, reactive systems, distributed resolutions on board, resolutions on the ground, etc.) Moreover, an ATM control system is a patchwork of many different tasks, some of which already being good candidates for automation, while others will still be impossible to automate for quite a long time. So we have to define a way to go from the current, existing system, to a system that will not be ready before at least 2020, the design of which being still uncertain. This transition phase is certainly the major thing to work on. In this paper, we are trying to show that there are many different ways to go from the existing system to an automated system, each way having drawbacks and advantages. Moreover, during this evolution, the role of the pilot and the role of the controller will both change.
• Genetic algorithms for partitioning air space , Daniel Delahaye, Jean-Marc Alliot, Marc Schoenauer, Jean-Loup Farges , 10th IEEE Conference on Artificial Intelligence Applications , 1993/07/14 .
  In this paper, we show how genetic algorithms can be used to compute automatically a balanced sectoring of airspace to increase Air Traffic Control capacity in high density areas.
• Genetic Algorithms for solving Air Traffic Control , Jean-Marc Alliot, Hervé Gruber, Georges Joly, Marc Schoenauer , 9th IEEE Conference of Artificial Intelligence Application , 1992/08/01 .
  This paper shows how genetic algorithms methods can be used to solve Air Traffic Control conflicts. We also compare these methods, in order to validate their solutions, to more classical methods such as graph search with A* and related algorithms, or simulated annealing. We show that genetic algorithms are perfectly suited for ATC conflict problems, as they are able to give many different solutions for a given problem and give almost optimal solution in a very short amount of time, with the possibility to enhance the solution later if more time is available, a critical property for ATC systems.
• Une machine parallèle pour l'implantation d'extensions de PROLOG , Jean-Marc Alliot , 1992/07/11 .
  PROLOG est parfaitement adapté au traitement des clauses de Horn mais ne permet pas de traiter naturellement les problèmes liés à la déduction pour les logiques non-classiques, les théories équationnelles, les prédicats flous. Tous ces différents cas réclament des moyens différents de calculer un nouveau but à partir du but courant. Nous définissons dans cette thèse un mécanisme général, le système TARSKI, permettant de développer des extensions de PROLOG :
  • Réécriture complète des mécanismes d'inférences et développement d'un nouveau formalisme permettant de traiter des clauses de Horn généralisées.
  • Développement d'une machine abstraite pour implanter des règles de résolution paramétrables.
  • Etude et implantation du parallélisme.
• ERATO, un système expert d'aide au controle du trafic aérien , Marcel Leroux, Jean-Marc Alliot , Avignon 1992 , 1992/06/01 .
  ERATO (En Route Air Traffic Organizer) est un système expert d'aide au controle du trafic aérien. Le but d'ERATO est de fournir au controleur des outils pour l'assister dans sa tache, et non de réaliser une automatisation du controle. Afin d'etre plus facile à intégrer, ERATO tente de modéliser au mieux le raisonnement du controleur pour lui fournir une aide directement en rapport avec ses méthodes de résolution.
• Implementing Prolog Extensions: A Parallel Inference Machine , Jean-Marc Alliot, Andreas Herzig, Mamede Lima-Marques , Fifth Generation Computer System'92 (Tokyo, Japan) , 1992/04/01 .
  We present in this paper a general inference machine for building a large class of meta-interpreters. In particular, this machine is suitable for implementing extensions of Prolog with non-classical logics. We give the description of the abstract machine model and an implementation of this machine in a fast language (ADA), along with a discussion on why and how parallelism can easily increase speed, with numerical results of sequential and parallel implementation.

Retour à ma page principale

Le téléchargement ou la reproduction des documents et photographies présents sur ce site sont autorisés à condition que leur origine soit explicitement mentionnée et que leur utilisation se limite à des fins non commerciales, notamment de recherche, d'éducation et d'enseignement.
Tous droits réservés.

Dernière modification: 09:48, 22/02/2024