Problematiken för vår undersökning grundar sig i den nya skollagen som trädde i kraft i juli 2011. Där står det reglerat att kommunen är ansvarig för alla elever i en kommun. Då det nu råder fritt skolval enligt den nya skollagen, kan elever och dess vårdnadshavare själva välja vilken grundskola de vill gå på. Eleverna kan antingen välja en kommunal grundskola eller en friskola och därmed blir planeringen och budgeteringen av elevantalet osäker för kommunerna då de inte vet hur många elever som kommer att gå i de olika skolorna. Vårt syfte med denna undersökning är att skapa förståelse för och en fördjupad kunskap om hur skolförvaltningen inom kommunen går tillväga för att planera och budgetera osäkerhet och om budgetarbetet har påverkats av det fria skolvalet och friskolorna. Undersökningen baseras på en kvalitativ metod med tre intervjuer av ekonomer på skolförvaltningen i tre kommuner; Helsingborgs stad, Lunds kommun och Kristianstads kommun. Utifrån det empiriska materialet har det framkommit att ledorden i budgetarbetet är; planering, kommunikation och kontroll. För att kunna budgetera för verksamheten som är oviss på grund av det osäkra elevantalet är dessa ledord viktiga i hela budgetarbetet, från förberedelser av budget till uppföljningen av budgetutfallet. Vad som har förändrats med införandet av det fria skolvalet och friskolorna är att det har blivit svårare att planera verksamheten och veta vilken skola som eleverna kommer att välja. Detta har medfört att behovet av långsiktig planering har blivit ännu viktigare och rektorerna har infört ett par tillvägagångssätt för att försöka ta reda på vilken skola eleverna kommer att välja. Det fria skolvalet och friskolorna har även bidragit till att kontrollen och själva uppföljningen har blivit än viktigare än det var tidigare. / The problem of our study is based on the new law of school which came into force in July 2011. In the law it is regulated that the municipality is responsible for all pupils in the municipality. Because of the new law of school the students and their guardians are free to choose which primary school they want to go to. Students can either choose a local school or an independent school and because of that planning and budgeting of the student population becomes more difficult for the municipalities when they do not know how many students will attend different schools. Our purpose in this study is to create an understanding and a deeper knowledge of how the school board in the municipality proceed in order to plan and budget uncertainty and if the budget has been affected by the free school choice and independent schools. This survey is based on a qualitative approach with interviews with economist on the school board in three municipalities; Helsingborgs’s city, Lund’s municipality and Kristianstad’s municipality. Based on the empirical material, it has emerged that the keywords in the budget are: planning, communication and control. To be able to budget for the schools which are uncertain because of the uncertain pupil numbers, these keywords are important throughout the whole budget process, from preparation of the budget to the monitoring of the budget. What has changed with the introduction of the free school choice and independent schools is that it becomes more difficult to plan for the schools and to know which school the students will choice. This has meant that long-term planning has become more important and principals have introduced a couple of approaches to attempt to find out at which school students will choice. The free school choice and independent schools have also contributed to the control and monitoring has become more important now than it was before.

Planning is an essential part of intelligent behavior and a ubiquitous task for both humans and rational agents. One framework for planning in the presence of uncertainty is probabilistic planning, in which actions are described by a probability distribution over their possible outcomes. Probabilistic planning has been applied to different real-world scenarios such as public health, sustainability and robotics; however, the usage of probabilistic planning in practice is limited due to the poor performance of existing planners. In this thesis, we introduce a novel approach to effectively solve probabilistic planning problems by relaxing them into short-sighted problems. A short-sighted problem is a relaxed problem in which the state space of the original problem is pruned and artificial goals are added to heuristically estimate the cost of reaching an original goal from the pruned states. Differently from previously proposed relaxations, short-sighted problems maintain the original structure of actions and no restrictions are imposed in the maximum number of actions that can be executed. Therefore, the solutions for short-sighted problems take into consideration all the probabilistic outcomes of actions and their probabilities. In this thesis, we also study different criteria to generate short-sighted problems, i.e., how to prune the state space, and the relation between the obtained short-sighted models and previously proposed relaxation approaches. We present different planning algorithms that use short-sighted problems in order to solve probabilistic planning problems. These algorithms iteratively generate and execute optimal policies for short-sighted problems until the goal of the original problem is reached. We also formally analyze the introduced algorithms, focusing on their optimality guarantees with respect to the original probabilistic problem. Finally, this thesis contributes a rich empirical comparison between our algorithms and state-of-the-art probabilistic planners.

Planejamento sob incerteza vem sendo cada vez mais requisitado em aplicações práticas de diversas áreas que eequerem soluções confiáveis para metas complexas. Em vista disso, nos últimos anos, algumas abordagens baseadas no uso de métodos formais para síntese automática de planos têm sido propostas na área de Planejamento em Inteligência Artificial. Entre essas abordagens, planejamento baseado em verificação de modelos tem se mostrado uma opção bastante promissora; entretanto, conforme observamos, a maioria dos trabalhos dentro dessa abordagem baseia-se em CTL e trata apenas problemas de planejamento para metas de alcançabilidade simples (como aquelas consideradas no planejamento clássico). Nessa tese, introduzimos uma classe de metas de planejamento mais expressivas (metas de alcançabilidade estendidas) e mostramos que, para essa classe de metas, a semântica de CTL não é adequada para formalizar algoritmos de síntese (ou validação) de planos. Como forma de contornar essa limitação, propomos uma nova versão de CTL, que denominamos alpha-CTL. Então, a partir da semântica dessa nova lógica, implementamos um verificador de modelos (Vactl), com base no qual implementamos também um planejador (Pactl) capaz de resolver problemas de planejamento para metas de alcançabilidade estendidas, em ambientes não-determinísticos com observabilidade completa. Finalmente, discutimos como garantir a qualidade das soluções quando dispomos de um modelo de ambiente onde as probabilidades das transições causadas pela execução das ações são conhecidas. / Planning under uncertainty has being increasingly demanded for practical applications in several areas that require reliable solutions for complex goals. In sight of this, in the last few years, some approaches based on formal methods for automatic synthesis of plans have been proposed in the area of Planning in Artificial Intelligence. Among these approaches, planning based on model checking seems to be a very attractive one; however, as we observe, the majority of the works in this approach are mainly based on CTL and deals only with planning problems for simple reachability goals (as those considered in classical planning). In this thesis, we introduce a more expressive class of planning goals (extended reachability goals) and show that, for this class of goals, the CTL\'s semantics is not adequate to formalize algorithms for synthesis (or validation) of plans. As a way to overcome this limitation, we propose a new version of CTL, called alpha-CTL. Then, based on the semantics of this new logic, we implement a model checker (Vactl), based on which we also implement a planner (Pactl) capable of solving planning problems for extended reachability goals, in nondeterministic planning environments with complete observability. Finally, we discuss how to guarantee the quality of the solutions when we have an environment model where the actions transitions probabilities are known.

The decentralized Markov decision process (Dec-POMDP) is a powerful formal model for studying multiagent problems where cooperative, coordinated action is optimal, but each agent acts based on local data alone. Unfortunately, it is known that Dec-POMDPs are fundamentally intractable: they are NEXP-complete in the worst case, and have been empirically observed to be beyond feasible optimal solution.To get around these obstacles, researchers have focused on special classes of the general Dec-POMDP problem, restricting the degree to which agent actions can interact with one another. In some cases, it has been proven that these sorts of structured forms of interaction can in fact reduce worst-case complexity. Where formal proofs have been lacking, empirical observations suggest that this may also be true for other cases, although less is known precisely.This thesis unifies a range of this existing work, extending analysis to establish novel complexity results for some popular restricted-interaction models. We also establish some new results concerning cases for which reduced complexity has been proven, showing correspondences between basic structural features and the potential for dimensionality reduction when employing mathematical programming techniques.As our new complexity results establish that worst-case intractability is more widespread than previously known, we look to new ways of analyzing the potential average-case difficulty of Dec-POMDP instances. As this would be extremely difficult using the tools of traditional complexity theory, we take a more empirical approach. In so doing, we identify new analytical measures that apply to all Dec-POMDPs, whatever their structure. These measures allow us to identify problems that are potentially easier to solve on average, and validate this claim empirically. As we show, the performance of well-known optimal dynamic programming methods correlates with our new measure of difficulty. Finally, we explore the approximate case, showing that our measure works well as a predictor of difficulty there, too, and provides a means of setting algorithm parameters to achieve far more efficient performance.

Promised some decades ago by researchers in artificial intelligence and robotics as an imminent breakthrough in our everyday lives, a robotic assistant that could work with us in our home and our workplace is a dream still far from being fulfilled. The work presented in this thesis aims at bringing this future vision a little closer to realization. Here, we start from the assumption that an efficient robotic helper should not impose constraints on users' activities, but rather perform its tasks unobtrusively to fulfill its goals and to facilitate people in achieving their objectives.  Also, the helper should be able to consider the outcome of possible future actions by the human users, to assess how those would affect the environment with respect to the agent's objectives, and to predict when its support will be needed. In this thesis we address two highly interconnected problems that are essential for the cohabitation of people and service robots: robot task planning and human activity recognition. First, we present human-aware planning, that is, our approach to robot high-level symbolic reasoning for plan generation. Human-aware planning can be applied in situations where there is a controllable agent, the robot, whose actions we can plan, and one or more uncontrollable agents, the human users, whose future actions we can only try to predict. In our approach, therefore, the knowledge of the users' current and future activities is an important prerequisite. We define human-aware as a new type of planning problem, we formalize the extensions needed by a classical planner to solve such a problem, and we present the implementation of a planner that satisfies all identified requirements. In this thesis we explore also a second issue, which is a prerequisite to the first one: human activity monitoring in intelligent environments. We adopt a knowledge driven approach to activity recognition, whereby a constraint-based domain description is used to correlate sensor readings to human activities. We validate our solutions to both human-aware planning and activity recognition both theoretically and experimentally, describing a number of explanatory examples and test runs in a real environment.

Markov decision processes (MDPs) have proven to be a useful model for sequential decision- theoretic reasoning under uncertainty, yet they require the specification of a reward function that can require sophisticated human judgement to assess relevant tradeoffs. This dissertation casts the problem of specifying rewards as one of preference elicitation and aims to minimize the degree of precision with which a reward function must be specified while still allowing optimal or near-optimal policies to be produced. We demonstrate how robust policies can be computed for MDPs given only partial reward information using the minimax regret criterion. Minimax regret offers an intuitive bound on loss; however, it is computationally intractable in general. This work develops techniques for exploiting MDP structure to allow for offline precomputation that enables efficient online minimax regret computation. To complement this exact approach we develop several general approximations that offer both upper and lower bounds on minimax regret. We further show how approximations can be improved online during the elicitation procedure to balance accuracy and efficiency. To effectively reduce regret, we investigate a spectrum of elicitation approaches that range from the computationally-demanding optimal selection of complex queries about full MDP policies (which are informative, but, we believe, cognitively difficult) to the heuristic selection of simple queries that focus on a small set of reward parameters. Results are demonstrated on MDPs drawn from the domains of assistive technology and autonomic computing. Finally we demonstrate our framework on a realistic website optimization domain, per- forming elicitation on websites with tens of thousands of webpages. We show that minimax regret can be efficiently computed, and develop informative and cognitively reasonable queries that quickly lower minimax regret, producing policies that offer significant improvement in the design of the underlying websites.

Planejamento sob incerteza vem sendo cada vez mais requisitado em aplicações práticas de diversas áreas que eequerem soluções confiáveis para metas complexas. Em vista disso, nos últimos anos, algumas abordagens baseadas no uso de métodos formais para síntese automática de planos têm sido propostas na área de Planejamento em Inteligência Artificial. Entre essas abordagens, planejamento baseado em verificação de modelos tem se mostrado uma opção bastante promissora; entretanto, conforme observamos, a maioria dos trabalhos dentro dessa abordagem baseia-se em CTL e trata apenas problemas de planejamento para metas de alcançabilidade simples (como aquelas consideradas no planejamento clássico). Nessa tese, introduzimos uma classe de metas de planejamento mais expressivas (metas de alcançabilidade estendidas) e mostramos que, para essa classe de metas, a semântica de CTL não é adequada para formalizar algoritmos de síntese (ou validação) de planos. Como forma de contornar essa limitação, propomos uma nova versão de CTL, que denominamos alpha-CTL. Então, a partir da semântica dessa nova lógica, implementamos um verificador de modelos (Vactl), com base no qual implementamos também um planejador (Pactl) capaz de resolver problemas de planejamento para metas de alcançabilidade estendidas, em ambientes não-determinísticos com observabilidade completa. Finalmente, discutimos como garantir a qualidade das soluções quando dispomos de um modelo de ambiente onde as probabilidades das transições causadas pela execução das ações são conhecidas. / Planning under uncertainty has being increasingly demanded for practical applications in several areas that require reliable solutions for complex goals. In sight of this, in the last few years, some approaches based on formal methods for automatic synthesis of plans have been proposed in the area of Planning in Artificial Intelligence. Among these approaches, planning based on model checking seems to be a very attractive one; however, as we observe, the majority of the works in this approach are mainly based on CTL and deals only with planning problems for simple reachability goals (as those considered in classical planning). In this thesis, we introduce a more expressive class of planning goals (extended reachability goals) and show that, for this class of goals, the CTL\'s semantics is not adequate to formalize algorithms for synthesis (or validation) of plans. As a way to overcome this limitation, we propose a new version of CTL, called alpha-CTL. Then, based on the semantics of this new logic, we implement a model checker (Vactl), based on which we also implement a planner (Pactl) capable of solving planning problems for extended reachability goals, in nondeterministic planning environments with complete observability. Finally, we discuss how to guarantee the quality of the solutions when we have an environment model where the actions transitions probabilities are known.

Cette thèse traite du problème où une équipe d'agents coopératifs et autonomes, évoluant dans un environnement stochastique partiellement observable, et œuvrant à la résolution d'une tâche complexe, doit modifier dynamiquement sa composition durant l'exécution de la tâche afin de s'adapter à l'évolution de celle-ci. Il s'agit d'un problème qui n'a été que peu étudié dans le domaine de la planification multi-agents. Pourtant, il existe de nombreuses situations où l'équipe d'agent mobilisée est amenée à changer au fil de l'exécution de la tâche.Nous nous intéressons plus particulièrement au cas où les agents peuvent décider d'eux-même de quitter ou de rejoindre l'équipe opérationnelle. Certaines fois, utiliser peu d'agents peut être bénéfique si les coûts induits par l'utilisation des agents sont trop prohibitifs. Inversement, il peut parfois être utile de faire appel à plus d'agents si la situation empire et que les compétences de certains agents se révèlent être de précieux atouts.Afin de proposer un modèle de décision qui permette de représenter ces situations, nous nous basons sur les processus décisionnels de Markov décentralisés et partiellement observables, un modèle standard utilisé dans le cadre de la planification multi-agents sous incertitude. Nous étendons ce modèle afin de permettre aux agents d'entrer et sortir du système. On parle alors de système ouvert. Nous présentons également deux algorithmes de résolution basés sur les populaires méthodes de recherche arborescente Monte-Carlo. Le premier de ces algorithmes nous permet de construire des politiques jointes séparables via des calculs de meilleures réponses successives, tandis que le second construit des politiques jointes non séparables en évaluant les équipes dans chaque situation via un système de classement Elo. Nous évaluons nos méthodes sur de nouveaux jeux de tests qui permettent de mettre en lumière les caractéristiques des systèmes ouverts. / This thesis addresses the problem where a team of cooperative and autonomous agents, working in a stochastic and partially observable environment towards solving a complex task, needs toe dynamically modify its structure during the process execution, so as to adapt to the evolution of the task. It is a problem that has been seldom studied in the field of multi-agent planning. However, there are many situations where the team of agents is likely to evolve over time.We are particularly interested in the case where the agents can decide for themselves to leave or join the operational team. Sometimes, using few agents can be for the greater good. Conversely, it can sometimes be useful to call on more agents if the situation gets worse and the skills of some agents turn out to be valuable assets.In order to propose a decision model that can represent those situations, we base upon the decentralized and partially observable Markov decision processes, the standard model for planning under uncertainty in decentralized multi-agent settings. We extend this model to allow agents to enter and exit the system. This is what is called agent openness. We then present two planning algorithms based on the popular Monte-Carlo Tree Search methods. The first algorithm builds separable joint policies by computing series of best responses individual policies, while the second algorithm builds non-separable joint policies by ranking the teams in each situation via an Elo rating system. We evaluate our methods on new benchmarks that allow to highlight some interesting features of open systems.

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.

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.