Classical planning problems consist of an environment in a predefined state; a set of deterministic actions that, under certain conditions, change the state of the environment; and a set of goal conditions. A solution to a classical planning problem is a sequence of actions that leads from the initial state to a state satisfying the problem’s goal conditions. There are many methods for finding solutions to classical planning problems, and a popular technique is to exploit structures that commonly occur. One such structure, apparent in many planning domains, is a breakdown of the problem into multiple agents. However, methods for finding and exploiting multiagent structures are not prevalent in the literature and are currently not competitive. This thesis sets out to rectify this problem. Its first main contribution, is to introduce a domain independent algorithm for extracting multiagent structure from classical planning problems. The algorithm relies on identifying a generalisable property of agents in planning; namely, that agents are entities with an internal state, a part of the planning problem that, under a certain distribution of actions, only they can modify. Once this is appropriately formalised, the decomposition algorithm is introduced and is shown to produce identifiably multiagent decompositions over all of the classical planning domains used in the International Planning Competitions, even finding more detailed decompositions than are used by humans in certain cases. Solving multiagent planning problems can be challenging because a solution may require complex inter-agent coordination. The second main contribution of the thesis is a heuristic planning algorithm that effectively exploits the structure of decomposed domains. The algorithm transforms the coordination problem into a process of subgoal generation that can be solved efficiently under a well-known relaxation in planning. The generated subgoals guide the search so that it is always performed by one single-agent subproblem at a time. The algorithm is evaluated and shown to greatly outperform current state-of-the-art planners over decomposable domains. The thesis also includes discussion of the possible extensions of this work, to include the multiagent concepts of self-interested agents and concurrent actions. Results from the multiagent planning literature are improved upon and a new solution concept is presented that accounts for the ‘farsightedness’ inherent in planning. A method is then presented that can find stable solutions for a certain class of multiagent planning problems. A new method is introduced for modelling concurrent actions that allows them to be written without requiring knowledge of each other agent in the domain, and it is shown how such problems can be solved by a translation to single-agent planning.

Motion planning is an increasingly important field of research. Factory automation is becoming more prevalent and at the same time, production runs are shortening in the name of customisation. With computer controlled equipment becoming cheaper and more modular, setting up near-fully automated production lines is becoming fast and easy. This means that the actual programming of the robots and assembly system is becoming the rate determining step. Automated motion planning is a possible solution to this—but only if it can run fast enough. Many heuristic planners have been created in an attempt to achieve the necessary speeds in off-line (or more ambitiously, on-line) processing. This thesis aims to show that different types of heuristic planners can be designed to take advantage of specialised environments or robot characteristics. To show this, three distinct classes of heuristic planners are put forward for discussion. The first of these classes, addressed in Chapter 2, is of very generic planners which will work in virtually all situations (ie. almost any combination of robot and environment). This generality is obviously useful when lacking more specific domain knowledge. However these methods do suffer performance-wise in comparison with more specialised planners when there are characteristics of the problem which can be targeted. Chapter 3 moves to planners which are designed to specifically address certain peculiarities of the environment. Particular focus is given to environments whose corresponding configuration-spaces contain narrow gaps and passages. Finally Chapter 4 addresses a third class of planners: those which are designed for specific types of robots and movements. The particular focus is on locomotion for legged vehicles. For each of these three classes, some discussion is made of existing planners which can be so characterised. In addition, a novel algorithm is introduced in each as an example for particular consideration.

Thesis (Ph. D.)--University of Texas at Austin, 2004. / Supervisor: Randy B. Machemehl. Vita. Includes bibliographical references. Also available from UMI.

No description available.

Thesis (M.S.)--Kutztown University of Pennsylvania, 1991. / Source: Masters Abstracts International, Volume: 45-06, page: 3181. Typescript. Includes bibliographical references (leaves 75-76).