The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark paradigm. The new heuristic’s novel feature is that it computes and stores a reduced amount of preprocessed information (in comparison to previous landmark-based algorithms) while enabling more informed search decisions. We demonstrate that domination of this heuristic over its predecessor depends on landmark selection and that, in general, the denser the landmark set, the better heuristic performs. Due to the reduced memory requirement, this new heuristic admits much denser landmark sets. We conduct experiments to characterize the impact that landmark configurations have on this new heuristic, demonstrating that centrality-based landmark selection has the best tradeoff between preprocessing and runtime. Using a developed graph library and static information from benchmark road map datasets, the algorithm is compared experimentally with previous landmark-based shortest path techniques in a fixed-memory environment to demonstrate a reduction in overall computational time and memory requirements. Experimental results are evaluated to detail the significance of landmark selection and density, the tradeoffs of performing preprocessing, and the practical use cases of the algorithm.

We introduce a steepest-descent-like search algorithm for the design of Boolean functions, yielding multiple desirable cryptographic properties in their Walsh and autocorrelation spectra together. The algorithm finds some Boolean functions on 9, 10, 11, 13 variables with very good cryptographic properties unattained in the literature. More specifically, we have discovered 9-variable rotation symmetric Boolean functions (RSBFs) having nonlinearity of 241, which exceeds the bent concatenation bound and has remained as an open question in the literature for almost three decades. We have then shown that there is no RSBF having nonlinearity greater than 241, and that there are 8x189 many RSBFs having nonlinearity of 241, such that, among them there are only two that are different up to the affine equivalence. We also propose a generalization to RSBFs and dihedral symmetric Boolean functions (DSBFs), which improves the nonlinearity result of 9-variable Boolean functions to 242. Further, we classify all possible permutations (362, 880) on the input variables of 9-variable Boolean functions and find that there are only 30 classes, which are different with respect to the linear equivalence of invariant Boolean functions under some permutations. Some of these classes and their subsets yield new 9-variable Boolean functions having the nonlinearity of 242 with different autocorrelation spectra from those of the Boolean functions found in generalized RSBF and DSBF classes. Moreover, we have attained 13-variable balanced Boolean functions having nonlinearity of 4036 which is greater than the bent concatenation bound of 4032, and improves the recent result of 4034.

In this thesis, a resource allocation problem in OFDMA is studied for the energy efficiency of wireless network. The objective is to minimize the total energy consumption which includes transmission energy consumption, and circuit energy consumption at both transmitter and receiver with required per user’s rate constraint. For problem solution, a heuristic algorithm with low computational complexity and suboptimal solution is proposed, developed in two steps with an increasing order of complexity. Besides, a bounding scheme based on model linearization of formulated nonlinear system model is also proposed to give lower and upper bounds for both small- and large-scale OFDMA network for further algorithm performance evaluation, while the implemented exhaustive search is only capable to provide the optimal solution for small-scale instance for algorithm performance evaluation. Numerical results show that the proposal heuristic algorithm can achieve near-optimal performance with applicable computational complexity even for large-scale networks, and that the bounds from the bounding scheme are very tight for both small- and large-scale OFDMA networks.

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.

Approved for public release; distribution is unlimited / Unmanned vehicle technology has matured significantly over the last two decades. This is evidenced by its widespread use in industrial and military applications ranging from deep-ocean exploration to anti-submarine warefare. Indeed, the feasiblity of short-range, special-purpose vehicles (whether aunonomous or remotely operated) is no longer in question. The research efforts have now begun to shift their focus on development of reliable, longer-range, high-endurance and fully autonomous systems. One of the major underlying technologies required to realize this goal is Artificial Intelligence (AI). The latter offers great potential to endow vehicles with the intelligence needed for full autonomy and extended range capability; this involves the increased application of AI technologies to support mission planning and execution, navigation and contingency planning. This thesis addresses two issues associated with the above goal for Autonomous Underwater Vehicles (AUV's). Firstly, a new approach is proposed for path planning in underwater environments that is capable of dealing with uncharted obstacles and which requires significantly less planning time and computer memory. Secondly, it explores the use of expert system technology in the planning of AUV missions.

This thesis analyzes the kinematical structure of Puma 760 arm and introduces the implementation of image based pick and place application by taking care of the obstacles in the environment. Forward and inverse kinematical solutions of PUMA 760 are carried out. A control software has been developed to calculate both the forward and inverse kinematics solution of this manipulator. The control program enables user to perform both offline programming and real time realization by transmitting the VAL commands (Variable Assembly Language) to the control computer. Using the proposed inverse kinematics solutions, an interactive application is generated on PUMA 760 arm. The picture of the workspace is taken using a fixed camera attached above the robot workspace. The captured image is then processed to find the position and the distribution of all objects in the workspace. The target is differentiated from the obstacles by analyzing some specific properties of all objects, i.e. roundness. After determining the configuration of the workspace, a clustering based search algorithm is executed to find a path to pick the target object and places it to the desired place. The trajectory points in pixel coordinates, are mapped into the robot workspace coordinates by using the camera calibration matrix obtained in the calibration procedure of the robot arm with respect to the attached camera. The required joint angles, to get the end effector of the robot arm to the desired location, are calculated using the Jacobian type inverse kinematics algorithm. The VAL commands are generated and sent to the control computer of PUMA 760 to pick the object and places it to a user defined location.

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

[pt] Este trabalho emprega conceitos e ferramentas de Teoria das Categorias e Teoria de Topoi para construir um modelo matemático de problemas, reduções entre problemas, espaços e estratégias de busca heurística. Mais precisamente, uma estratégia de construção de espaços de busca é representada por um funtor de uma certa categoria de problemas para uma certa categoria de florestas. A coleção de todos estes funtores forma um topos, um modelo específico equipado com uma lógica interna própria. Esta lógica interna é usada, então, para definir estratégias de busca e heurísticas em Teoria Local dos Conjuntos. Possíveis aplicações do trabalho incluem (1) a especificação lógica e a classificação de heurísticas e meta-heurísticas usadas na prática e (2) uma versão mais abstrata e geral de resultados específicos relacionando a estrutura de problemas com métodos de resolução adequados. / [en] This work employs concepts and tools from Category Theory and Topos Theory to construct a mathematical model for problems, reductions between problems, heuristic search spaces and strategies. More precisely, a search space construction strategy is represented by a functor from a certain category of problems to a certain category of forests. The collection of all such functors forms a topos, a specific model equipped with its own internal logic. This internal logic is then used to define search satrategies and heuristics in Local Set Theory. Possible applications of this work include (1) the logical specification and classification of heuristics and metaheuristics used in pratice and (2) a more abstract and general rendering of specific results relating the structure of problems to adequate problem-solving methods.

Modularity Density Maximization is a graph clustering problem which avoids the resolution limit degeneracy of the Modularity Maximization problem. This thesis aims at solving larger instances than current Modularity Density heuristics do, and show how close the obtained solutions are to the expected clustering. Three main contributions arise from this objective. The first one is about the theoretical contributions about properties of Modularity Density based prioritizers. The second one is the development of eight Modularity Density Maximization heuristics. Our heuristics are compared with optimal results from the literature, and with GAOD, iMeme-Net, HAIN, BMD- heuristics. Our results are also compared with CNM and Louvain which are heuristics for Modularity Maximization that solve instances with thousands of nodes. The tests were carried out by using graphs from the “Stanford Large Network Dataset Collection”. The experiments have shown that our eight heuristics found solutions for graphs with hundreds of thousands of nodes. Our results have also shown that five of our heuristics surpassed the current state-of-the-art Modularity Density Maximization heuristic solvers for large graphs. A third contribution is the proposal of six column generation methods. These methods use exact and heuristic auxiliary solvers and an initial variable generator. Comparisons among our proposed column generations and state-of-the-art algorithms were also carried out. The results showed that: (i) two of our methods surpassed the state-of-the-art algorithms in terms of time, and (ii) our methods proved the optimal value for larger instances than current approaches can tackle. Our results suggest clear improvements to the state-of-the-art results for the Modularity Density Maximization problem.

Nesta tese, nós estudamos a classe de problemas de blocos-móveis. Um problema de blocos-móveis consiste em k blocos móveis dispostos em um labirinto em grade quadrangular onde há um bloco móvel adicional chamado de o homem, que é o único bloco que pode ser movido diretamente. Em particular, cada problema de blocos-móveis é definido pelo conjunto de movimentos disponíveis, pela descrição do objetivo e pelo o que acontece quando o homem tenta mover um bloco. Sokoban é o problema de blocos-móveis mais conhecido e pesquisado. Nós investigamos a complexidade computacional de problemas de blocos-móveis. Antes desta tese, a maior parte da literatura cientifica abordou problemas de blocos-móveis apenas com movimentos de EMPURRAR, na maioria dos casos provando que esses problemas são PSPACE-complete. Nós consideramos dois conjuntos de problemas: apenas movimentos de PUXAR, e movimentos de EMPURRAR e PUXAR combinados. Nossas reduções usam a Lógica de Restrições Não Determinística. Nós provamos que muitos problemas apenas com movimentos de PUXAR são PSPACE-complete. Além disso, nós provamos que o conjunto de problemas com movimentos de EMPURRAR e PUXAR é PSPACE-complete. A nossa contribuição nessa linha de pesquisa é aprimorar o conhecimento sobre o panorama da complexidade de problemas de blocos-móveis. Nosso principal objetivo com essa tese é resolver otimamente problemas de blocos-móveis com foco em Sokoban. Métodos baseados em busca heurística e heurísticas de abstrações como banco de dados de padrões são as abordagens mais efetivas para resolver otimamente esses problemas. Nós fazemos muitas contribuições nessa linha de pesquisa. Nós introduzimos novas funções heurísticas usando bancos de dados padrão com a ideia de estados objetivos intermediários. Propomos uma técnica baseada em bancos de dados padrão para detectar impasses. Propomos regras de desempate que exploram a estrutura do problema. Usando estas funções heurísticas e regras de desempate nós aumentamos o número de instâncias resolvidas de forma ótima de Sokoban e outros problemas em comparação com os métodos anteriores. / In this thesis, we study the class of moving-blocks problems. A moving-blocks problem consists of k movable blocks placed on a grid-square maze where there is an additional movable block called the man, which is the only block that can be moved directly. In particular, each moving-blocks problem is defined by the set of moves available, by the goal description and by what happens when the man attempts to move a block. Sokoban is the best known and researched moving-blocks problem. We study moving-blocks problems in theory and practice. We investigate the computational complexity of problems of moving-blocks. Prior to this thesis, most of the scientific literature addressed moving-blocks problems with PUSH moves only, in most of the cases proving that these problems are PSPACE-complete. We consider two sets of problems: PULL moves only, and PUSH and PULL moves combined. Our reductions are from Nondeterministic Constraint Logic. We prove that many problems with PULL moves only are PSPACE-complete. In addition, we prove that the entire set of PUSH and PULL moves is PSPACE-complete. Our contribution in this research line is to enhance the knowledge on the complexity landscape of moving-blocks problems. Our main objective in this thesis is to optimally solve moving-blocks problems with a focus on Sokoban. Methods based on heuristic search and abstraction heuristics such as pattern databases are the most effective approaches to optimally solve these problems. We make many contributions in this research line. We introduce novel heuristic functions using pattern databases with the idea of intermediate goal states. We propose a technique based on pattern databases to detect deadlocks. We propose tie-breaking rules that exploit the structure of the problem. Using these heuristic functions and tie-breaking rules we increase the number of optimally solved instances of Sokoban and other problems compared to previous methods.