Página 1 dos resultados de 1073 itens digitais encontrados em 0.009 segundos

Estudo e implementação de um método de cinemática inversa baseado em busca heurística para robôs manipuladores : aplicação em robôs redundantes e controle servo visual; Heuristic search based inverse kinematics for robotic manipulators : application to redundant robots and visual servoing

Fabricio Nicolato
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 01/06/2007 PT
Relevância na Pesquisa
56.21%
Esta tese trata o problema da resolução do modelo cinemático inverso para manipuladores industriais redundantes ou não. O problema foi abordado por um método de busca heurística no qual a solução da cinemática inversa é construída passo a passo calculando-se a contribuição do movimento de apenas uma junta a cada iteração. Dessa forma, o problema n-dimensional é transformado em problemas unidimensionais mais simples, cuja solução analítica tanto para juntas rotacionais quanto para juntas prismáticas é apresentada em termos da representação de Denavit-Hartenberg. O método proposto não possui singularidades internas. Além disso, o método foi expandido para incorporar informações de sensores externos visando fazer com que o processo seja mais robusto a incertezas nas modelagens envolvidas. Foram realizadas diversas simulações e comparações com técnicas tradicionais que evidenciaram as vantagens da abordagem proposta. O trabalho também englobou o projeto e a construção de um ambiente experimental e a implementação das técnicas desenvolvidas na parte teórica. Desenvolveu-se um sistema com um robô planar redundante de 3 DOF, assim como seus sistemas de controle, acionamento e interfaceamento usando técnicas de sistemas hardware-inthe-loop e lógica programável. As técnicas desenvolvidas foram aplicadas no ambiente experimental demonstrando características como: facilidade de lidar com redundâncias...

Symbolic search and abstraction heuristics for cost-optimal planning in automated planning

Torralba Arias de Reyna, Álvaro
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Tese de Doutorado
ENG
Relevância na Pesquisa
46.54%
La Planificación Automática puede ser definida como el problema de encontrar una secuencia de acciones (un plan) para conseguir una meta, desde un punto inicial, asumiendo que las acciones tienen efectos deterministas. La Planificación Automática es independiente de dominio porque los planificadores toman como información inicial una descripción del problema y deben resolverlo sin ninguna información adicional. Esta tesis trata en particular de planificación automática ´optima, en la cual las acciones tienen un coste asociado. Los planificadores óptimos deben encontrar un plan y probar que no existe ningún otro plan de menor coste. La mayoría de los planificadores óptimos están basados en la búsqueda de estados explícita. Sin lugar a dudas, esta aproximación ha sido la dominante en planificación automática óptima durante los últimos años. No obstante, la búsqueda simbólica se presenta como una alternativa interesante. En esta tesis, proponemos dos mejoras ortogonales para la planificación basada en búsqueda simbólica. En primer lugar, estudiamos diferentes métodos para mejorar la computación de la “imagen”, operación que calcula el conjunto de estados sucesores a partir de un conjunto de estados. Posteriormente...

A case-based approach to heuristic planning

Rosa Turbides, Tomás Eduardo de la; García-Olaya, Ángel; Borrajo Millán, Daniel
Fonte: Springer Publicador: Springer
Tipo: info:eu-repo/semantics/acceptedVersion; info:eu-repo/semantics/article
Publicado em /01/2013 ENG
Relevância na Pesquisa
46.45%
Most of the great success of heuristic search as an approach to AI Planning is due to the right design of domain-independent heuristics. Although many heuristic planners perform reasonably well, the computational cost of computing the heuristic function in every search node is very high, causing the planner to scale poorly when increasing the size of the planning tasks. For tackling this problem, planners can incorporate additional domain-dependent heuristics in order to improve their performance. Learning-based planners try to automatically acquire these domain-dependent heuristics using previous solved problems. In this work, we present a case-based reasoning approach that learns abstracted state transitions that serve as domain control knowledge for improving the planning process. The recommendations from the retrieved cases are used as guidance for pruning or ordering nodes in different heuristic search algorithms applied to planning tasks. We show that the CBR guidance is appropriate for a considerable number of planning benchmarks.; This work has been partially supported by the Spanish MEC projects PELEA: TIN2008-6701-C03-03 and PlanInteraction: TIN2011-27652-C03-02.

Heuristic Search in Bounded-depth Trees: Best-Leaf-First Search

Ruml, Wheeler
Fonte: Harvard University Publicador: Harvard University
Tipo: Research Paper or Report
EN_US
Relevância na Pesquisa
46.32%
Many combinatorial optimization and constraint satisfaction problems can be formulated as a search for the best leaf in a tree of bounded depth. When exhaustive enumeration is infeasible, a rational strategy visits leaves in increasing order of predicted cost. Previous systematic algorithms for this setting follow a predetermined search order, making strong implicit assumptions about predicted cost and using problem-specific information inefficiently. We introduce a framework, best-leaf-first search (BLFS), that employs an explicit model of leaf cost. BLFS is complete and visits leaves in an order that efficiently approximates increasing predicted cost. Different algorithms can be derived by incorporating different sources of information into the cost model. We show how previous algorithms are special cases of BLFS. We also demonstrate how BLFS can derive a problem-specific model during the search itself. Empirical results on latin square completion, binary CSPs, and number partitioning problems suggest that, even with simple cost models, BLFS yields competitive or superior performance and is more robust than previous methods. BLFS can be seen as a model=based extension of iterative-deepening A*, and thus it unifies search for combinatorial optimization and constraint satisfaction with traditional AI heuristic search for shortest-path problems.; Engineering and Applied Sciences

Domain-independent construction of pattern database heuristics for cost-optimal planning

Haslum, Patrik; Botea, Adi; Helmert, Malte; Bonet, Blai; Koenig, Sven
Fonte: AAAI Press Publicador: AAAI Press
Tipo: Conference paper
Relevância na Pesquisa
46.35%
Heuristic search is a leading approach to domain-independent planning. For cost-optimal planning, however, existing admissible heuristics are generally too weak to effectively guide the search. Pattern database heuristics (PDBs), which are based on abstra

On Backtracking in Real-time Heuristic Search

Bulitko, Valeriy K.; Bulitko, Vadim
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 16/12/2009
Relevância na Pesquisa
46.44%
Real-time heuristic search algorithms are suitable for situated agents that need to make their decisions in constant time. Since the original work by Korf nearly two decades ago, numerous extensions have been suggested. One of the most intriguing extensions is the idea of backtracking wherein the agent decides to return to a previously visited state as opposed to moving forward greedily. This idea has been empirically shown to have a significant impact on various performance measures. The studies have been carried out in particular empirical testbeds with specific real-time search algorithms that use backtracking. Consequently, the extent to which the trends observed are characteristic of backtracking in general is unclear. In this paper, we present the first entirely theoretical study of backtracking in real-time heuristic search. In particular, we present upper bounds on the solution cost exponential and linear in a parameter regulating the amount of backtracking. The results hold for a wide class of real-time heuristic search algorithms that includes many existing algorithms as a small subclass.

mGPT: A Probabilistic Planner Based on Heuristic Search

Bonet, B.; Geffner, H.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 09/09/2011
Relevância na Pesquisa
46.31%
We describe the version of the GPT planner used in the probabilistic track of the 4th International Planning Competition (IPC-4). This version, called mGPT, solves Markov Decision Processes specified in the PPDDL language by extracting and using different classes of lower bounds along with various heuristic-search algorithms. The lower bounds are extracted from deterministic relaxations where the alternative probabilistic effects of an action are mapped into different, independent, deterministic actions. The heuristic-search algorithms use these lower bounds for focusing the updates and delivering a consistent value function over all states reachable from the initial state and the greedy policy.

Avoiding and Escaping Depressions in Real-Time Heuristic Search

Hernández, Carlos; Baier, Jorge A
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 22/01/2014
Relevância na Pesquisa
46.58%
Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is inaccurate compared to the actual cost to reach a solution. Early real-time search algorithms, like LRTA*, easily become trapped in those regions since the heuristic values of their states may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms, like LSS-LRTA* or LRTA*(k), improve LRTA*s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We propose two ways in which depression avoidance can be implemented: mark-and-avoid and move-to-border. We implement these strategies on top of LSS-LRTA* and RTAA*, producing 4 new real-time heuristic search algorithms: aLSS-LRTA*, daLSS-LRTA*, aRTAA*, and daRTAA*. When the objective is to find a single solution by running the real-time search algorithm once, we show that daLSS-LRTA* and daRTAA* outperform their predecessors sometimes by one order of magnitude. Of the four new algorithms...

MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs

Szer, Daniel; Charpillet, Francois; Zilberstein, Shlomo
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/07/2012
Relevância na Pesquisa
46.31%
We present multi-agent A* (MAA*), the first complete and optimal heuristic search algorithm for solving decentralized partially-observable Markov decision problems (DEC-POMDPs) with finite horizon. The algorithm is suitable for computing optimal plans for a cooperative group of agents that operate in a stochastic environment such as multirobot coordination, network traffic control, `or distributed resource allocation. Solving such problems efiectively is a major challenge in the area of planning under uncertainty. Our solution is based on a synthesis of classical heuristic search and decentralized control theory. Experimental results show that MAA* has significant advantages. We introduce an anytime variant of MAA* and conclude with a discussion of promising extensions such as an approach to solving infinite horizon problems.; Comment: Appears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)

A Heuristic Search Algorithm for Solving First-Order MDPs

Karabaev, Eldar; Skvortsova, Olga
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 09/08/2014
Relevância na Pesquisa
46.41%
We present a heuristic search algorithm for solving first-order MDPs (FOMDPs). Our approach combines first-order state abstraction that avoids evaluating states individually, and heuristic search that avoids evaluating all states. Firstly, we apply state abstraction directly on the FOMDP avoiding propositionalization. Such kind of abstraction is referred to as firstorder state abstraction. Secondly, guided by an admissible heuristic, the search is restricted only to those states that are reachable from the initial state. We demonstrate the usefullness of the above techniques for solving FOMDPs on a system, referred to as FCPlanner, that entered the probabilistic track of the International Planning Competition (IPC'2004).; Comment: Appears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)

Multiple-Goal Heuristic Search

Davidov, D.; Markovitch, S.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 29/09/2011
Relevância na Pesquisa
46.44%
This paper presents a new framework for anytime heuristic search where the task is to achieve as many goals as possible within the allocated resources. We show the inadequacy of traditional distance-estimation heuristics for tasks of this type and present alternative heuristics that are more appropriate for multiple-goal search. In particular, we introduce the marginal-utility heuristic, which estimates the cost and the benefit of exploring a subtree below a search node. We developed two methods for online learning of the marginal-utility heuristic. One is based on local similarity of the partial marginal utility of sibling nodes, and the other generalizes marginal-utility over the state feature space. We apply our adaptive and non-adaptive multiple-goal search algorithms to several problems, including focused crawling, and show their superiority over existing methods.

A Comparison of Meta-heuristic Search for Interactive Software Design

Simons, C. L.; Smith, J. E.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/11/2012
Relevância na Pesquisa
46.35%
Advances in processing capacity, coupled with the desire to tackle problems where a human subjective judgment plays an important role in determining the value of a proposed solution, has led to a dramatic rise in the number of applications of Interactive Artificial Intelligence. Of particular note is the coupling of meta-heuristic search engines with user-provided evaluation and rating of solutions, usually in the form of Interactive Evolutionary Algorithms (IEAs). These have a well-documented history of successes, but arguably the preponderance of IEAs stems from this history, rather than as a conscious design choice of meta-heuristic based on the characteristics of the problem at hand. This paper sets out to examine the basis for that assumption, taking as a case study the domain of interactive software design. We consider a range of factors that should affect the design choice including ease of use, scalability, and of course, performance, i.e. that ability to generate good solutions within the limited number of evaluations available in interactive work before humans lose focus. We then evaluate three methods, namely greedy local search, an evolutionary algorithm and ant colony optimization, with a variety of representations for candidate solutions. Results show that after suitable parameter tuning...

Global Heuristic Search on Encrypted Data (GHSED)

Halloush, Maisa; Sharif, Mai
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/09/2009
Relevância na Pesquisa
46.32%
Important document are being kept encrypted in remote servers. In order to retrieve these encrypted data, efficient search methods needed to enable the retrieval of the document without knowing the content of the documents In this paper a technique called a global heuristic search on encrypted data (GHSED) technique will be described for search in an encrypted files using public key encryption stored on an untrusted server and retrieve the files that satisfy a certain search pattern without revealing any information about the original files. GHSED technique would satisfy the following: (1) Provably secure, the untrusted server cannot learn anything about the plaintext given only the cipher text. (2) Provide controlled searching, so that the untrusted server cannot search for a word without the user's authorization. (3) Support hidden queries, so that the user may ask the untrusted server to search for a secret word without revealing the word to the server. (4) Support query isolation, so the untrusted server learns nothing more than the search result about the plaintext.; Comment: International Journal of Computer Science Issues (IJCSI), Volume 1, pp13-17, August 2009

Bidirectional Heuristic Search Reconsidered

Kaindl, H.; Kainz, G.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 30/11/1997
Relevância na Pesquisa
46.62%
The assessment of bidirectional heuristic search has been incorrect since it was first published more than a quarter of a century ago. For quite a long time, this search strategy did not achieve the expected results, and there was a major misunderstanding about the reasons behind it. Although there is still wide-spread belief that bidirectional heuristic search is afflicted by the problem of search frontiers passing each other, we demonstrate that this conjecture is wrong. Based on this finding, we present both a new generic approach to bidirectional heuristic search and a new approach to dynamically improving heuristic values that is feasible in bidirectional search only. These approaches are put into perspective with both the traditional and more recently proposed approaches in order to facilitate a better overall understanding. Empirical results of experiments with our new approaches show that bidirectional heuristic search can be performed very efficiently and also with limited memory. These results suggest that bidirectional heuristic search appears to be better for solving certain difficult problems than corresponding unidirectional search. This provides some evidence for the usefulness of a search strategy that was long neglected. In summary...

Anytime Heuristic Search

Hansen, E. A.; Zhou, R.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/10/2011
Relevância na Pesquisa
46.49%
We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.

FluCaP: A Heuristic Search Planner for First-Order MDPs

Hoelldobler, S.; Karabaev, E.; Skvortsova, O.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 29/09/2011
Relevância na Pesquisa
46.41%
We present a heuristic search algorithm for solving first-order Markov Decision Processes (FOMDPs). Our approach combines first-order state abstraction that avoids evaluating states individually, and heuristic search that avoids evaluating all states. Firstly, in contrast to existing systems, which start with propositionalizing the FOMDP and then perform state abstraction on its propositionalized version we apply state abstraction directly on the FOMDP avoiding propositionalization. This kind of abstraction is referred to as first-order state abstraction. Secondly, guided by an admissible heuristic, the search is restricted to those states that are reachable from the initial state. We demonstrate the usefulness of the above techniques for solving FOMDPs with a system, referred to as FluCaP (formerly, FCPlanner), that entered the probabilistic track of the 2004 International Planning Competition (IPC2004) and demonstrated an advantage over other planners on the problems represented in first-order terms.

Search-Space Characterization for Real-time Heuristic Search

Huntley, Daniel; Bulitko, Vadim
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/08/2013
Relevância na Pesquisa
46.32%
Recent real-time heuristic search algorithms have demonstrated outstanding performance in video-game pathfinding. However, their applications have been thus far limited to that domain. We proceed with the aim of facilitating wider applications of real-time search by fostering a greater understanding of the performance of recent algorithms. We first introduce eight algorithm-independent complexity measures for search spaces and correlate their values with algorithm performance. The complexity measures are statistically shown to be significant predictors of algorithm performance across a set of commercial video-game maps. We then extend this analysis to a wider variety of search spaces in the first application of database-driven real-time search to domains outside of video-game pathfinding. In doing so, we gain insight into algorithm performance and possible enhancement as well as into search space complexity.

HyFlex: A Benchmark Framework for Cross-domain Heuristic Search

Burke, Edmund; Curtois, Tim; Hyde, Matthew; Ochoa, Gabriela; Vazquez-Rodriguez, Jose A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 27/07/2011
Relevância na Pesquisa
46.52%
Automating the design of heuristic search methods is an active research field within computer science, artificial intelligence and operational research. In order to make these methods more generally applicable, it is important to eliminate or reduce the role of the human expert in the process of designing an effective methodology to solve a given computational search problem. Researchers developing such methodologies are often constrained on the number of problem domains on which to test their adaptive, self-configuring algorithms; which can be explained by the inherent difficulty of implementing their corresponding domain specific software components. This paper presents HyFlex, a software framework for the development of cross-domain search methodologies. The framework features a common software interface for dealing with different combinatorial optimisation problems, and provides the algorithm components that are problem specific. In this way, the algorithm designer does not require a detailed knowledge the problem domains, and thus can concentrate his/her efforts in designing adaptive general-purpose heuristic search algorithms. Four hard combinatorial problems are fully implemented (maximum satisfiability, one dimensional bin packing...

A Heuristic Search Approach to Planning with Continuous Resources in Stochastic Domains

Meuleau, Nicolas; Benazera, Emmanuel; Brafman, Ronen I.; Hansen, Eric A.; Mausam
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/01/2014
Relevância na Pesquisa
46.31%
We consider the problem of optimal planning in stochastic domains with resource constraints, where the resources are continuous and the choice of action at each step depends on resource availability. We introduce the HAO* algorithm, a generalization of the AO* algorithm that performs search in a hybrid state space that is modeled using both discrete and continuous state variables, where the continuous variables represent monotonic resources. Like other heuristic search algorithms, HAO* leverages knowledge of the start state and an admissible heuristic to focus computational effort on those parts of the state space that could be reached from the start state by following an optimal policy. We show that this approach is especially effective when resource constraints limit how much of the state space is reachable. Experimental results demonstrate its effectiveness in the domain that motivates our research: automated planning for planetary exploration rovers.

A timed state space-heuristic search framework for colored petri net-based scheduling of discrete event systems —an application to flexible manufacturing systems

Baruwa, Olatunde Temitope
Fonte: [Barcelona] : Universitat Autònoma de Barcelona, Publicador: [Barcelona] : Universitat Autònoma de Barcelona,
Tipo: Tesis i dissertacions electròniques; info:eu-repo/semantics/doctoralThesis; info:eu-repo/semantics/publishedVersion Formato: application/pdf
Publicado em //2015 ENG
Relevância na Pesquisa
46.61%
Para obtener una ventaja competitiva en el mercado global, los fabricantes tienen que adaptarse rápidamente sus sistemas para responder a las fluctuantes demandas de los clientes en virtud de factores de servicio de alta calidad. La alta inversión de capital en los sistemas de fabricación flexible (SFFs), junto con los desafíos de las condiciones de mercado que cambian rápidamente se ha convertido en esencial la utilización eficiente de los recursos. Para maximizar los beneficios de un SFF, se necesita una implantación de técnicas de programación e planificación adecuadas para aprovechar plenamente las flexibilidades de fabricación. El objetivo global de esta tesis es establecer un marco de programación basado en el modelado de redes de Petri coloreadas temporales (RdPCT) para optimizar el rendimiento de los SFF mediante el desarrollo de herramientas y métodos de búsqueda eficientes basados en el análisis del espacio de estados (EdE). El análisis del espacio del estado es una herramienta potente que se puede utilizar para automatizar la actividad de toma de decisiones en problemas de programación mediante el seguimiento de todos los posibles comportamientos del sistema modelado. Sin embargo, adolece del problema de explosión de espacio de estado debido a la complejidad computacional de los problemas de programación de la producción en SFFs. Lo que ha limitado su aplicabilidad a problemas de tamaño pequeño. En la metodología de la programación propuesta...