The Assembly sequencing problem (ASP) is part of the assembly planning process. The ASP is basically a large scale, combinatorial problem which is highly constrianed. The aim of this thesis is to automatically generate assembly sequence(s) for mechanical products. In this thesis, the CAD model of an assembly is represented or modeled as a label-rich graph. The assembly sequences are generated using graph grammar rules that are applied on the graph. The sequences are stored in a search tree and to find an optimal sequence multiple evaluation criteria like time, subassembly stability and accessibility measures are used. This research implements a novel tree search algorithm called "Ordered Depth First Search" (ODFS) to find an optimal assembly sequence in very low processing time. The software has successfully generated an optimized assembly sequence for an assembly with 14 parts. / text

This work presents an enhancement of a search process that is suited for a problem that can be solved using a graph grammar based generative tree. Generative grammar can be used to generate a vast number of design alternatives by using a seed graph of the problem and a set of transformation rules. The problem is to find the best solution among this space by doing the least number of evaluations possible. In a previous paper, an interactive algorithm for searching in a graph grammar representation was presented. The process was demonstrated for a problem of tying a necktie and the work here builds on top of this process to be useful for solving engineering problem. To test the search process, two problems, a photovoltaic array topology optimization problem and an electromechanical product redesign problem, are chosen. It is shown this search process converges in finding the best solution within a few hundred evaluations which is a manageable number compared to the large solution space of millions of candidates. Further optimization and tweaks are done on the process to control exploration vs. exploitation and find the parameters for fastest convergence and the best solution. / text

<p> Codes with a tree structure find wide use in data compression and error correction. It is generally impractical to view and weigh all the branches in a code tree, so a search algorithm is employed which considers some but not others in a predetermined fashion. Traditionally, the efficiency of code tree search algorithms has been measured by the number of tree branches visited for a given level of performance. This measure does not indicate the true consumption of resources. Cost functions are defined based on the number of code tree paths retained, S, the length of the paths, L, and the number of code tree branches searched per branch released as output, E[C]. Using these cost functions, most of the existing algorithms as well as some new algorithms proposed here are compared.</p> <p> These new algorithms include three metric-first algorithms. The first one, the merge algorithm, uses, in addition to the main list used by the stack algorithm, an auxiliary list to store paths. The merge algorithm reduces the dependence on S for the product resource cost from O(S^2) for the stack algorithm to O(S^4/3 ) for the merge algorithm. A generalization of this algorithm reduces the product cost to O(S log S). The second algorithm uses a class of height-balanced trees, known as AVL trees, to store code tree paths, resulting in an alternate method to the merge algorithm achieving O(S log S) cost.</p> <p> The third algorithm, using the concepts of dynamic hashing and trie searching, provides important modifications to the Jelinek bucket algorithm by incorporating dynamic splitting and merging of buckets. This strategy provides a balanced data structure and reduces the product cost still further compared to the first two algorithms.</p> <p> We next turn to analysis of the number of nodes visited during a search. Using the theory of multitype branching processes in random environments an equation for node computation is derived for asymmetric source coding by the single stack algorithm. This equation is shown to be the stochastic analog of an equation for symmetric sources. Simulation results, obtained by encoding the Hamming source by the single stack algorithm, are used to optimize the performance of the algorithm with respect to the bias factor, stack length, and limit on computation. A modification to the algorithm that raises the barrier during forward motion provides a better distortion performance.</p> <p> The metric-first stack algorithm is used to encode a voiced speech sound. From experimental evidence, it is shown how to optimize the algorithm's SNR performance with respect to the algorithm's storage, execution time, and node computation. For each of these, the optimal parameterizing of the algorithm differs markedly. Similarities are pointed out between the results for speech and earlier theoretical results for the binary i.i.d. source with Hamming distortion measure. It is shown that metric-first algorithms may perform better with "real life" sources like speech than they do with artificial sources, and in view of this the algorithms proposed here take on added significance.</p> / Thesis / Doctor of Philosophy (PhD)

The purpose of this thesis is to evaluate the possibility of predicting difficulty, measured in average human success rate (AHSR), across game levels of a mobile game using a general AI algorithm. We implemented and tested a simulation based bot using MCTS for Candy. Our results indicate that AHSR can be predicted accurately using MCTS, which in turn suggests that our bot could be used to streamline game level development. Our work is relevant to the field of AI, especially the subfields of MCTS and single-player stochastic games as Candy, with its diverse set of features, proved an excellent new challenge for testing the general capabilities of MCTS. The results will also be valuable to companies interested in using AI for automatic testing of software.

DeepMind’s development of AlphaGo took the world by storm in 2016 when it became the first computer program to defeat a world champion at the game of Go. Through further development, DeepMind showed that the underlying algorithm could be made more general, and applied to a large set of problems. This thesis will focus on the AlphaZero algorithm and what parameters affect the rate at which an agent is able to learn through self-play. We investigated the effect that the neural network size has on the agent’s learning as well as how the environment complexity affects the agent’s learning. We used Connect4 as the environment for our agents, and by varying the width of the board we were able to simulate environments with different complexities. For each board width, we trained an AlphaZero agent and tracked the rate at which it improved. While we were unable to find a clear correlation between the complexity of the environment and the rate at which the agent improves, we found that a larger neural network both improved the final performance of the agent as well as the rate at which it learns. Along with this, we also studied what impact the number of MonteCarlo tree search iterations have on an already trained AlphaZero agent. Unsurprisingly, we found that a higher number of iterations led to an improved performance. However, the difference between using only the priors of the neural network and a series of Monte-Carlo tree search iterations is not very large. This suggest that using solely the priors can sometimes be useful if inferences need to made quickly. / DeepMinds utveckling av AlphaGo blev ett stort framsteg året 2016 då det blev första datorprogrammet att besegra världsmästaren i Go. Med utvecklingen av AlphaZero visade DeepMind att en mer generell algoritm kunde användas för att lösa en större mängd problem. Den här rapporten kommer att fokusera på AlphaZero-algoritmen och hur olika parametrar påverkar träningen. Vi undersökte påverkan av neuronnätets storlek och spelkomplexiteten på agentens förmåga att förbättra sig. Med hjälp av 4 i rad som testningsmiljö för våra agenter, och genom att ändra på bredden på spelbrädet kunde vi simulera olika komplexa spel. För varje bredd som vi testade, tränade vi en AlphaZero-agent och mätte dens förbättring. Vi kunde inte hitta någon tydlig korrelation mellan spelets komplexitet och agentens förmåga att lära sig. Däremot visade vi att ett större neuronnät leder till att agenten förbättrar sig mer, och dessutom lär sig snabbare. Vi studerade även påverkan av att variera antalet trädsökningar för en färdigtränad agent. Våra experiment visar på att det finns en korrelation mellan agentens spelstyrka och antalet trädsökningar, där fler trädsökningar innebär en förbättrad förmåga att spela spelet. Skillnaden som antalet trädsökningar gör visade sig däremot inte vara så stor som förväntad. Detta visar på att man kan spara tid under inferensfasen genom att sänka antalet trädsökningar, med en minimal bestraffning i prestanda.

Presented master thesis defines and investigates Adversarial Cooperative Path-finding problem (ACPF), a generalization of standard Cooperative Path-finding. In addition to the Cooperative path- finding where non-colliding paths for multiple agents connecting their initial positions and destinations are searched, consideration of agents controlled by the adversary is included in ACPF. This work is focused on both theoretical properties and practical solving techniques of the considered problem. ACPF is introduced formally using terms from graph theory. We study computational complexity of the problem where we show that the problem is PSPACE-hard and belongs to EXPTIME complexity class. We introduce and discuss possible methods suitable for practical solving of the problem. Considered solving approaches include greedy algorithms, minimax methods, Monte Carlo Tree Search and adaptation of algorithm for the cooperative version of the problem. Surprisingly frequent success rate of greedy methods and rather weaker results of Monte Carlo Tree Search are indicated by the conducted experimental evaluation. Powered by TCPDF (www.tcpdf.org)

We introduce our competitive implementation of a Monte Carlo Tree Search (MCTS) algorithm for the board game of Go: Pachi. The software is based both on previously published methods and our original improvements. We then focus on improving the tree search performance by collecting information regarding tactical situations and game status from the Monte Carlo simulations and sharing it with and within the game tree. We propose specific methods of such sharing --- dynamic komi, criticality-based biasing, and liberty maps --- and demonstrate their positive effect. based on collected play-testing measurements. We also outline some promising future research directions related to our work.

The Monte Carlo Tree Search (MCTS) algorithm has recently proved to be able to solve difficult problems in the field of optimization as well as game-playing. It has been able to address several problems that no conventional techniques have been able to solve efficiently. In this thesis we investigate possible ways to use MCTS in the field of planning and scheduling. We analyze the problem theoretically trying to identify possible difficulties when using MCTS in this field. We propose the solutions to these problems based on a modification of the algorithm and preprocessing the planning domain. We present the techniques we have developed for these tasks and we combine them into an applicable algorithm. We specialize the method for a specific kind of planning problems - the transportation problems. We compare our planner with other planning system.

The aim of this work is design, implementation and experimental evaluation of distributed algorithms for planning actions of a team of cooperative autonomous agents. Particular algorithms require different amount of communication. In the work, the related research on Monte-Carlo tree search algorithm, its parallelization and distributability and algorithms for distributed coordination of autonomous agents. Designed algorithms are tested in the environment of the game of Ms Pac-Man. Quality of the algorithms is tested in dependence on computational time, the amount of communication and the robustness against communication failures. Particular algorithms are compared according to these characteristics. Powered by TCPDF (www.tcpdf.org)

In this work, the algorithm used by AlphaZero is adapted for dots and boxes, a two-player game. This algorithm is explored using different numbers of convolutional filters and training loops, in order to better understand the effect these parameters have on the learning of the player. Different board sizes are also tested to compare these parameters in relation to game complexity. AlphaZero originated as a Go player using an algorithm which combines Monte Carlo tree search and convolutional neural networks. This novel approach, integrating a reinforcement learning method previously applied to Go (MCTS) with a supervised learning method (neural networks) led to a player which beat all its competitors.