Search

Recent advances in applying deep learning to planning have shown that Deep Reactive Policies (DRPs) can be powerful for fast decision-making in complex environments. However, an important limitation of current DRP-based approaches is either the need of optimal planners to be used as ground truth in a supervised learning setting or the sample complexity of high-variance policy gradient estimators, which are particularly troublesome in continuous state-action domains. In order to overcome those limitations, we introduce a framework for training DRPs in continuous stochastic spaces via gradient-based policy search. The general approach is to explicitly encode a parametric policy as a deep neural network, and to formulate the probabilistic planning problem as an optimization task in a stochastic computation graph by exploiting the re-parameterization of the transition probability densities; the optimization is then solved by leveraging gradient descent algorithms that are able to handle non-convex objective functions. We benchmark our approach against stochastic planning domains exhibiting arbitrary differentiable nonlinear transition and cost functions (e.g., Reservoir Control, HVAC and Navigation). Results show that DRPs with more than 125,000 continuous action parameters can be optimized by our approach for problems with 30 state fluents and 30 action fluents on inexpensive hardware under 6 minutes. Also, we observed a speedup of 5 orders of magnitude in the average inference time per decision step of DRPs when compared to other state-of-the-art online gradient-based planners when the same level of solution quality is required.

Planning problems with continuous state and action spaces are difficult to solve with existing planning techniques, specially when the state transition is defined by a high-dimension non-linear dynamics. Recently, a technique called Planning through Backpropagation (PtB) was introduced as an efficient and scalable alternative to traditional optimization-based methods for continuous planning problems. PtB leverages modern gradient descent algorithms and highly optimized automatic differentiation libraries to obtain approximate solutions. However, to date there have been no empirical evaluations comparing PtB with Linear-Quadratic (LQ) control problems. In this work, we compare PtB with an optimal algorithm from control theory called LQR, and its iterative version iLQR, when solving linear and non-linear continuous deterministic planning problems. The empirical results suggest that PtB can be an efficient alternative to optimizing non-linear continuous deterministic planning, being much easier to be implemented and stabilized than classical model-predictive control methods.

Policy gradient methods in deep reinforcement learning have received increasing attention over the last few years, mainly because of their several successful applications to challenging sequential decision-making tasks, such as playing Atari games from pixels and solving simulated robotics tasks. Several publically available benchmarks have enabled the development and evaluation of novel policy gradient methods; however, few incorporate environment stochasticities as a feature. We hypothesize that environments with stochastic dynamics may hinder the performance of these methods and propose an empirical analysis to evaluate so. We implement stochastic variations of a classic cartpole balancing task and select and implement three algorithms: Vanilla Policy Gradient, Natural Policy Gradient, and TRPO. Our results show that convergence in these environments is slower for all three algorithms and that policies obtained in the deterministic setting aren't useful even though the expected effect of each action is the same. We suggest that both further analyses of policy gradient algorithms in stochastic environments and new benchmarks that incorporate these tasks are necessary for better evaluating existing and novel solutions.

Planning with partial observation, an area called contingent planning, is a complex and challenging problem since it requires to keep track of belief states to search for a contingent plan of actions. Recent approaches considers the agent's knowledge about the world to compile a contingent planning problem into a full observable planning problem, described in an epistemic logic language, and then use an efficcient full observable planner to solve the translated problem. In this paper we use the concept of relevance and causality to propose a new translation based in a structure called Causal Graph that can improve the belief tracking task of contingent Planning problems described in a more general planning language, in particular problems envolving actions with uncertainty on its conditional effects.

A área de Robótica Cognitiva tem como principal objetivo desenvolver agentes robóticos capazes de realizar funções de alto-nível, especificando o programa de controle do robô em uma linguagem de programação baseada em lógica. Desta forma, é possível declarar e verificar propriedades do agente como prova de teoremas. Além disso, uma especificação feita em uma linguagem formal pode ser executável, o que permite simular o comportamento do agente através dessa especificação. Este artigo apresenta o desenvolvimento, passo a passo, de um agente para um robô Lego® MindStorms™, usando IndiGolog - uma linguagem para especificação de agentes baseada no Cálculo de Situações. Como exemplo de aplicação, foi escolhido o problema clássico do Mundo do Wumpus para o qual a construção de um agente completo envolve a integração das seguintes técnicas de: planejamento reativo, planejamento para satisfação de metas e realização de tarefas (planejamento hierárquico), execução de ações, raciocínio com informação incompleta, geração e raciocínio hipotético sobre o estado do mundo e mudanças de crença.

A rational agent exploring a complex and dynamic environment with incomplete information needs cognitive capabilities, e.g. planning, in addition to its perception and reaction for basic functionalities. However, mere planning, i.e., reasoning about sequences of actions, is not sufficient to solve problems in such complex environment. This is because (i) agents need to execute actions while they plan, (ii) they must gather and interpret sensor information, (iii) revise their world model, and (iv) adapt their own goals during a task. The knowledge representation and non monotonic reasoning area has shown the advantage of using logical formalisms to specify rational agents for complex robot applications, also called cognitive robotics applications. An example of such formalism is the Golog language and its different dialects. What those areas are still missing is implementational testbeds to evaluate existing theories. Since practical experimentation highlights the need for the improvement of existing formal theories at the ontological level. This work presents a logic-based implementation of an agent for the Wumpus World domain, which can be envisaged as a simplified model of an agent that reasons logically about its actions and sensor information in the presence of incomplete knowledge. Through a complete implementation of an agent in a real robot, the LegoMindStorm robot, we show some experiments to verify that the Wumpus World can be an implementational testbed used to identify difficulties in transforming theory into operational solutions.

It is not easy for a student to develop programming skills and learn how to construct their own problem solving algorithms. Well designed materials and tools can guide programming students knowledge and skill construction. Such tools may allow students to acquire better and faster, the necessary programming skills. In this paper we show the results of some experiments realized on a set of faulty student’s programs using ProPAT_deBUG, an automatic program debugger, based on the Model Based Diagnosis technique of Artificial Intelligence. The results show that during the interactive debugging process it is possible for a student to learn by answering the questions posed by the AI diagnosis system to discriminate its fault hypotheses.

Programming Patterns help create a shared language for communicating insight and experience about programming problems and their solutions. Inspired by this idea, we developed the PROPAT e-learning tool: an Eclipse IDE that allows students of a first Computer Science course to learn how to program using pedagogical patterns, i.e., a set of programming patterns recommended by Computer Science educators. PROPAT has been implemented as an Eclipse plugin with two main perspectives: the Teacher Perspective and the Student Perspective. To identify some of the students' mistakes, the PROPAT plug-in also includes a program diagnosis system that uses Model Based Diagnosis techniques from the Artificial Inteligence.

This paper proposes a new language that can be used to build high-level robot controllers with high-level cognitive functions such as plan specification, plan generation, plan execution, perception, goal formulation, communication and collaboration. The proposed language is based on Golog, a language that uses the situation calculus as a formalism to describe actions and deduction as an inference rule to synthesize plans. On the other hand, instead of situation calculus and deduction, the new language uses event calculus and abductive reasoning to synthesize plans. As we can forsee, this change of paradigm allows the agent to reason about partial order plans, making possible a more flexible integration between deliberative and reactive behaviors.

In this work we show how a planner implemented as an abductive reasoning process can have the same performance and behavior as classical planning algorithms. We demonstrate this result by considering three different versions of an abductive event calculus planner on reproducing some important comparative analyses of planning algorithms found in the literature. We argue that a logic-based planner, defined as the application of general purpose theorem proving techniques to a general purpose action formalism, can be a very solid base for the research on extending the classical planning approach.

Research on cognitive theories about programming learning suggests that experienced programmers solve problems by looking for previous solutions that are related to the new problem and that can be adapted to the current situation. Inspired by these ideas, programming teachers have developed a pattern based programming instruction. In this model, learning can be seen as a process of pattern recognition, which compares experiences from the past with the current situation. In this work, we present a new Eclipse programming environment in which a student can program using a set of pedagogical patterns, i.e., elementary programming patterns recommended by a group of teachers.

There are several works whose goal is to specify complete and sound planning systems based on general purpose theorem provers. Some planners implemented in this way can have a close correspondence with existing partial-ordered planning algorithms. To improve the efficiency of logic-based planners we would like to use some of the results achieved by the AI planning community over the past twenty years in terms of algorithm design. We claim that a knowledge level analysis of problem-solving methods for planning, can help to identify what is the role of each piece of knowledge in a system and provide a common language to map, classify and compare different systems. In this paper we analyze an abductive event calculus planner using a library of problem-solving methods for planning.

We propose a multi-agent vision-based architecture to solve complex sensor-based planning tasks. A test bed implementation, with skills such as vision and collision avoidance, was used to run experiments in the proposed architecture. We demonstrate experimentally how the system can execute successfully complex assembly plans while dealing with unpredictable events and imprecise information, with no significant cost in run-time efficiency. Such experiments provided important insights about vision and planning and on how to build real world robotic systems.

Esta dissertação tem como objetivo estudar a combinação de duas técnicas de planejamento em inteligência artificial: planejamento hierárquico e planejamento sob incerteza Knightiana. Cada uma delas possui vantagens distintas, mas que podem ser combinadas, permitindo um ganho de eficiência para o planejamento sob incerteza e maior robustez a planos gerados por planejadores hierárquicos. Primeiramente, estudamos um meio de efetuar uma transformação, de modo sistemático, que permite habilitar algoritmos de planejamento determinístico com busca progressiva no espaço de estados a tratar problemas com ações não-determinísticas, sem considerar a distribuição de probabilidades de efeitos das ações (incerteza Knightiana). Em seguida, esta transformação é aplicada a um algoritmo de planejamento hierárquico que efetua decomposição a partir das tarefas sem predecessoras, de modo progressivo. O planejador obtido é competitivo com planejadores que representam o estado-da-arte em planejamento sob incerteza, devido à informação adicional que pode ser fornecida ao planejador, na forma de métodos de decomposição de tarefas. This dissertation\'s objective is to study the combination of two artificial intelligence planning techniques, namely: hierarchical planning and planning under Knightian uncertainty. Each one of these has distinct advantages, but they can be combined, allowing the planning under uncertainty a performance gain and giving the hierarchical planning the ability to produce more robust plans. First, we study a way of performing a transformation, in a sistematic way, that enables forward-chaining deterministic planning algorithms to deal with non-deterministic actions, that doesn\'t take into account the probability distribution of actions\' effects (Knightian uncertainty). Afterwards, this transformation is applied to a hierarchical planning algorithm that progressively performs decomposition starting from tasks without predecessors. The obtained planner is competitive with state-of-the-art non-deterministic planners, thanks to the additional information that can be given to the planner, in the form of task decomposition methods.

Redes de Anúncios (Ad Networks) são redes que promovem a distribuição de anúncios pela internet, de forma a maximizar o lucro total gerado pela exibição dos anúncios nos websites. Estas redes tipicamente operam através do modelo de negócios chamado CPC (Custo por Clique), em que o anunciante paga um determinado valor somente se algum usuário clicar em seu anúncio. A escolha de como o intermediador planeja a distribuição dos anúncios aos websites é de extrema importância, já que a taxa de cliques nos anúncios é extremamente baixa. Atualmente a alocação dos anúncios tem sido feita através de uma solução aproximada baseada na alocação ótima definida com dados de um período anterior, a qual é calculada através de programação linear aliada à utilização de heurísticas. Entretanto, este sistema claramente é um processo de decisão sequencial em que diversas restrições são aplicáveis, como por exemplo: o orçamento dos anunciantes, limites mínimos do número de exibições de cada anúncio, categorias dos anúncios, entre outras. Neste trabalho argumenta-se que MDPs (Markov Decision Processes) fornecem uma melhor modelagem para o problema, já que conseguem levar em conta a dinâmica do sistema, considerando, por exemplo, que um anúncio que tem poucas chances de ser clicado consiga ser alocado de forma eficiente em relação ao retorno de longo prazo, mesmo quando outros anúncios proveriam um lucro maior a curto prazo. No entanto, devido ao grande número de estados, utilizar uma solução ótima através de MDPs é impraticável. Portanto analisa-se o desempenho relativo entre o estado da arte e a modelagem ótima, obtendo garantias de que a solução aproximada baseada em programação linear não está longe da solução ótima, e que em problemas grandes (similares aos encontrados na prática) essa diferença pode ser ignorada. Por fim, propõe-se uma modelagem baseada em aprendizado por reforço para a solução deste problema, utilizando duas abordagens, uma desconsiderando informações de contexto e outra considerando informações de contexto. Aqui argumenta-se que o uso de aprendizado por reforço é mais apropriado para a solução do problema de alocação de anúncios, já que ele é capaz de adaptar sua política de alocação em função das mudanças que ocorrem como, por exemplo, no perfil do usuário. Ad Networks promote the distribution of ads in the internet, so as to maximize the revenue generated by their display of ads in websites. These networks typically operate using the CPC (Cost per Click) business model, where the advertiser pays a monetary value when a user clicks in its advertisement. The choice of how the Ad Network distributes ads to websites is of utmost importance, since the rate of clicks on ads is extremely low. The allocation of ads has been done by an approximate solution based on data from an early period of time, which is calculated using linear programming combined with heuristics. However, this problem is clearly a sequential decision process in which multiple sequential restrictions apply, such as: the budget of the advertisers, minimum limits on the number of views for each campaign, categories of advertisements. In this dissertation we argue that MDPs (Markov Decision Processes) provide a better model for the problem, since they can automatically take into account the dynamics of the system, considering, for example, an ad with little chance of being clicked can be allocated in an efficient way, even when other ads would provide a higher profit in the short term. However, due to the large number of states, an optimal solution through MDPs is impractical; therefore we analyze here the relative performance between the linear programming and the MDP approaches, deriving guarantees that the approximate solution based on linear programming is not far from the MDP optimal solution, and in large problems (similar to those found in practice) this difference can be disregarded. Finally, we propose a model based on reinforcement learning using two different approaches, one disregarding the contextual information, and the other using contextual information. We argue that the use of reinforcement learning is more suitable for solving the problem of allocation of ads, since it is able to adapt its allocation policy to reflect changes that occur, e.g., in the user profile.

Além da capacidade de negociar, a atuação conjunta de agentes autônomos para resolver problemas complexos requer objetivos ao menos parcialmente compartilhados, de modo a tornar a cooperação atraente para tais agentes. Por outro lado, agentes competindo entre si podem trazer benefícios sociais, à medida que os mais aptos forem identificados e recursos sejam canalizados para aumentar sua relevância social e deste modo contribuir mais fortemente para a eficiência de todo o grupo. Dentro deste conceito, este trabalho apresenta uma arquitetura multiagentes que busca através da competição entre agentes com interesses comuns obter maior ganho social. Esta arquitetura, nomeada COAST, foi desenhada para o complexo ambiente que é a administração automatizada de ativos. Um sistema COAST é capaz de administrar uma carteira de ativos, utilizando um modelo explícito de perfil de investidor também proposto neste trabalho. Busca-se não apenas a maximização dos retornos, mas também um efetivo controle de risco e retorno, seguindo as restrições dadas pelo perfil do investidor. Um sistema de simulação de mercado financeiro, denominado AgEx, foi criado para facilitar o trabalho de desenvolver agentes para a administração de ativos e simular sua atuação através do uso de dados reais de negociações ocorridas em mercados financeiros. Foram realizadas várias simulações onde se pode observar que a arquitetura COAST se mostrou bastante eficaz no domínio escolhido In order to solve complex problems using several autonomous agents it is necessary that these agents present negotiation skills and share some common goals to make cooperation attractive. On the other hand, competition among agents may bring some social benefits, since the most effective agents can be identified and more resources could be associated to them, thus contributing better to the whole society. According to this idea, this work presents a multiagent architecture that tries to explore competition among agents with commons goals, as a way to achieve better social results. The architecture was named COAST and it was designed to manage assets in an autonomous way. COAST is able to manage assets using an explicit investor profile model that is also proposed in this work. COAST architecture tries not only to maximize profits but also an effective risk and return control, according to an investor profile. A financial market simulation tool, called AgEx, was also implemented. This tool may facilitate the development of agents to automated asset management and simulate their acting in stock markets was also developed. We have performed many simulated experiments to validate COAST and the obtained results show that the use of COAST architecture in this domain is quite effective.