The stochastic shortest path problem lies at the heart of many questions in the formal verification of probabilistic systems. It asks to find a scheduler resolving the non-deterministic choices in a weighted Markov decision process (MDP) that minimizes or maximizes the expected accumulated weight before a goal state is reached. In the classical setting, it is required that the scheduler ensures that a goal state is reached almost surely. For the analysis of systems without guarantees on the occurrence of an event of interest (reaching a goal state), however, schedulers that miss the goal with positive probability are of interest as well. We study two non-classical variants of the stochastic shortest path problem that drop the restriction that the goal has to be reached almost surely. These variants ask for the optimal partial expectation, obtained by assigning weight 0 to paths not reaching the goal, and the optimal conditional expectation under the condition that the goal is reached, respectively. Both variants have only been studied in structures with non-negative weights. We prove that the decision versions of these non-classical stochastic shortest path problems in MDPs with arbitrary integer weights are at least as hard as the Positivity problem for linear recurrence sequences. This Positivity problem is an outstanding open number-theoretic problem, closely related to the famous Skolem problem. A decid- ability result for the Positivity problem would imply a major breakthrough in analytic number theory. The proof technique we develop can be applied to a series of further problems. In this way, we obtain Positivity-hardness results for problems addressing the termination of one-counter MDPs, the satisfaction of energy objectives, the satisfaction of cost constraints and the computation of quantiles, the conditional value-at-risk – an important risk measure – for accumulated weights, and the model-checking problem of frequency-LTL. Despite these Positivity-hardness results, we show that the optimal values for the non-classical stochastic shortest path problems can be achieved by weight-based deter- ministic schedulers and that the optimal values can be approximated in exponential time. In MDPs with non-negative weights, it is known that optimal partial and conditional expectations can be computed in exponential time. These results rely on the existence of a saturation point, a bound on the accumulated weight above which optimal schedulers can behave memorylessly. We improve the result for partial expectations by showing that the least possible saturation point can be computed efficiently. Further, we show that a simple saturation point also allows us to compute the optimal conditional value-at-risk for the accumulated weight in MDPs with non-negative weights. Moreover, we introduce the notions of long-run probability and long-run expectation addressing the long-run behavior of a system. These notions quantify the long-run average probability that a path property is satisfied on a suffix of a run and the long-run average expected amount of weight accumulated before the next visit to a target state, respectively. We establish considerable similarities of the corresponding optimization problems with non-classical stochastic shortest path problems. On the one hand, we show that the threshold problem for optimal long-run probabilities of regular co-safety properties is Positivity-hard via the Positivity-hardness of non-classical stochastic shortest path problems. On the other hand, we show that optimal long-run expectations in MDPs with arbitrary integer weights and long-run probabilities of constrained reachability properties (a U b) can be computed in exponential time using the existence of a saturation point.

This Master’s Thesis consists of description of current routing protocols and routers, basic principles of neural networks and their interpretation in connection with the use for routing in data networks and telecommunications networks. In the thesis I focused on neural networks, which use energetic functions to find solution stabled states and their use for data routing. I produced the application software to test and find suitable variables for each function. This application counts the shortest path and is able to change variables to reach the best solution of stabled state of neural network. These solutions are compared with other functions that are usually used in nowadays systems for data network routing.

The master’s thesis deals with the design and realization of a program that is able to find the shortest route in the tourist map between selected points. The user can select the type of hiking trail. Application also generates terrain heightmap from contour lines and path elevation profile.

This thesis deals with theoretical basics of risk modelling in transportation and optimization using aggregated traffic data. In this thesis is suggested the procedure and implemented the application solving network problem of shortest path between geographical points. The thesis includes method for special paths evaluation depending on the frequency of traffic incidents based on real historical data. The thesis also includes a~graphical interface for presentation of the achieved results.

L’enjeu de planification de vol à bord d’un hélicoptère en tenant compte des différents paramètres environnementaux constitue un facteur clé dans le secteur aéronautique afin d’assurer une mission en toute sécurité avec un coût réduit. Ce défi concerne à la fois la phase de préparation de la mission sur une station au sol mais aussi en cours de vol pour faire face à un évènement imprévu. Nous citons un premier exemple de mission de type recherche et sauvetage qui dispose d’un temps limité pour localiser et rechercher des personnes en danger. Pour ce faire, le plan de vol généré doit suivre le relief du terrain à des altitudes relativement basses entre des points de passage désignés. L’objectif est de permettre au pilote de localiser une victime dans une durée bornée. Un deuxième type de mission comme l’assistance médicale a la particularité d’assurer un vol qui favorise le confort du passager ainsi qu’une route qui minimise le temps de vol selon la criticité de la situation. Pendant la phase dynamique, lorsqu’il s’agit d’un événement complexe telle qu’une panne moteur, une replanification de la mission devient nécessaire afin de trouver un chemin aérien qui permet d’atterrir en toute sécurité dans les plus brefs délais. Dans un autre exemple comme l’évitement d’obstacle dynamique ou de zone dangereuse, il s’agit de calculer un autre plan de vol pour atteindre la destination. Cependant à ce jour, les pilotes ne bénéficient pas de système d’autoroutage 3D permettant la replanification dynamique de mission face à une situation d’urgence. Face au défi de génération d’un plan de vol optimal, nos réflexions profondes ont abouti à la proposition d’un nouveau système de planification de chemin, pour des aéronefs, dédié à la préparation de mission avant le vol ainsi qu’à la replanification dynamique en cours de vol face à une situation d’urgence. Le système de planification peut être déployé sur une station au sol ou bien intégré comme fonction avionique au sein de l’aéronef. Les résultats obtenus ont abouti à un brevet déposé devant l’INPI et à plusieurs actions de transfert technologique au sein d’Airbus Hélicoptères. Le système s’appuie sur des techniques de discrétisation de l’espace et de calcul du plus court chemin afin de générer automatiquement des solutions flexibles en terme de profil de chemin en respectant plusieurs contraintes liées à l’appareil, le terrain et l’environnement. La solution proposée est générique et capable de s’adapter selon le type de l’aéronef, le type de la mission et la fonction objectif à minimiser. Le système de planification peut offrir des solutions avec différents compromis entre le temps d’exécution et la qualité du chemin selon le temps disponible qui peut être corrélé avec la criticité de la situation. Le fonctionnement du système de planification de chemin se compose principalement de deux phases : le prétraitement et le routage. La phase de prétraitement permet une discrétisation multi-altitude de l’espace 3D selon une précision donnée et la génération automatique d’un graphe de navigation avec une connexité paramétrable. La phase de routage 3D calcule le chemin en prenant en considération un ensemble de contraintes telles que les limitations angulaires en horizontal et en vertical et une fonction objectif à minimiser tels que la distance, le carburant, le temps, etc. Lors de la phase d’exploration du graphe, le système de planification peut communiquer avec le modèle de performance de l’appareil afin de minimiser une fonction coût liée à la performance et de s’assurer au fur et à mesure de la faisabilité de la mission. La génération automatique des plans de vol et la replanification dynamique représentent une brique essentielle pour concevoir des systèmes d’assistance au pilote ainsi que des aéronefs autonomes. / Helicopter flight planning is a key factor in the aeronautics domain in order to ensure a safe mission at a reduced cost taking into consideration different environmental parameters like terrain, weather, emergency situations, etc. This challenge concerns both the mission preparation phase using a ground station and also during the flight to cope with a complex event (mechanical failure, dynamic obstacle, bad weather conditions, etc.). We quote as a first example a Search and Rescue mission that should be performed in limited time to locate persons in danger. To achieve that, the generated flight path must follow the terrain profile at relatively low altitudes crossing the predefined waypoints. The objective is to allow the pilot to locate a victim in a short time. Another example for a mission of medical assistance where the helicopter should ensure the comfort of patients as well as minimizing the flight time to respect critical situations. During the flight, when a complex event occurs such as engine failure, re-planning the mission becomes necessary in order to find a new path that could guarantee safe landing. Unfortunately, pilots do not benefit from an embedded 3D path planning system that enables dynamic mission re-planning in case of emergency. To tackle the challenge of generating an optimal flight plan, we proposed new path planning system dedicated to mission preparation and dynamic path re-planning during critical situations. The planning system can be deployed on a ground station or embedded as an avionic function in the aircraft. The achieved results are registered as a patent at National Institute of Intellectual Property and deployed inside Airbus Helicopters through several technology transfers. The system relies on 3D space discretization and shortest path planning techniques to generate automatically flexible path profiles that respect several. The proposed solution is generic and is able to adapt to the aircraft model, mission and the objective function to be minimized. The path planning system can offer solutions with different tradeoffs between timing and path quality within the available runtime depending on the criticality of the situation. The functioning of the path planning system consists mainly of two phases : preprocessing and routing phase. The preprocessing allows a multi-altitude discretization of the 3D space according to a given precision and generate automatically a navigation graph with a configurable density. The 3D routing phase calculates the path by considering a set of constraints such as horizontal and vertical angular limitations and the objective function such as distance, fuel, time, etc. During the graph exploration phase, the path planning system can communicate with the aircraft performance model to evaluate a given criterion. Automatic flight path generation is an essential building block for designing pilot assistance systems and autonomous aircraft. In summary, we succeeded to reach the industrial expectations namely : the evaluation of mission feasibility, performances improvement, navigation workload reduction, as well as improving the flight safety. In order to realize the proposed solution, we designed a new tool for automatic 3D flight path planning. We named our tool DTANAV : Demonstration Tool for Aircraft NAVigation. It allows to apply the proposed planning process on real scenarios. Through the tool interface, the user has the possibility to set the parameters related to the mission (starting point, end point, aircraft model, navigation ceiling, etc.). Other algorithmic parameters are defined in order to control the quality and the profile of the generated solution.

The convergence of mobile services and Internet has brought a radical change in mobile networks. An all IP network architecture, an evolution of the radio access transport network, is required to support new high-bandwidth services. Unfortunately, existing control mechanisms are insufficient to guarantee end users a high quality of experience. However, coordinating radio and transport network resources is expected to yield a more efficient solution. This thesis project investigates the interactions between the congestion avoidance protocols, explicit congestion notification, and the traffic engineering metrics for latency and bandwidth, when using Open Shortest Path First with traffic engineering (OSPF-TE) as a routing protocol. Using knowledge of these interactions, it is possible to identify the appearance of bottlenecks and to control the congestion in the transport links within a radio access transport network. Augmenting a topology map with the network’s current characteristics and reacting to evidence of potential congestion, further actions, such as handovers can be taken to ensure the users experience their expected quality of experience. The proposed method has been validated in a test bed. The results obtained from experiments and measurements in this test bed provide a clear picture of how the traffic flows in the network. Furthermore, the behavior of the network observed in these experiments, in terms of real-time performance and statistical analysis of metrics over a period of time, shows the efficiency of this proposed solution. / Tjänstekonvergensen av Internet- och mobila tjänster har medfört en radikal förändring i mobilnäten. En ”All IP” nätverksarkitektur, en utveckling av radios transportnät. Utvecklingen krävs för att stödja de nya bredbandiga tjänsterna. Tyvärr är befintliga kontrollmekanismer otillräckliga för att garantera användarens kvalitetsupplevelse. Med att samordna radio- och transportnätverkets resurser förväntar man sig en effektivare lösning. Detta examensarbete undersöker samspelet mellan protokoll för att undvika överlast, direkt indikation av överlast och trafikal statistik för fördröjning och bandbredd med trafikstyrning baserat på fördröjning och bandbredd , vid användning av Open Shortest Path First ( OSPF - TE ) som routingprotokoll. Med hjälp av information om dessa interaktioner, är det möjligt att identifiera uppkomsten av flaskhalsar och för att styra trafikstockningar i transportförbindelser inom ett radioaccess transportnät. En utökad topologikarta med nätverkets aktuella egenskaper kommer att reagera på en potentiell överbelastning. Ytterligare åtgärder, till exempel överlämningar, vidtas i mobilnätet för att säkerställa användarens upplevda kvalitet. Den föreslagna metoden har validerats i en testmiljö. Resultaten från experiment och mätningar i denna testmiljö ger en tydlig bild av hur trafikflödena framskrider i nätverket. Beteendet hos nätverket som observeras i dessa experiment, i termer av realtidsprestanda och statistisk analys av mätvärden över en tidsperiod, visar effektiviteten av denna föreslagna lösning.

[pt] O objetivo do trabalho é o desenvolvimento de uma aplicação web capaz de realizar diferentes análises de diagramas UML. Umas dascaracterísticas da ferramenta é a compatibilidade com outras ferramentas de edição de diagramas UML. Para isto, foi implementado um parser genérico XMI que importa driagramas de classe e gera um grafo orientado equivalente. Com a posse do grafo, são realizados estudos capazes de adicionar informações extras aos diagramas. O primeiro estudo é a identificação de quais clases compõesm o core concept (classes de alta importância para o sistema). Outro estudo é a clusterização deste grafo a fim de agrupar classes em propostas de componentes. Por fim, são discutidas estimativas de importância, do grau de coesão, além de métricas de acoplamento e tamanho do diagrama como um todo e dos componetes gerados. / [en] The goal of this dissertation is to develop a web application that explores different analysis of UML diagrams. One of the main features of this tool is the compatibility with other tools that create UML diagrms. In order to do that, we implemented a generic XMI parser that import class diagrams and provides as result a directed graph. With this graph in hand, we conducted studies that provide extra information regrading this diagram. The first study is the identification of the classes that can be considered core concepts (defining the important classes of the system). The other study permorms graph clustering, aiming to create groups pf classes, making it possible to generate components. Finally, we discuss estimates of importance and degree of cohesion, as well as size and coupling metrics of the diagram as a whole and the generated components.

Traditional shortest path algorithms can efficiently find the optimal paths in graphs using simple heuristics. However, formulating a simple heuristic is challenging under the road network setting since there are multiple factors to consider, such as road segment length, edge centrality, and speed limit. This study investigates how a neural network can learn to take these factors as inputs and yield a path given a pair of origin and destination. The research question is formulated as: Are neural networks applicable to real-time route planning tasks in a roadnetwork?. The proposed metric to evaluate the effectiveness of the neural network is arrival rate. The quality of generated paths is evaluated by time efficiency. The real-time performance of the model is also compared between pathfinding in dynamic and static graphs, using theabove metrics. A staggered approach is applied in progressing this investigation. The first step is to generate random graphs, which allows us to monitor the size and properties of the training graph without caring too many details in a road network. The next step is to determine, as a proof of concept, if a neural network can learn to traverse simple graphs with multiple strategies, given that road networks are in effect complex graphs. Finally, we scale up by including factors that might affect the pathfinding in real road networks. Overall, the training data is optimal paths in a graph generated by a shortest path algorithm. The model is then applied to new graphs to generate a path given a pair of origin and destination. The arrival rate and time efficiency are calculated and compared with that of the corresponding optimal path. Experimental results show that the effectiveness, i.e., arrival rate ofthe model is 90% and the path quality, i.e., time efficiency has a medianof 0.88 and a large variance. The experiment shows that the model has better performance in dynamic graphs than in static graphs. Overall, the answer to the research question is positive. However, there is still room to improve the effectiveness of the model and the paths generated by the model. This work shows that a neural network trained to make locally optimal choices can hardly give a globally optimal solution. We also show that our method, only making locally optimal choices, can adapt to dynamic graphs with little performance overhead. / Traditionella algoritmer för att hitta den kortaste vägen kan effektivt hitta de optimala vägarna i grafer med enkel heuristik. Att formulera en enkel heuristik är dock utmanande för vägnätverk eftersom det finns flera faktorer att överväga, såsom vägsegmentlängd, kantcentralitet och hastighetsbegränsningar. Denna studie undersöker hur ett neuralt nätverk kan lära sig att ta dessa faktorer som indata och finna en väg utifrån start- och slutpunkt. Forskningsfrågan är formulerad som: Är neuronnätverket tillämpliga på realtidsplaneringsuppgifter i ett vägnät?. Det föreslagna måttet för att utvärdera effektiviteten hos det neuronnätverket är ankomstgrad. Kvaliteten på genererade vägar utvärderas av tidseffektivitet. Prestandan hos modellen jämförs också mellan sökningen i dynamiska och statiska grafer, med hjälp av ovanstående mätvärden. Undersökningen bedrivs i flera steg. Det första steget är att generera slumpmässiga grafer, vilket gör det möjligt för oss att övervaka träningsdiagrammets storlek och egenskaper utan att ta hand om för många detaljer i ett vägnät. Nästa steg är att, som ett bevis på konceptet, undersöka om ett neuronnätverk kan lära sig att korsa enkla grafer med flera strategier, eftersom vägnätverk är i praktiken komplexa grafer. Slutligen skalas studien upp genom att inkludera faktorer som kan påverka sökningen i riktiga vägnät. Träningsdata utgörs av optimala vägar i en graf som genereras av en algoritm för att finna den kortaste vägen. Modellen appliceras sedan i nya grafer för att hitta en väg mellan start och slutpunkt. Ankomstgrad och tidseffektivitet beräknas och jämförs med den motsvarande optimala sökvägen. De experimentella resultaten visar att effektiviteten, dvs ankomstgraden av modellen är 90% och vägkvaliteten dvs tidseffektiviteten har en median på 0,88 och en stor varians. Experimentet visar att modellen har bättre prestanda i dynamiska grafer än i statiska grafer. Sammantaget är svaret på forskningsfrågan positivt. Det finns dock fortfarande utrymme att förbättra modellens effektivitet och de vägar som genereras av modellen. Detta arbete visar att ett neuronnätverk tränat för att göra lokalt optimala val knappast kan ge globalt optimal lösning. Vi visar också att vår metod, som bara gör lokalt optimala val, kan anpassa sig till dynamiska grafer med begränsad prestandaförlust.

Topographic maps are an invaluable tool for planning routes through unfamiliar terrain. However, accurately planning routes on topographic maps is a time- consuming and error-prone task. One factor is the difficulty of interpreting the map itself, which requires prior knowledge and practice. Another factor is the difficulty of making choices between possible routes that have different trade-offs between length and the terrain they traverse. To alleviate these difficulties, this thesis presents a system to automate the process of finding routes on scanned images of topographic maps. The system allows users to select any two points on a topographic map and identify their specific preferences for their route. This system extracts terrain and contour line data from topographic map images using image processing techniques and then uses the A* Search algorithm to find a route between the specified points. This system can be used as a starting point for hand-drawn routes, as a means of considering alternative routes, or to entirely replace drawing routes by hand. This thesis also presents a user study which shows that this system produces routes in a significantly shorter time than hand-drawn routes, and with a similar level of accuracy.

No description available.