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.

In this thesis, some novel ideas are presented for solving automated web service composition problem. Some possible real world problems such as partial observability of environment, nondeterministic effects of web services, service execution failures are solved through some mechanisms. In addition to automated web service composition, automated web service invocation task is handled in this thesis by using reflection mechanism. The proposed approach is based on AI planning. Web service composition problem is translated to AI planning problem and a novel AI planner namely &ldquo / Simplanner&rdquo / that is designed for working in highly dynamic environments under time constraints is adapted to the proposed system. World altering service calls are done by conforming to the WS-Coordination and WS-Business Activity web service transaction specifications in order to physically repair failure situations and prevent undesired side effects of aborted web service composition efforts.

In this thesis, some enhancements to an existing automatic web service composition and execution system are described which provide a practical significance to the existing framework with scalability, i.e. the ability to operate on large service sets in reasonable time. In addition, the service storage mechanism utilized in the enhanced system presents an effective method to maintain large service sets. The described enhanced system provides scalability by implementing a pre-processing phase that extracts service chains and problem initial and goal state dependencies from service descriptions. The service storage mechanism is used to store this extracted information and descriptions of available services. The extracted information is used in a forward chaining algorithm which selects the potentially useful services for a given composition problem and eliminates the irrelevant ones according to the given problem initial and goal states. Only the selected services are used during the AI planning and execution phases which generate the composition and execute the services respectively.

The factored state representation and concurrency semantics of Petri nets are closely related to those of classical planning models, yet automated planning and Petri net analysis have developed independently, with minimal and mainly unconvincing attempts at crossfertilisation. This thesis exploits the relationship between the formal reachability problem, and the automated planning problem, via Petri net unfolding, which is an attractive reachability analysis method for highly concurrent systems as it facilitates reasoning about independent sub-problems. The first contribution of this thesis is the theory of directed unfolding: controlling the unfolding process with informative strategies, for the purpose of optimality and increased efficiency. The second contribution is the application of directed unfolding to automated planning. Inspired by well-known planning heuristics, this thesis shows how problem specific information can be employed to guide unfolding, in response to the formal problem of developing efficient, directed reachability analysis methods for concurrent systems. Complimenting this theoretical work, this thesis presents a new forward search method for partial order planning which can be exponentially more efficient than state space search. Our suite of planners based on directed unfolding can perform optimal and suboptimal classical planning subject to arbitrary action costs, optimal temporal planning with respect to arbitrary action durations, and address probabilistic planning via replanning for the most likely path. Empirical results reveal directed unfolding is competitive with current state of the art automated planning systems, and can solve Petri net reachability problems beyond the reach of the original “blind” unfolding technique. / Thesis (Ph.D.) -- University of Adelaide, School of Electrical and Electronic Engineering, 2008

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.

Made available in DSpace on 2016-08-17T14:52:54Z (GMT). No. of bitstreams: 1 Carlos Roberto Baluz Almeida.pdf: 871522 bytes, checksum: 977790536a9b751306209d20d7242a1e (MD5) Previous issue date: 2004-12-17 / The ICS (Intelligent Commerce System), a developing project of the Intelligent Systems Lab (LSI) at Federal University of Maranhão (UFMA), under Prof. Dr. Sofiane Labidi´s supervision, is a project that has the objective of develop an Electronic Commerce System, in the B2B (Business to Business) category, effectively intelligent. It is based in the technology of intelligent mobile agents and has five phases in its life cycle: User Modeling, Matchmaking, Negotiation, Contract Formation and Contract Fulfillment. The Matchmaking is the process in which agents that represent traders (buyers and sellers), that are interested in the exchange of economic values, are put in touch with their potential business counterparts. The enrichment of the matchmaking process is the main focus of this work. Nowadays in the ICS, the matchmaking process only matches simple services. Our contribution is to enrich the actual matchmaking process allowing the composition of services, that is, simple services can add its capacities and form complex services with the goal to return a greater number of positive responses. To do this, we use ontologies allied to AI planning techniques to provide the discovery of complementary services and the posterior composition of them to elaborate more complex services. / O ICS (Intelligent Commerce System), projeto atualmente em desenvolvimento no Laboratório de Sistemas Inteligentes (LSI) na Universidade Federal do Maranhão (UFMA) sob a orientação do Prof. Dr. Sofiane Labidi, é um projeto que tem como objetivo desenvolver um Sistema de Comércio Eletrônico, na categoria B2B, efetivamente Inteligente. Ele é baseado na tecnologia de agentes móveis inteligentes e possui cinco fases no seu ciclo de vida: Modelagem do Usuário, Matchmaking, Negociação, Formação de Contrato e Cumprimento do Contrato. O Matchmaking é o processo no qual agentes representando negociantes (compradores e vendedores), que possuem interesse na troca de valores econômicos, são colocados em contato com seus potenciais parceiros de negócios. O enriquecimento do processo de matchmaking é o foco principal deste trabalho. Atualmente no ICS o processo de matchmaking somente emparceira serviços simples. Nossa contribuição é enriquecer o processo de matching atualmente em uso no ICS permitindo a composição de serviços, ou seja, serviços simples somam suas capacidades e formam serviços complexos com a finalidade de retornar maior número de respostas positivas. Para isso utilizamos ontologias aliadas às técnicas de planejamento automático para proporcionar a descoberta de serviços complementares e posterior composição dos mesmos para elaboração de serviços mais complexos.