Algorithme | EPFL Graph Search

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation. Etymologie et Histoire Le mot algorithme a une longue histoire. 'Al-Khwârizmî (en arabe : الخوارزمي), est un mathématicien persan du , dont le nom est relatif au Khwarezm, une région située au Sud de la mer d'Aral. Au , il écrit en arabe un traité qui sera traduit en latin au sous le titre Algoritmi de numero Indorum. "A

Uncooperative Rendezvous in Space: Design of an Electronic Architecture for High Performance Avionic with Multi Sensor Input and Intensive Data Rate.

Michaël Yannick Juillard

Active Debris Removal missions consist of sending a satellite in space and removing one or more debris from their current orbit. A key challenge is to obtain information about the uncooperative target. By gathering the velocity, position, and rotation of the desired object, the satellite is able to plan its trajectory and define the sequence of approach. It requires the use of a variety of sensors with often a high data rate. For this task, a dedicated payload computer is envisioned with the responsibility of processing the information from the various rendezvous sensors. This component has the goal to provide meaningful information to the main satellite computer about the targeted debris. The focus of this work is on the data processing, the number of elements, and the electrical energy with constraints due to internal communication.First, an avionic testbench was built at the EPFL Space Center to assess early hardware and software architectures. The goal is to enable Hardware-In-the-Loop testing while developing the payload computer. A communication data bus has been implemented between the Platform and the Payload On-Board Computer. Emphasis was placed on the reliability of the high-level protocol and multiple concepts for improvement were analyzed.In a second phase, the testbench has been extended to support other data buses. The aim was to develop a reliable and efficient backup or fall-back data bus in case of failure in the main link. Four data buses have been tested with extensive analyses on their resilience to error and the efficiency of their data exchange.In parallel, extensive work has been performed to develop a simulation and optimization tool. Its goal is to support the design of payload avionic architectures for ADR missions by providing trade-offs and analyses. In the first iteration, a simulator has been created with instances of various high-level elements modeled.The second iteration introduced the additional dimension of optimization. It is trying to determine the best set of instruments and algorithms to use. With this capability, numerous analyses have been conducted on the influence of various parameters linked to the general optimizer behavior. It allows us to better understand the strength and limitations of the tool.The third step regarding the tool was to start its verification. The task has been to develop an Hardware-In-the-Loop architecture to compare its behavior with the results of the optimizer. The implementation of various mock-up algorithms enables the verification of their models in the tool. These analyses guarantee the feasibility of the outputted solution.The last part was dedicated to the creation and analysis of a realistic payload avionic architecture. The goal was to test the capability of the tool with hardware elements inspired by actual components. This work has shown the procedure to efficiently use the tool in the design phase of a mission.In conclusion, the work on the communication between the Payload and the Platform On-Board Computer has brought valuable lessons and experiences to the projects. They can now be used for the establishment of the high-level protocol into ClearSpace-1 flight software. In addition, the optimizer created allows tackling the design of complex payload avionic architecture where mass saving and processing resources are crucial. It is an essential point to develop a highly efficient payload computer for an Active Debris Removal satellite.

EPFL2022

Problèmes de cheminements optimaux dans les réseaux avec contraintes associées aux arcs

In this thesis we consider two optimal routing problems in networks. Both are NP-hard and are often used to modelize real life problems of large size. We first present the capacitated arc routing problem (CARP). In this problem, we have to serve a set of customers represented by the arcs of a network with vehicles of restricted capacity. The aim is to design a set of vehicle routes of least total cost. We describe two heuristic methods for the CARP based on local search techniques. The first one is a Tabu Search heuristic using an original post-optimization procedure. Principles appearing in this procedure are used to define a class of neighborhoods we combine in a Variable Neighborhood Descent method. Our algorithms compare favorably with some of her methods. They were initially developed to deal with the undirected CARP. We describe how to transform them so that they can be applied to the directed CARP. We also propose an adaptation to the directed case of a lower bound originally developed for the undirected CARP. This lower bound is used to evaluate the quality of the solutions produced by our algorithms for the directed CARP. Our methods obtain solutions whose value is, on average, close to known lower bounds. We use the CARP to tackle a real life problem of boat routing and scheduling. This problem can be viewed as a directed CARP with time windows. We describe in detail its modeling process and we analyze our first results. We obtain solutions that require less boats than the present schedule. Nevertheless, these solutions are not completely feasible in practice. We suggest some ways to improve them. The second problem treated in this thesis is the shortest capacitated paths problem (SCPP). We present a Tabu Search heuristic and some post-optimization procedures for the SCPP. These procedures are called in our Tabu Search algorithm. Two versions of this algorithm are considered. In the first one, post-optimization procedures are intensively used. In the second one, they are less frequently applied. This second version is faster. Compared with a greedy approach, the two versions of our Tabu Search heuristic obtain solutions which are, on average, of better quality. The SCPP was proposed to us by EDF (Electricité de France) in order to minimize the total length of the paths followed by cables in a nuclear power-station. It can also be viewed as a subproblem of the bandwidth packing problem (BWP) appearing in telecommunications.

EPFL2000

Problèmes de cheminements optimaux dans les réseaux avec contraintes associées aux arcs

EPFL2000

Uncooperative Rendezvous in Space: Design of an Electronic Architecture for High Performance Avionic with Multi Sensor Input and Intensive Data Rate.

Michaël Yannick Juillard

EPFL2022