FREE ELECTRONIC LIBRARY - Books, abstracts, thesis

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 26 |

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

-- [ Page 6 ] --

Based on the approach of Bobrow et al. [5], the technique splits the time-optimal problem into two by first determining the top several minimum distance paths, and then optimizing each of their velocity profiles using kinematics, dynamics and dynamic constraints. An obvious disadvantage with this sequential approach is that the minimum-distance path is not necessarily the time-optimal path. Aside from the approach used to optimize the path, an interesting feature of the approach is the use of B-spline patches and B-splines to model the terrain and paths, repectively. These continuous parametric functions enable a smooth integration of trajectories, but prevent optimization using gradient descent since the parameters to be optimized are the control points for the spline curves.


Another approach, by Pai and Reissell, represents terrain at multiple resolutions using wavelets, and plans paths hierarchically from the coarsest to finest maps [49]. The authors show that when applying wavelet filters in natural terrain, the wavelet coefficients in smooth areas shrink quickly at greater filtering levels (i.e. at higher resolutions), while in rough terrain, coefficients persist through many iterations. Therefore, in smoother areas, the lower-resolution wavelet levels match the original data well, while in rough areas, the coarse levels model the original terrain with significant error. Under this observation, the authors use an error measure at coarse terrain levels, a quantity that falls directly from the wavelet filtering operation, as a metric for terrain smoothness. Using the smooth terrain metric, the planning algorithm seeks smoothness-optimal paths at the lowest resolution, and then advances to higher resolutions in an “anytime” manner to refine the original path. The authors also examine various means of computing cumulative path cost, and derive a generalized worst cost function that heuristically prefers safest paths. Under experiments using digital elevation models of actual terrain, the algorithm appears to select the best paths through terrain. The approach here is novel, and potentially very useful in this work as a means of terrain analysis. However, it takes a heuristic rather than model-based approach to cost calculations, so is difficult to use in conjunction with power estimation that is required of an energy-cognizant path planner.

As mentioned in Section 2.1.1, grid-based representations suffer from memory inefficiency and the restriction of motion to paths between cell centers (or grid vertices). Another body of work plans paths on terrain approximated by polygonal regions with homogenous properties. This representation efficiently maps homogeneous regions and allows motion to occur in arbitrary directions. Richbourg et al. [52] introduce a technique for finding optimal paths, in terms of energy expense, where costs within the regions are isotropic - where the path cost per unit distance does not vary with path heading. They show that optimal paths consist of straight line segments across regions and direction changes between regions governed by Snell’s Law from optics literature. This restriction of paths to Snell’s Law trajectories, combined with several pruning rules, enables an efficient search of the region-wise continuous space for optimal paths. Rowe and Ross [54] extend this work, again for minimum energy expense paths, to travel through regions of anisotropic costs - where legal directions on sloping terrain are defined by maximum vehicle power limitations, sideslope tipover, and downhill braking. They prove that optimal paths can only cross these regions in one of four ways and, as in [52], that direction changes between regions must follow Snell’s Law. Sun and Reif [67] apply an efficient discretization to the polygonal region boundaries, using Steiner points, and a more efficient search algorithm, to display good search performance on maps of natural terrain.

In another extension of the work by Richbourg, et al., Rowe and Lewis [53] describe a method for defining paths for both land and airborne vehicles to either minimize or maximize visibility with respect to fixed observers (e.g. representing beneficial resources or enemy observers) while minimizing path cost in terms of an energy metric. The planner divides the free space into convex visibility regions, defined by visibility to each observer, and assumes each of these volumes to be homogeneous in terms of both energy and visibility costs. Assuming linear costs, the authors


apply the Snell’s Law model to path propagation and minimum-cost path angle transitions between regions. Though interesting, the method appears more directed towards flight, and in its quest to abide by Snell’s Law, uses overly simplistic, linear cost models. However, to its credit, the method does raise the issue of effective space decomposition, and addresses the balance between visibility and energy costs.

Several robots have used the D* algorithm [63],[64],[65] in conjunction with the Morphin local planner (Section 2.7.1) to drive autonomously on rough terrain over long distances. Local maps derived from stereo camera data are also used to populate a cost map in D* based upon estimated terrain traversability. D* produces an optimal path to a global goal position, given all available information. Unlike Morphin, which assigns infinite cost to unknown regions, D* planners have historically been designed to assign zero cost to areas with no existing data. Typically these no-data regions are at the field-of-view limits of the cameras, and will ultimately contain data as the rover gets closer. As new data is introduced, D* efficiently re-plans by repairing only those regions affected by the changes.

Hence the optimal global path updates with each stereo image set, typically several times per second. The local obstacle avoidance and global planner each vote with their respective arcs; the higher-value arc is sent as a command to the rover controller. A relative weight factor allows operators to tune the behavior of the robot. Weights emphasizing obstacle avoidance will steer further from obstacles, but may avoid legal paths through narrow passages. Conversely, boosting the weight of the global path planner improves the likelihood of finding paths, but also increases the chances of collision with obstacles. The combination of local and global path planning has proven itself in many natural terrain rover experiments [59], [78], [32].

Of recent popular interest is the DARPA Grand Challenge automated racing contest. In 2004, teams developed vehicles and software systems to drive autonomously 143 miles in under 10 hours on a combination of rough roads and off-road conditions. Though no team completed the course, Urmson et al. describe Sandstorm, the system that drove further and faster than all other competing vehicles [73]. Teams were supplied the race route only 3 hours prior to the start of the race, in the form of GPS waypoints spaced an average of 89 meters apart, maximum speed limits, and maximum allowable corridors of travel. Sandstorm path planning was a mixed-initiative system that combined automated route generation on a regular grid at 1 meter resolution to follow the GPS points while staying within corridor bounds and minimizing travel on unknown and poor road conditions, subsequent automated route vectorization to compress and simplify the plan representation, and human inspection, correction and smoothing of paths using various graphical interface tools. Automated planning used coarse road classifications, as well as distance from the center of the drive corridor, as a basis for driving cost. It appears that a velocity profile was selected in a separate step after route planning. Onboard GPS and a scanned laser enabled Sandstorm to follow the course 7.4 miles at speeds up to 36 miles per hour. This system clearly did not freely select its global route, but rather connected pre-selected waypoints and established a speed profile that would enable completion of the route within the race deadline.


Despite their applicability to long-distance path planning, none of these approaches considers time-dependent costs.

For example, though the representation of terrain using homogeneous cost regions and Snell’s Law in [52][54][67] is attractive, it is not clear how to extend the model when cost regions are time-varying. Furthermore, the cases that seek minimum-energy paths ignore sources of incoming energy, such as solar energy. They minimize resource costs, but none models renewable resources where a balance must be achieved between input, output and storage. As a result, none can predict how a finite battery capacity might prevent certain paths, or how resource collection might extend the set of feasible paths. However, in terms of operational utility, the efficient re-planning provided by D*based planners is clearly advantageous.

2.8 Planning and Scheduling In an entirely different vein of research, the artificial intelligence community has evolved two related fields - planning and scheduling - whose overarching goal is to create feasible sequences of activities that start from a set of preexisting conditions and achieve a desired set of goal conditions. Planning decomposes high-level goals into atomiclevel activities that collectively achieve the goals. There may be many alternate ways to break tasks into subtasks, and activities may have complex interrelationships that prevent loose ordering. Scheduling takes a set of activities and determines an ordering that respects constraints and resource demands to accomplish an overall task.

Automated activity planning and scheduling software has been successfully deployed on spacecraft and prototype planetary rovers. The Remote Agent Experiment demonstrated automated planning and scheduling onboard the Deep Space 1 spacecraft [4], [3]. The planner/scheduler software (PS) accessed a database of long-term mission objectives and planned concurrent activity schedules over multi-day planning horizons. The PS derived planning problems by taking goals relevant to the planning horizon and projecting initial spacecraft conditions to the anticipated plan execution time. Beginning with an incomplete plan, the PS searched over plan space, adding constraints and subgoals where necessary and reordering activities, to create full partially-ordered plans. The PS also maintained onboard state predictions, for example resource levels, under the same model as activities in primitives collectively termed tokens.

ASPEN was developed to automate planning and scheduling for spacecraft and rovers [10]. The software uses a most-committed, local, heuristic iterative repair approach to decompose high-level mission goals into concurrent action sequences that respect operational and resource constraints. Because the search is not systematic, there is no guarantee that all combinations of actions will be searched exhaustively, or that disadvantageous sequences will not be examined more than once. However, ASPEN achieves planning, scheduling and resource management at far less computational expense than for more flexible, exhaustive approaches. The ASPEN system and the derivative CASPER system each produced coordinated activity schedules, based on science and engineering team requests, for the JPL Rocky 7 rover (see Figure 2-2). The activity planners repair plans in response to changing goals and other


unexpected events. Rover activity scheduling considers resources and environment effects (e.g. day/night cycle, sun angle), but demonstrates only loose coupling to path planning. ASPEN calls a path planner that is ignorant of absolute time and resources to estimate the duration of small traverses. ASPEN’s primary focus is on conflict resolution through event rescheduling or reordering. Furthermore, ASPEN and CASPER essentially react to evolving initial state and updated mission goals. Neither has the ability to plan in anticipation of a range of possible outcomes, and so cannot build in contingency branches to plans.

–  –  –

2.8.1 Contingency Planning Contingency planning is addressed by Bresina and Washington under the Contingent Rover Language (CRL) and the propagation of expected utility distributions [6]. Combining the action condition structure of classical planning and conditional rewards characteristic of decision-theoretic planning, the authors present a means of efficiently evaluating contingent branches in an existing plan. The method specifies probability distributions on execution times for all events, and defines local rewards conditioned on action success or failure. Valid action execution is defined under start, wait-for, maintain and end conditions, which include requirements on initial available resources. The method assumes knowledge of resource availability as a function of time. Given an existing plan with conditional branches, the algorithm first forward-propagates distributions of possible action start times, given action duration distributions and conditional requirements on actions, to establish temporal bounds on outcomes. Then, it backward-propagates distributions of utility from the branch endpoints, restricting computation to the time distributions. The resulting util



ity distributions specify the expected value of executing each branch, conditioned on start time. The advantage under this approach is that the utility distributions remain valid regardless of the temporal outcome of actions, as long as the resource bound model also remains valid. Though this approach pre-supposes a profile of resource availability, it estimates contingent branch utility factoring in whether actions can be legally executed. An extension of contingent planning that reasoned about uncertainty in activity time and resource consumption, using CRL and the Pico planner (based on EUROPA [28]), was used to successfully demonstrate multi-target single-cycle instrument placement on the K9 rover [50].

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 26 |

Similar works:

«SHAKESPEARE‟S TELLING WORDS: GRAMMAR, LINGUISTIC ENCOUNTERS, AND THE RISKS OF SPEECH by Alysia Michelle Kolentsis A thesis submitted in conformity with the requirements for the degree of Doctor of Philosophy Graduate Department of English University of Toronto © Copyright by Alysia Michelle Kolentsis (2008) ii Shakespeare‟s Telling Words: Grammar, Linguistic Encounters, and the Risks of Speech Alysia Michelle Kolentsis Doctor of Philosophy Department of English University of Toronto...»

«Komplexitat einer kunstlichen Intelligenz vorgelegt von Diplom-Informatiker Dr.-Ing. Achim Ho mann aus Backnang Vom Fachbereich Kommunikationsund Geschichtswissenschaft der Technischen Universitat Berlin genehmigte Dissertation zur Erlangung des akademischen Grades Doktor der Philosophie Promotionsausschu : Vorsitzender: Prof. Dr. Karl Heinz Stahl Berichter: Prof. Dr. Christoph Hubig Berichter: Prof. Dr. Hans Poser Berichter: Prof. Dr. Bernd Mahr (FB 20) Tag der wissenschaftlichen Aussprache:...»

«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 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...»

«Wittgenstein and the Future of Philosophy Wittgenstein und die Zukunft der Philosophie A Reassessment after 50 Years Eine Neubewertung nach 50 Jahren Beiträge der Österreichischen Ludwig Wittgenstein Gesellschaft Contributions of the Austrian Ludwig Wittgenstein Society Editorial Board Elisabeth Leinfellner Rudolf Haller Werner Leinfellner Klaus Puhl Paul Weingartner Volume IX (1) Band IX (1) Wittgenstein und die Zukunft der Philosophie Eine Neubewertung nach 50 Jahren Beiträge des 24....»


«© Copyright 2005 Joseph Tate SHAKESPEARE, PROSE AND VERSE: UNREADABLE FORMS Joseph Tate A dissertation submitted in partial fulfilment of the requirements for the degree of Doctor of Philosophy University of Washington Program Authorized to Offer Degree: Department of English University of Washington Graduate School This is to certify that I have examined this copy of a doctoral dissertation by Joseph Tate and have found that it is complete and satisfactory in all respects, and that any and...»

«DIPLOMARBEIT Titel der Diplomarbeit „na wos ge / ge wos na“ Die Konkrete Dichtung und Dialektdichtung der Wiener Gruppe aus sprachwissenschaftlicher Sicht Verfasserin Verena Maria Weigl angestrebter akademischer Grad Magistra der Philosophie (Mag.a phil.) Wien, 2010 Studienkennzahl lt. Studienblatt: A 332 Studienrichtung lt. Studienblatt: Diplomstudium Deutsche Philologie Betreuer: Ao. Univ.-Prof. Mag. Dr. Franz Patocka II Danksagung Zuallererst möchte ich meinen Eltern großen Dank für...»

«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...»

«MAN AND SUPERMAN A COMEDY AND A PHILOSOPHY George Bernard Shaw This public-domain (U.S.) text was produced by Eve Sobol, South Bend, Indiana, USA. The Project Gutenberg edition (designated “mands10”) was subsequently converted to LTEX using GutenMark software and reA edited by Ron Burkey. The text of the Appendix, “The Revolutionist’s Handbook,” which was omitted from the Project Gutenberg edition, has been restored from alternate online sources (www.bartleby.com). Report problems to...»

«A Second Refuge French Opera and the Huguenot Migration, c. 1680 – c. 1710 By Rebekah Susannah Ahrendt A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Music in the Graduate Division of the University of California, Berkeley Committee in charge: Professor Kate van Orden, Chair Professor Richard Taruskin Professor Peter Sahlins Fall 2011 A Second Refuge French Opera and the Huguenot Migration, c. 1680 – c. 1710 Copyright 2011 by...»

<<  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.