FREE ELECTRONIC LIBRARY - Books, abstracts, thesis

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 26 |

«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»

-- [ Page 7 ] --

2.9 Summary Mission-directed path planning seeks to solve for paths in a context historically addressed in the AI planning and scheduling literature. Path planning is most naturally solved in a state space formulation; the planning and scheduling community has almost universally used spaces of possible plans. Planning and scheduling software deals very effectively with temporal and resource constraint problems, but has not addressed problems where spatial dimensions are so critical, as in path planning. Specifically, planning and scheduling has been most successful at satisfying resource constraints, but has not typically sought to optimize resource usage. Optimization of state parameters is the domain of the state space. Meanwhile, the path planning community has addressed temporal planning in a hierarchical fashion that prevents globally-optimal solutions, and has limited its treatment of the resource management problem to resources that are consumed monotonically over a path.

As demonstrated by ASPEN and CASPER, AI planning and scheduling software can call a path planner as a subroutine to handle mobile phases of a larger activity plan. In scenarios where traverses are relatively short-distance and duration, this type of hierarchy might suffice. But in situations where traverse activities consume a large share of the time and resources in a mission plan, the system cannot tolerate a path planner that is naive to time, resources and constraints. Addressing the combined problem of path planning, temporal planning and resource planning is a central contribution of this thesis.

This thesis elects to follow the path planning paradigm. The following is a brief list of problems in mission-directed

path planning that are largely absent in the robot path planning literature but have been addressed in this thesis:

• Efficient, optimal planning and re-planning, under global constraints, in a state space of greater than two dimensions.

• Simultaneous, global consideration of highly-coupled route, time and resource variables.

• Incorporation of time-varying anisotropic costs and constraints.

• Capability to reason about, constrain and optimize non-monotonic (expendable and replenishable) resource variables.


• Representation of actions, either coupled with navigation actions or distinct, and both mobile and stationary, that enable resource management or achieve non-navigational mission goals.

The Incremental Search Engine by Stentz and Tompkins embodies several attributes that are highly desirable or even essential to solve the mission-directed path planning problem. ISE offers the optimality guarantees and re-planning efficiency of D*, which has proven itself in many robot applications. It is also more space and time efficient in addressing higher-dimensional state spaces than other existing algorithms. This is critical if we expect to consider time and resources. Furthermore, ISE enforces global constraints on paths, for example bounds on battery energy.

The next chapter describes ISE in far greater detail as background for presenting a practical solution to missiondirected path planning.

3. Incremental Search

This chapter describes one of the foundations for this work - an algorithm developed by Stentz and Tompkins, called Incremental Search Engine (ISE), that satisfies many of the demands of mission-directed path planning. ISE provides several enhancements over previous algorithms that are critical in mission-directed path planning. ISE is a generalization of the D* algorithm (see Section 2.5 or [63][65]) that retains the planning and re-planning efficiency of Focussed D* [63], but enforces global constraints and operates efficiently in state spaces with greater than two dimensions. Mission-directed path planning is the first and most exhaustive application of ISE.

ISE is a backwards-chaining algorithm that starts its search from one or more goal states, and finds an optimal path that “ends” at the specified start state. Like A* and D*, ISE maintains a list of states to “expand” to propagate the search to new states. These states, beginning with the goals, are prioritized for expansion according to an objective function which accumulates the cost from each state to the goal, and a heuristic function which estimates the cost from the start state to each of the states. State expansion generates all possible backward “arcs”, representing actions in the planning domain, from the final state to several initial states originating the actions. The new states are placed on the list, and prioritized according to their own value. The optimal path emerges upon expanding the start state.

Further machinery within the prioritized state list enables ISE to efficiently repair path solutions when the transition arcs change during a path execution.

The following sections describe the salient features of the algorithm. Section 3.1 describes how ISE encodes application domains. Section 3.2 explains several efficiency mechanisms which speed search and minimize state proliferation. Section 3.3 provides an overview of the search process (Appendix 1 describes the ISE algorithm in detail).

Throughout these sections, it should become clear that ISE is a general incremental search algorithm that can be applied to a wide range of problems. A user must define state space variables and application-specific functions of state to compute state transitions between states, heuristics, and state priorities, and other quantities. Section 3.4 experimentally demonstrates how ISE performance varies as these parameters change.


3.1 States, Transitions and Cost A*, D* and other incremental graph search algorithms are best suited for two-dimensional grid planning, or in domains where states are abstract nodes in a graph. In factored spaces of greater than two dimensions, existing algorithms fail to provide a simple means of encoding state spaces. ISE allows a natural representation of state space in terms of discrete independent and dependent parameters.

3.1.1 Independent and Dependent State Parameters ISE allows two types of state variables - independent parameters (IPARMS) and dependent parameters (DPARMS).

IPARMS are the foundation of the ISE state space and search and are essential to defining a problem domain.

Changes in IPARMS are independent of other state parameters. A domain may optionally include DPARMS, parameters whose values change as a function of changes in IPARMS or other DPARMS. DPARMS for a state are stored in a set corresponding to the state’s IPARMS. An ISE state combines the IPARMS and DPARMS of the domain.

For example, a robot control problem might entail planning a path through a two-dimensional office area, where obstacles are time-varying. The state space might define two independent spatial parameters X and Y that are positions in a regular grid, and a dependent temporal dimension T, such that ∆T = f ( ∆X, ∆Y ). The ISE state is an ( x, y, t ) tuple. ISE would represent this domain by encoding a regular grid of sets, each corresponding to an x-y cell, that store values of t. Each t value would represent a different state ( x, y, t ).

3.1.2 State Transitions Arcs are transitions between two ISE states. ISE uses two user-defined arc transition functions, one backwards ( β ) and one forwards ( Φ ), to model state transitions in a domain. Given a state space S and action space A, the arc transition functions define deterministic mappings S × A → S that obey the Markov assumption, that is, the resulting state is a function only of the action and the originating state. Given a state and a choice of action, the transition arc functions define the change in IPARMS and the corresponding change in DPARMS. The backward function β takes a final state and produces the initial state from which the action was executed. In many cases, the forward function Φ

–  –  –

The forward transition function Φ is not always single-valued. ISE state variables can be constrained to minimum or maximum values. For example, a state variable b might represent battery charge which can never rise above the battery capacity b max. Function β could legally take the form b initial = min ( b final – i∆t, b max ), where i and ∆t are the the charging current during the action and the action duration, repectively. Now, suppose there is an action A where

–  –  –

i is negative (signifying a battery discharge in the forward-time direction). If b final ≥ b max – i ∆t, then b initial = b max.

Clearly, then, the forward transition function Φ for action A cannot unambiguously predict b final from b initial = b max. Instead, Φ must predict the range of legal states that are possible from an initial state. Using the above example, Φ could take the form b final = b initial + i∆t for b initial b max, and b final ∈ [ b initial + i∆t, b max ] for b initial = b max.

Arc parameters, or APARMS, govern the effects of transitions. Each IPARMS combination has APARMS that help define the transitions into or out of the states with those IPARMS. Most importantly, APARMS are parameters that are allowed to change during plan execution. As discussed in upcoming sections, re-planning enables ISE to efficiently repair a plan whose underlying APARMS have changed.

3.1.3 Local Constraints Local constraints are a generalization of obstacles in the path planning literature. The satisfaction or violation of local constraints depends solely on the specific state and the action executed to or from that state; it does not depend on state or action history. Obstacles in traditional path planning are local constraints on locomotion actions. Local constraints extend obstacles by limiting arbitrary actions over any range of states in the state space. Through the application-specific (user-defined) arc transition functions β and Φ, ISE permits or rejects arcs into states that violate local constraints. Rejected states cannot become part of any ISE path solution.

In the running example, the office robot would be constrained to avoid people and closed doors, as defined by local constraints at specific ( x, y, t ) regions of the state space. The office environment might further restrict its operation to certain hours of day, a purely temporal local constraint.

3.1.4 Global Constraints In contrast to local constraints, which operate on state parameters, global constraints operate on parameters that integrate over the history of state or actions. Examples include path distance, duration, and capacity limitations on consumable or replenishable resources. ISE enforces global constraints in one of two ways. ISE stores global constraint parameters through auxiliary variables stored alongside DPARMS state parameters or, if the parameter is to be optimized, in the objective function (see Sections 3.1.6 and 3.1.7). If stored alongside the DPARMS parameters, the global constraint parameters are evaluated inside the β state transition function. When a violation occurs, the β function rejects the arc. Alternatively, if the parameter is stored in the objective function, ISE cannot reject the arc, but assigns a very high cost to the arc to reduce its chances of entering into any optimal solution. Under this second approach, if no cheaper legal path exists, ISE will yield the least expensive illegal path.


What are the implications of local and global constraint parameters? The addition of global constraint parameters does not add dimensions to the state space. However, under the Markov assumption, aside from rejecting arcs, global constraint parameters cannot legally have any effect on DPARMS or cost for state transitions. Furthermore, ISE can only guarantee planning completeness in the variables comprising the state space. If a parameter is not a member of the state, ISE cannot explore trajectories that vary the parameter to find feasible path solutions. Any global constraint can be transformed into a local constraint by promoting its parameter to a full DPARMS state parameter. The parameter can then affect state transitions and costs for legal state transitions, but at the computational and memory expense of an added dimension in the state space (see Section 3.4.2).

3.1.5 Resource Parameters Because of its flexible treatment of state, constraints and cost, ISE is particularly well-suited to reasoning about resources. A resource is a quantity that is essential to achieving a goal, and yet is in limited supply. ISE represents resources as constraint-limited parameters. ISE can be represent resources as DPARMS state variables, limited by local constraints, or as global constraint parameters alongside DPARMS or in the objective function.

Resource parameters can be divided into two categories - monotonic and non-monotonic. Monotonic resource parameters monotonically increase or decrease over the course of a trajectory. Examples of monotonic resources include non-rechargeable battery energy or finite-lifetime components. More abstractly, if a path is constrained to be less than a given distance or duration, then remaining distance or duration can also be considered resources. Planning problems often involve renewable resources - parameters that can be expended and replenished over different arcs, and hence are non-monotonic. Rechargeable energy, thermal load, available computer memory or communications bandwidth are all examples of non-monotonic resources.

In ISE, because of the backwards-chaining order of search, the semantics of resource parameters are different than for typical parameters. As with all DPARMS and objective function parameters, values for resource parameters must be initialized for each goal prior to search. Semantically, it is useful to treat these values as minimum allowable resource levels at the completion of a path. For example, a parameter to represent duration remaining to the goal (as a way of constraining duration over a path) might be set to zero. In words, at the start of a path if a robot is given an upper bound on duration to reach the goal, it is legal in the worst case to exhaust the entire duration “resource”, but no more.

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 26 |

Similar works:

«Systematische Ganzheitlichkeit Eine methodologische Vermittlung zwischen Perspektivität und Universalität mit einem Grundriß der Anwendbarkeit dieses Ansatzes auf die Geowissenschaften Inauguraldissertation zur Erlangung der Würde eines Doktors der Philosophie vorgelegt der Philosophisch-Naturwissenschaftlichen Fakultät der Universität Basel von Alec A. Schaerer Bürger von Sumiswald / BE und Genf Basel, Oktober 2011 Genehmigt von der Philosophisch-Naturwissenschaftlichen Fakultät auf...»

«GET A ROOM: PRIVATE SPACE AND PRIVATE PEOPLE IN OLD FRENCH AND MIDDLE ENGLISH LOVE STORIES by Alice Jane Cooley A thesis submitted in conformity with the requirements for the degree of Doctor of Philosophy Centre for Medieval Studies University of Toronto © Copyright by Alice Jane Cooley, 2010 Abstract Get a Room: Private Space and Private People in Old French and Middle English Love Stories Submitted by: Alice Jane Cooley Degree: Doctor of Philosophy (2010) Department: Centre for Medieval...»

«The interaction between physical and sedimentary biogeochemical processes in south-west Spencer Gulf, South Australia. Emlyn Morris Jones B. Sc. (Hons) A thesis submitted in fulfillment for the degree of Doctor of Philosophy School of the Environment Faculty of Science and Engineering Flinders University of South Australia March, 2010 Contents Abstract v Declaration viii Acknowledgments ix 1 General introduction 1 1.1 Regional setting.......................... 5 1.1.1...»

«Diplomarbeit Titel der Diplomarbeit „240 Tage Sodom – Sade, Pasolini und die Verwertung des Individuums in der Moderne“ Verfasser Lukas Johne Angestrebter akademischer Grad Magister der Philosophie (Mag. phil.) Wien, September 2011 A – 296 Studienkennzahl lt. Studienblatt: Diplomarbeitsgebiet lt. Studienblatt: Philosophie Univ.-Doz. DDr. Mădălina Diaconu Betreuerin: But inside doesn’t matter.whatever. There are no more barriers to cross. All I have in common with the uncontrollable...»

«Ruprecht – Karls – Universität Heidelberg Philosophische Fakultät Musikwissenschaftliches Seminar Prof. Dr. Silke Leopold Dissertation on the topic Musical Settings of Psalm 51 in Germany c. 1600-1750 in the Perspectives of Reformational Music Aesthetics Presented by Billy Kristanto Supervisor: Prof. Dr. Silke Leopold Second Examiner: PD Dr. Michael Heymel Third Examiner: Prof. Dr. Dorothea Redepenning Acknowledgments This present study could not have been written without various supports...»

«The Medieval Tournament: Chivalry, Heraldry and Reality An Edition and Analysis of Three Fifteenth-Century Tournament Manuscripts 2 Volumes Ralph Dominic Moffat Submitted in accordance with the requirements for the degree of Doctor of Philosophy The University of Leeds Institute for Medieval Studies August 2010 The candidate confirms that the work submitted is his own and that appropriate credit has been given where reference has been made to the work of others. Acknowledgments The production...»

«DIPLOMARBEIT Titel der Diplomarbeit „Frauenstimmen von der Grenze – Bilder von Weiblichkeit bei mexikanischen und ChicanaAutorinnen“ Verfasserin Elisabeth Haslinger angestrebter akademischer Grad Magistra der Philosophie (Mag.phil.) Wien, 2012 Studienkennzahl lt. Studienblatt: A 236 352 Studienrichtung lt. Studienblatt: Diplomstudium Romanistik / Spanisch Betreuerin: Univ. Prof. Dr. Kathrin Sartingen Danksagung An dieser Stelle möchte ich mich bei all jenen Personen bedanken, die mich im...»

«Suhrkamp Verlag Leseprobe Brandom, Robert B. Wiedererinnerter Idealismus Aus dem Amerikanischen von Falk Hamann und Aaron Shoichet © Suhrkamp Verlag suhrkamp taschenbuch wissenschaft 2104 978-3-518-29704-9 suhrkamp taschenbuch wissenschaft 2104 Was unterscheidet uns Menschen von anderen Lebewesen? Laut dem großen amerikanischen Philosophen Robert Brandom vor allem die Tatsache, dass wir in unserem Handeln und Urteilen Verpflichtungen eingehen und Verantwortung für das übernehmen, was wir...»

«TEACHING ENGLISH AS A SECOND OR FOREIGN LANGUAGE TO ADULTS IN QATAR: EXPLORING GENDER DIFFERENCES IN LANGUAGE ACQUISTION by RIANA ROUSSEAU submitted in accordance with the requirements for the degree of DOCTOR OF PHILOSOPHY WITH SPECIALISATION IN ADULT EDUCATION at the UNIVERSITY OF SOUTH AFRICA SUPERVISOR: PROF E.R. MATHIPA APRIL 2014 Acknowledgements My sincere thanks and appreciation are due to Prof E.R. Mathipa for selecting me, and under whose supervision, this research was conducted. His...»

«J. TECHNICAL WRITING AND COMMUNICATION, Vol. 34(4) 265-290, 2004 HERBERT SPENCER’S PHILOSOPHY OF STYLE: CONSERVING MENTAL ENERGY RUSSEL HIRST University of Tennessee, Knoxville ABSTRACT My article traces the development, chronicles the impact, and explains the essence of Herbert Spencer’s “The Philosophy of Style” (1852). Spencer’s essay has had a significant influence on stylistics, especially in scientific and technical communication. Although in our generation Spencer’s...»

«Exposé Menschenrecht und Staat in Spinozas politischer Philosophie (Arbeitstitel) Dissertationsgebiet: Rechtsphilosophie Dissertant: Mag. iur. Harald Spritzendorfer Betreuer: Ao. Univ.-Prof. DDr. Christian Stadler Studienkennzahl: A 783 101 Studienrichtung: Rechtswissenschaften I. D A R S T E L L U N G D E S T H E M A S 1. Einleitung Auch wenn Spinozas Philosophie vielleicht nicht „alles zermalmte“1, so zeichnet sie sich doch durch ihren Facettenreichtum und die immer neuen Zugänge aus,...»

«Diplomarbeit Titel der Diplomarbeit Wirkfaktoren in der Filialtherapie Eine theoretische Abhandlung über Wirkgrößen in der CPRT Verfasserin Maria Farahnaz Faseli Zur Erlangung des akademischen Grades Magistra der Philosophie (Mag. Phil.) Wien, 2011 Studienkennzahl lt. Studienblatt: 297 Studienrichtung lt. Studienblatt: Pädagogik Betreuer: Ao. Univ.-Prof. Dr. Robert Hutterer Ich widme diese Arbeit Shirin, Clemens und Nikolaus DANKSAGUNG An erster Stelle möchte ich Ao. Univ.-Prof. Dr. Robert...»

<<  HOME   |    CONTACTS
2016 www.book.xlibx.info - Free e-library - Books, abstracts, thesis

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.