A large class of practical planning problems that require reasoning about uncertain outcomes, as well as tradeoffs among competing goals, can be modeled as Markov decision processes (MDPs). This model has been studied for over 60 years, and has many applications that range from stochastic inventory control and supply-chain planning, to probabilistic model checking and robotic control. Standard dynamic programming algorithms solve these problems for the entire state space. A more efficient heuristic search approach focuses computation on solving these problems for the relevant part of the state space only, given a start state, and using heuristics to identify irrelevant parts of the state space that can be safely ignored. This dissertation considers the heuristic search approach to this class of problems, and makes three contributions that advance this approach. The first contribution is a novel algorithm for solving MDPs that integrates the standard value iteration algorithm with branch-and-bound search. Called branch-and-bound value iteration, the new algorithm has several advantages over existing algorithms. The second contribution is the integration of recently-developed suboptimality bounds in heuristic search algorithm for MDPs, making it possible for iterative algorithms for solving these planning problems to detect convergence to a bounded-suboptimal solution. The third contribution is the evaluation and analysis of some techniques that are widely-used by state-of-the-art planning algorithms, the identification of some weaknesses of these techniques, and the development of a more efficient implementation of one of these techniques -- a solved-labeling procedure that speeds converge by leveraging a decomposition of the state-space graph of a planning problem into strongly-connected components. The new algorithms and techniques introduced in this dissertation are experimentally evaluated on a range of widely-used planning benchmarks.

Em geral, quando modelamos problemas de planejamento probabilístico do mundo real, usando o arcabouço de Processos de Decisão Markovianos (MDPs), é difícil obter uma estimativa exata das probabilidades de transição. A incerteza surge naturalmente na especificação de um domínio, por exemplo, durante a aquisição das probabilidades de transição a partir de um especialista ou de dados observados através de técnicas de amostragem, ou ainda de distribuições de transição não estacionárias decorrentes do conhecimento insuficiente do domínio. Com o objetivo de se determinar uma política robusta, dada a incerteza nas transições de estado, Processos de Decisão Markovianos com Probabilidades Imprecisas (MDP-IPs) têm sido usados para modelar esses cenários. Infelizmente, apesar de existirem diversos algoritmos de solução para MDP-IPs, muitas vezes eles exigem chamadas externas de rotinas de otimização que podem ser extremamente custosas. Para resolver esta deficiência, nesta tese, introduzimos o MDP-IP fatorado e propomos métodos eficientes de programação matemática e programação dinâmica que permitem explorar a estrutura de um domínio de aplicação. O método baseado em programação matemática propõe soluções aproximadas eficientes para MDP-IPs fatorados, estendendo abordagens anteriores de programação linear para MDPs fatorados. Essa proposta, baseada numa formulação multilinear para aproximações robustas da função valor de estados, explora a representação fatorada de um MDP-IP, reduzindo em ordens de magnitude o tempo consumido em relação às abordagens não-fatoradas previamente propostas. O segundo método proposto, baseado em programação dinâmica, resolve o gargalo computacional existente nas soluções de programação dinâmica para MDP-IPs propostas na literatura: a necessidade de resolver múltiplos problemas de otimização não-linear. Assim, mostramos como representar a função valor de maneira compacta usando uma nova estrutura de dados chamada de Diagramas de Decisão Algébrica Parametrizados, e como aplicar técnicas de aproximação para reduzir drasticamente a sobrecarga computacional das chamadas a um otimizador não-linear, produzindo soluções ótimas aproximadas com erro limitado. Nossos resultados mostram uma melhoria de tempo e até duas ordens de magnitude em comparação às abordagens tradicionais enumerativas baseadas em programação dinâmica e uma melhoria de tempo de até uma ordem de magnitude sobre a extensão de técnicas de iteração de valor aproximadas para MDPs fatorados. Além disso, produzimos o menor erro de todos os algoritmos de aproximação avaliados. / When modeling real-world decision-theoretic planning problems with the framework of Markov Decision Processes(MDPs), it is often impossible to obtain a completely accurate estimate of transition probabilities. For example, uncertainty arises in the specification of transitions due to elicitation of MDP transition models from an expert or data, or non-stationary transition distributions arising from insuficient state knowledge. In the interest of obtaining the most robust policy under transition uncertainty, Markov Decision Processes with Imprecise Transition Probabilities (MDP-IPs) have been introduced. Unfortunately, while various solutions exist for MDP-IPs, they often require external calls to optimization routines and thus can be extremely time-consuming in practice. To address this deficiency, we introduce the factored MDP-IP and propose eficient mathematical programming and dynamic programming methods to exploit its structure. First, we derive eficient approximate solutions for Factored MDP-IPs based on mathematical programming resulting in a multilinear formulation for robust maximin linear-value approximations in Factored MDP-IPs. By exploiting factored structure in MDP-IPs we are able to demonstrate orders of magnitude reduction in solution time over standard exact non-factored approaches. Second, noting that the key computational bottleneck in the dynamic programming solution of factored MDP-IPs is the need to repeatedly solve nonlinear constrained optimization problems, we show how to target approximation techniques to drastically reduce the computational overhead of the nonlinear solver while producing bounded, approximately optimal solutions. Our results show up to two orders of magnitude speedup in comparison to traditional at dynamic programming approaches and up to an order of magnitude speedup over the extension of factored MDP approximate value iteration techniques to MDP-IPs while producing the lowest error among all approximation algorithm evaluated.

Uncertainty is a feature of many AI applications. While there are polynomial-time algorithms for planning in stochastic systems, planning is still slow, in part because most algorithms plan for all eventualities. Algorithms such as LAO* are able to find good or optimal policies more quickly when the starting state of the system is known. In this thesis we present an extension to LAO*, called BLAO*. BLAO* is an extension of the LAO* algorithm to a bidirectional search. We show that BLAO* finds optimal or E-optimal solutions for goal-directed MDPs without necessarily evaluating the entire state space. BLAO* converges much faster than LAO* or RTDP on our benchmarks.

Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state and state transitions. While few practical problems are purely conformant, the ability to find conformant plans is needed in planning with observations where conformant situations are an special case and where relaxations into conformant planning yield useful heuristics. In this dissertation, we introduce new formulations for tackling the conformant planning problem with deterministic actions using translations. On the one hand, we propose a translation in propositional logic and two schemes for obtaning conformant plans for it, one based on boolean operations of projection and model counting, the other based on projection and satisfiability. On the other hand, we introduce translations of the conformant planning problem into classical problems that are solved by a modern and effective classical planner. We analyze the formal properties of the translations into classical planning and evaluate the performance of the resulting conformant planners. / La planificación conformante es el problema de encontrar una secuencia de acciones para lograr un objetivo en presencia de información incompleta sobre el estado inicial y en las transiciones entre estados. Aunque pocos problemas son de carácter puramente conformante, la posibilidad de encontrar planes conformantes es necesaria en planificación con observaciones, donde las situaciones conformantes son un caso particular, y donde las relajaciones a planificación conformante dan heurísticas útiles. En esta tesis atacamos el problema de la planificación conformante con acciones determinísticas mediante dos formulaciones basadas en traducciones. Por un lado, proponemos una traducción a lógica proposicional y dos esquemas para obtener planes conformantes a partir de ésta, uno basado en operaciones booleanas de projección y conteo de modelos, y otro basado en projección y satisfacción proposicional. Por otro lado, introducimos traducciones que permiten transformar un problema de planificación conformante en un problema de planificación clásica que es luego resuelto usando planificadores clásicos. También analizamos las propiedades formales de las traducciones y evaluamos el rendimiento de los planificadores obtenidos.

Em geral, quando modelamos problemas de planejamento probabilístico do mundo real, usando o arcabouço de Processos de Decisão Markovianos (MDPs), é difícil obter uma estimativa exata das probabilidades de transição. A incerteza surge naturalmente na especificação de um domínio, por exemplo, durante a aquisição das probabilidades de transição a partir de um especialista ou de dados observados através de técnicas de amostragem, ou ainda de distribuições de transição não estacionárias decorrentes do conhecimento insuficiente do domínio. Com o objetivo de se determinar uma política robusta, dada a incerteza nas transições de estado, Processos de Decisão Markovianos com Probabilidades Imprecisas (MDP-IPs) têm sido usados para modelar esses cenários. Infelizmente, apesar de existirem diversos algoritmos de solução para MDP-IPs, muitas vezes eles exigem chamadas externas de rotinas de otimização que podem ser extremamente custosas. Para resolver esta deficiência, nesta tese, introduzimos o MDP-IP fatorado e propomos métodos eficientes de programação matemática e programação dinâmica que permitem explorar a estrutura de um domínio de aplicação. O método baseado em programação matemática propõe soluções aproximadas eficientes para MDP-IPs fatorados, estendendo abordagens anteriores de programação linear para MDPs fatorados. Essa proposta, baseada numa formulação multilinear para aproximações robustas da função valor de estados, explora a representação fatorada de um MDP-IP, reduzindo em ordens de magnitude o tempo consumido em relação às abordagens não-fatoradas previamente propostas. O segundo método proposto, baseado em programação dinâmica, resolve o gargalo computacional existente nas soluções de programação dinâmica para MDP-IPs propostas na literatura: a necessidade de resolver múltiplos problemas de otimização não-linear. Assim, mostramos como representar a função valor de maneira compacta usando uma nova estrutura de dados chamada de Diagramas de Decisão Algébrica Parametrizados, e como aplicar técnicas de aproximação para reduzir drasticamente a sobrecarga computacional das chamadas a um otimizador não-linear, produzindo soluções ótimas aproximadas com erro limitado. Nossos resultados mostram uma melhoria de tempo e até duas ordens de magnitude em comparação às abordagens tradicionais enumerativas baseadas em programação dinâmica e uma melhoria de tempo de até uma ordem de magnitude sobre a extensão de técnicas de iteração de valor aproximadas para MDPs fatorados. Além disso, produzimos o menor erro de todos os algoritmos de aproximação avaliados. / When modeling real-world decision-theoretic planning problems with the framework of Markov Decision Processes(MDPs), it is often impossible to obtain a completely accurate estimate of transition probabilities. For example, uncertainty arises in the specification of transitions due to elicitation of MDP transition models from an expert or data, or non-stationary transition distributions arising from insuficient state knowledge. In the interest of obtaining the most robust policy under transition uncertainty, Markov Decision Processes with Imprecise Transition Probabilities (MDP-IPs) have been introduced. Unfortunately, while various solutions exist for MDP-IPs, they often require external calls to optimization routines and thus can be extremely time-consuming in practice. To address this deficiency, we introduce the factored MDP-IP and propose eficient mathematical programming and dynamic programming methods to exploit its structure. First, we derive eficient approximate solutions for Factored MDP-IPs based on mathematical programming resulting in a multilinear formulation for robust maximin linear-value approximations in Factored MDP-IPs. By exploiting factored structure in MDP-IPs we are able to demonstrate orders of magnitude reduction in solution time over standard exact non-factored approaches. Second, noting that the key computational bottleneck in the dynamic programming solution of factored MDP-IPs is the need to repeatedly solve nonlinear constrained optimization problems, we show how to target approximation techniques to drastically reduce the computational overhead of the nonlinear solver while producing bounded, approximately optimal solutions. Our results show up to two orders of magnitude speedup in comparison to traditional at dynamic programming approaches and up to an order of magnitude speedup over the extension of factored MDP approximate value iteration techniques to MDP-IPs while producing the lowest error among all approximation algorithm evaluated.

Les robots vont être de plus en plus utilisés dans les domaines civils, comme dans le domaine militaire. Ces robots, opérant en flottes, peuvent accompagner des soldats au combat, ou accomplir une mission en étant supervisés par un poste de contrôle. Du fait des exigences d'une opération militaire, il est difficile de laisser les robots décider de leurs actions sans accord d'un opérateur ou surveillance, en fonction de la situation. Dans cette thèse, nous nous attardons sur deux problématiques:D'une part, nous cherchons à exploiter l'autonomie ajustable de sorte à ce qu'un robot puisse accomplir sa mission de la manière la plus efficace possible, tout en respectant des restrictions assignées par un opérateur sur son niveau d'autonomie. Pour cela, celui-ci est en mesure de définir pour un ensemble d'états et d'actions donné un niveau de restriction. Ce niveau peut par exemple imposer au robot la télé-opération pour accéder à une zone à risque.D'autre part, comme nous envisageons la possibilité que plusieurs robots soient déployés en même temps, ces robots doivent se coordonner pour accomplir leurs objectifs. Seulement, comme les opérateurs peuvent prendre le contrôle de certains d'entre eux, la question de la coordination se pose. En effet, l'opérateur ayant ses propres préférences, perception de l'environnement, connaissances et étant sujet aux stress, hésitations, il est difficile de prévoir les actions que celui-ci va effectuer, et donc de s'y coordonner. Nous proposerons dans cette thèse une approche visant à estimer la politique exécutée par un robot télé-opéré à partir d'apprentissage basé sur les actions observés de ce robot.La notion de planification est très présente dans ces travaux. Ceux-ci se baseront sur des modèles de planifications comme les Processus Décisionnels de Markov. / Robots will be more and more used in both civil and military fields. These robots, operating in fleet, can accompany soldiers in fight, or accomplish a mission while being supervised by a control center. Considering the requirement of a military operation, it is complicated to let robots decide their action without an operator agreement or watch, in function of the situation.In this thesis, we focus on two problematics:First, we try to exploit adjustable autonomy to make a robot accomplishes is mission as efficiency as possible, while he respects restrictions, assigned by an operator, on his autonomy level. For this, it is able to define for given sets of states and actions a restriction level. This restriction can force, for example, the need of being tele-operated to access a dangerous zone.Secondly, we consider that several robots can be deployed at the same time. These robots have to coordinate to accomplish their objectives. However, since operators can take the control of some robots, the coordination is harder. In fact, the operator has preferences, perception, hesitation, stress that are not modeled by the agent. It is then hard to estimate his next actions, so to coordinate with him. We propose in this thesis an approach to estimate the policy executed by a tele-operated robot from learning methods, based on observed actions from this robot.The notion of planning his important in these works. These are based on planning models, such as Markov Decision Processes.

Industrial automation systems normally consist of four different hierarchy levels: planning, scheduling, real-time optimization, and control. At the planning level, the goal is to compute an optimal production plan that minimizes the production cost while meeting process constraints. The planning model is typically formulated as a mixed integer nonlinear programming (MINLP), which is hard to solve to global optimality due to nonconvexity and large dimensionality attributes. Uncertainty in component qualities in gasoline blending due to measurement errors and variation in upstream processes may lead to off-specification products which require re-blending. Uncertainty in product demands may lead to a suboptimal solution and fail in capturing some potential profit due to shortage in products supply. While incorporating process uncertainties is essential to reducing the production cost and increasing profitability, it comes with the disadvantage of increasing the complexity of the MINLP planning model. The key contribution in the planning level is to employ the inventory pinch decomposition method to consider uncertainty in components qualities and products demands to reduce the production cost and increase profitability of the gasoline blend application. At the control level, the goal is to ensure desired operation conditions by meeting process setpoints, ensure process safety, and avoid process failures. Model predictive control (MPC) is an advanced control strategy that utilizes a dynamic model of the process to predict future process dynamic behavior over a time horizon. The effectiveness of the MPC relies heavily on the availability of a reasonably accurate process model. The key contributions in the control level are: (1) investigate the use of different system identification methods for the purpose of developing a dynamic model for high-purity distillation column, which is a highly nonlinear process. (2) Develop a novel hybrid based MPC to improve the control of the column and achieve flooding-free control. / Dissertation / Doctor of Philosophy (PhD) / The operation of a chemical process involves many decisions which are normally distributed into levels referred to as process automation hierarchy. The process automation hierarchy levels are planning, scheduling, real-time optimization, and control. This thesis addresses two of the levels in the process automation hierarchy, which are planning and control. At the planning level, the objective is to ensure optimal utilization of raw materials and equipment to reduce production cost. At the control level, the objective is to meet and follow process setpoints determined by the real-time optimization level. The main goals of the thesis are: (1) develop an efficient algorithm to solve a large-scale planning problem that incorporates uncertainties in components qualities and products demands to reduce the production cost and maximize profit for gasoline blending application. (2) Develop a novel hybrid-based model predictive control to improve the control strategy of an industrial distillation column that faces flooding issues.

Planning is the sub-area of artificial intelligence that studies the process of selecting actions to lead an agent, e.g. a robot or a softbot, to a goal state. In many realistic scenarios, any choice of actions can lead the robot into a dead-end state, that is, a state from which the goal cannot be reached. In such cases, the robot can, pro-actively, resort to human help in order to reach the goal, an approach called symbiotic autonomy. In this work, we propose two different approaches to tackle this problem: (I) contingent planning, where the initial state is partially observable, configuring a belief state, and the outcomes of the robot actions are non-deterministic; and (II) probabilistic planning, where the initial state may be partially or totally observable and the actions have probabilistic outcomes. In both approaches, the human help is considered a scarce resource that should be used only when necessary. In contingent planning, the problem is to find a policy (a function mapping belief states into actions) that: (i) guarantees the agent will always reach the goal (strong policy); (ii) guarantees that the agent will eventually reach the goal (strong cyclic policy), or (iii) does not guarantee achieving the goal (weak policy). In this scenario, we propose a contingent planning system that considers human help to transform weak policies into strong (cyclic) policies. To do so, two types of human help are included: (i) human actions that modify states and/or belief states; and (ii) human observations that modify belief states. In probabilistic planning, the problem is to find a policy (a function mapping between world states and actions) that can be one of these two types: a proper policy, where the agent has probability 1 of reaching the goal; or an improper policy, in the case of unavoidable dead-ends. In general, the goal of the agent is to find a policy that minimizes the expected accumulated cost of the actions while maximizes the probability of reaching the goal. In this scenario, this work proposes probabilistic planners that consider human help to transform improper policies into proper policies however, considering two new (alternative) criteria: either to minimize the probability of using human actions or to minimize the expected number of human actions. Furthermore, we show that optimal policies under these criteria can be efficiently computed either by increasing human action costs or given a penalty when a human help is used. Solutions proposed in both scenarios, contingent planning and probabilistic planning with human help, were evaluated over a collection of planning problems with dead-ends. The results show that: (i) all generated policies (strong (cyclic) or proper) include human help only when necessary; and (ii) we were able to find policies for contingent planning problems with up to 10^15000 belief states and for probabilistic planning problems with more than 3*10^18 physical states. / Planejamento é a subárea de Inteligência Artificial que estuda o processo de selecionar ações que levam um agente, por exemplo um robô, de um estado inicial a um estado meta. Em muitos cenários realistas, qualquer escolha de ações pode levar o robô para um estado que é um beco-sem-saída, isto é, um estado a partir do qual a meta não pode ser alcançada. Nestes casos, o robô pode, pró-ativamente, pedir ajuda humana para alcançar a meta, uma abordagem chamada autonomia simbiótica. Neste trabalho, propomos duas abordagens diferentes para tratar este problema: (I) planejamento contingente, em que o estado inicial é parcialmente observável, configurando um estado de crença, e existe não-determinismo nos resultados das ações; e (II) planejamento probabilístico, em que o estado inicial é totalmente observável e as ações tem efeitos probabilísticos. Em ambas abordagens a ajuda humana é considerada um recurso escasso e deve ser usada somente quando estritamente necessária. No planejamento contingente, o problema é encontrar uma política (mapeamento entre estados de crença e ações) com: (i) garantia de alcançar a meta (política forte); (ii) garantia de eventualmente alcançar a meta (política forte-cíclica), ou (iii) sem garantia de alcançar a meta (política fraca). Neste cenário, uma das contribuições deste trabalho é propor sistemas de planejamento contingente que considerem ajuda humana para transformar políticas fracas em políticas fortes (cíclicas). Para isso, incluímos ajuda humana de dois tipos: (i) ações que modificam estados do mundo e/ou estados de crença; e (ii) observações que modificam estados de crenças. Em planejamento probabilístico, o problema é encontrar uma política (mapeamento entre estados do mundo e ações) que pode ser de dois tipos: política própria, na qual o agente tem probabilidade 1 de alcançar a meta; ou política imprópria, caso exista um beco-sem-saída inevitável. O objetivo do agente é, em geral, encontrar uma política que minimize o custo esperado acumulado das ações enquanto maximize a probabilidade de alcançar a meta. Neste cenário, este trabalho propõe sistemas de planejamento probabilístico que considerem ajuda humana para transformar políticas impróprias em políticas próprias, porém considerando dois novos critérios: minimizar a probabilidade de usar ações do humano e minimizar o número esperado de ações do humano. Mostramos ainda que políticas ótimas sob esses novos critérios podem ser computadas de maneira eficiente considerando que ações humanas possuem um custo alto ou penalizando o agente ao pedir ajuda humana. Soluções propostas em ambos cenários, planejamento contingente e planejamento probabilístico com ajuda humana, foram empiricamente avaliadas sobre um conjunto de problemas de planejamento com becos-sem-saida. Os resultados mostram que: (i) todas as políticas geradas (fortes (cíclicas) ou próprias) incluem ajuda humana somente quando necessária; e (ii) foram encontradas políticas para problemas de planejamento contingente com até 10^15000 estados de crença e para problemas de planejamento probabilístico com até 3*10^18 estados do mundo.

Les Processus Décisionnels de Markov Partiellement Observables (PDMPOs) permettent de modéliser facilement lesproblèmes probabilistes de décision séquentielle dans l'incertain. Lorsqu'il s'agit d'une mission robotique, lescaractéristiques du robot et de son environnement nécessaires à la définition de la mission constituent le système. Son étatn'est pas directement visible par l'agent (le robot). Résoudre un PDMPO revient donc à calculer une stratégie qui remplit lamission au mieux en moyenne, i.e. une fonction prescrivant les actions à exécuter selon l'information reçue par l'agent. Cetravail débute par la mise en évidence, dans le contexte robotique, de limites pratiques du modèle PDMPO: ellesconcernent l'ignorance de l'agent, l'imprécision du modèle d'observation ainsi que la complexité de résolution. Unhomologue du modèle PDMPO appelé pi-PDMPO, simplifie la représentation de l'incertitude: il vient de la Théorie desPossibilités Qualitatives qui définit la plausibilité des événements de manière qualitative, permettant la modélisation del'imprécision et de l'ignorance. Une fois les modèles PDMPO et pi-PDMPO présentés, une mise à jour du modèle possibilisteest proposée. Ensuite, l'étude des pi-PDMPOs factorisés permet de mettre en place un algorithme appelé PPUDD utilisantdes Arbres de Décision Algébriques afin de résoudre plus facilement les problèmes structurés. Les stratégies calculées parPPUDD, testées par ailleurs lors de la compétition IPPC 2014, peuvent être plus efficaces que celles des algorithmesprobabilistes dans un contexte d'imprécision ou de grande dimension. Cette thèse propose d'utiliser les possibilitésqualitatives dans le but d'obtenir des améliorations en termes de temps de calcul et de modélisation. / Partially Observable Markov Decision Processes (POMDPs) define a useful formalism to express probabilistic sequentialdecision problems under uncertainty. When this model is used for a robotic mission, the system is defined as the featuresof the robot and its environment, needed to express the mission. The system state is not directly seen by the agent (therobot). Solving a POMDP consists thus in computing a strategy which, on average, achieves the mission best i.e. a functionmapping the information known by the agent to an action. Some practical issues of the POMDP model are first highlightedin the robotic context: it concerns the modeling of the agent ignorance, the imprecision of the observation model and thecomplexity of solving real world problems. A counterpart of the POMDP model, called pi-POMDP, simplifies uncertaintyrepresentation with a qualitative evaluation of event plausibilities. It comes from Qualitative Possibility Theory whichprovides the means to model imprecision and ignorance. After a formal presentation of the POMDP and pi-POMDP models,an update of the possibilistic model is proposed. Next, the study of factored pi-POMDPs allows to set up an algorithmnamed PPUDD which uses Algebraic Decision Diagrams to solve large structured planning problems. Strategies computedby PPUDD, which have been tested in the context of the competition IPPC 2014, can be more efficient than those producedby probabilistic solvers when the model is imprecise or for high dimensional problems. This thesis proposes some ways ofusing Qualitative Possibility Theory to improve computation time and uncertainty modeling in practice.

The thesis is that automation of en-route Air Traffic Management in high complexity airspace can be achieved with a combination of automated tactic planning in a look-ahead time horizon of up to two hours complemented with automated tactic conflict resolution functions. The literature review reveals that no significant results have yet been obtained and that full automation could be approached with a complementary integration of automated tactic resolutions AND planning. The focus shifts to ‘planning for capacity’ and ‘planning for resolution’ and also – but not only – for ‘resolution’. The work encompasses a theoretical part on planning, and several small scale studies of empirical, mathematical or simulated nature. The theoretical part of the thesis on planning under uncertainties attempts to conceive a theoretical model which abstracts specificities of planning in Air Traffic Management into a generic planning model. The resulting abstract model treats entities like the planner, the strategy, the plan and the actions, always considering the impact of uncertainties. The work innovates in specifying many links from the theory to the application in planning of air traffic management, and especially the new fields of tactical capacity management. The second main part of the thesis comprises smaller self-containing works on different aspects of the concept grouped into a section on complexity, another on tactic planning actions, and the last on planners. The produced studies are about empirical measures of conflicts and conflict densities to get a better understanding of the complexity of air traffic; studies on traffic organisation using tactical manoeuvres like speed control, lateral offset and tactical direct using fast time simulation; and studies on airspace design like sector optimisation, dynamic sectorisation and its optimisation using optimisation techniques. In conclusion it is believed that this work will contribute to further automation attempts especially by its innovative focus which is on planning, base on a theory of planning, and its findings already influence newer developments.