FREE ELECTRONIC LIBRARY - Books, abstracts, thesis

Pages:     | 1 |   ...   | 14 | 15 || 17 | 18 |   ...   | 26 |

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

-- [ Page 16 ] --
than would be limited by unbounded sequential goal planning alone, it could also limit how late downstream goals can be completed, under the minimum allowable speed restriction. It is pointless to plan for goal completion times that can only be reached by slower-than-allowable speeds. Therefore, the algorithm must determine which time limitation is more constraining - the latest allowable time from unbounded sequential goal planning, or the propagated effect of earlier goal time bounds.

–  –  –

00:00 06:00 12:00 18:00 00:00 06:00 12:00

–  –  –

00:00 06:00 12:00 18:00 00:00 06:00

–  –  –

00:00 06:00 12:00 18:00 00:00 06:00 12:00 18:00 06:00 12:00 18:00 00:00 06:00 12:00 00:00

–  –  –

Figure 4-9: Initialization for Time-Bounded Sequential Goal Planning: a) Originally-specified reachable and allowable time limits; b) Earlier goal-imposed allowable time limit; c) Goal time interval definitions; d) Final segment goal states and query start states


Figure 4-8b shows that the time bound for goal N-1 limits the goal interval for goal N. The projection of the slowest allowable speed for segment N, summed with the goal N action duration, is earlier than the end of the original allowable time interval. Any arrival time later than this new time would require an approach to goal N by a slower-thanallowable speed.

Returning back to Table 4-9, in computing the final goal allowable time interval, the algorithm searches to find the last time-bounded goal in the goal sequence (L62 and L63). It projects the latest allowable time from the end of that goal time bounds to the final goal ( t max1, from L64), and keeps the minimum of t max1 and t max2 as the true closing time (L66 and L73). For earlier start intervals, the time bounds propagate from the next latest goal interval just as with INIT_SEGMENTS ( S, Γ, k ) (L70 and L71). The only difference is that the overall goal time interval is the intersection of three time ranges - the reachable, allowable and goal-limited time bounds.

Figure 4-8c shows the effect of the intersection. In the specific case of goal N-1, the latest allowable time falls later than the mission-imposed goal time bounds. The intersection removes a large time interval from the allowable unbounded sequential goal range from consideration. In the case of goal 2, the latest allowable time falls earlier than the mission-imposed bounds, causing the minimum allowable speed restriction to take precedence. For goal 1, no mission-imposed time bounds exist, and so again, the minimum allowable speed restriction takes precedence.

Importantly, if at any time during the initialization a goal time interval is computed to be empty, the mission, as specified, is infeasible.

The new initialization procedure is all that is required to enable TEMPEST to plan and re-plan for time-bounded sequential goals. Once segments are initialized, either prior to planning or in response to execution updates, PLAN_SEQ_GOALS ( S, Γ ) solves for the plan that obeys the temporal bounds on goal completion.

4.4 Plans TEMPEST plans consist of a fully-ordered sequence of state-action pairs, called waypoints, corresponding to the

states and arcs that follow the optimal path from the start state, through all intermediate goals, to one of the designated final goal states. A plan π with N waypoints takes the form:

–  –  –

Each state is an aggregation of the ISE IPARMS, DPARMS and auxiliary resource variables for the application. The corresponding action is the action departing from the state.

As a sequence of waypoints, a plan acts as a guide for path execution whose granularity is defined by the resolution of the spatial coordinates and the other state variables. Each action in the plan must be initiated as close as possible to the position and time of the waypoint. Each resource variable specifies the minimum resource level that must remain in order to satisfy all the goals in the plan, as described in Chapter 3, Section 3.1.5. A deviation from plan position greater than the spatial resolution of the map, or in timing greater than the time equivalence class resolution may justify re-planning. Similarly, if any resource falls below the recommended minimum level as dictated by the plan, successful re-planning is necessary to ensure mission completion.

4.5 Plan Evaluation In evaluating TEMPEST planning behaviors, it is useful to introduce some approaches for analyzing plans. Plan solutions are often difficult to interpret. Even when a planner produces formally correct and optimal plans, it is not immediately obvious whether plans display a desired behavior, how much of a behavior to attribute to artifacts of representation versus to good planning, or how to compare plans stemming from alternate approaches. This section presents some simple analysis tools that help with this problem.

4.5.1 Distance Plan distance is an important path planning measure. For many path planners, minimizing feasible path length is the single objective. Though minimizing path length is not the only objective for TEMPEST, it is still very important. In many cases, the shortest path is the least costly in terms of resources, mechanical stress and vehicle risk. This thesis introduces two factors that describe a plan’s increase in path length above the planar Euclidean distance between goals.


Figure 4-10: Representation Factor for Regular Four and Eight-Connected Grids Representation Factor f R : This factor encodes the ratio of the minimum distance possible under the planner’s state

representation ( D rep ) to the planar Euclidean map distance ( D map ) such that:

–  –  –

Representation factor encodes how much a planner’s underlying spatial representation contributes to an extension of path length beyond the minimum. Representation factor has a minimum value of 1, and a maximum value that depends on the system of spatial representation. TEMPEST uses a grid-based representation for terrain. Actions transition between cells in the grid and their eight nearest neighbors, forming an eight-connected graph. The minimum eight-connected plan distance between two points depends on the ratio of their relative grid distance in the xcoordinate (∆x) and the y-coordinate (∆y). When the start and goal lie along a common horizontal (∆x/∆y= ∞ ), vertical (∆x/∆y=0) or principle diagonal axis of the graph (∆x/∆y=1 or ∆x/∆y=-1), the minimum eight-connected distance

–  –  –

is equal to the Euclidean map distance between the points ( f R = 1 ). Since the eight-connected path cannot assume arbitrary headings, other ratios of ∆x-to-∆y produce indirect paths whose path lengths exceed the Euclidean distance between the points ( fR 1 ). Figure 4-10 plots f R for both four- and eight-connected motion on regular grids given the relative positioning of the start and goal. The four-connected graph, corresponding to the “Manhattan distance”, yields a worst-case error of 2 for two points directly on a diagonal. At worst, the eight-connected graph contributes a 8.2% increase in path length.

Avoidance Factor fA : This factor encodes the ratio of the plan distance ( D plan ) to the minimum distance possible

under the planner’s state representation ( D rep ) such that:

–  –  –

Avoidance factor captures the amount of extra distance, inserted by a planner, to avoid obstacles and sub-optimal regions. Its minimum value is one, and its maximum value is unbounded. It is important to note that an avoidance factor of 1 does not mean that the path it describes has not avoided obstacles or areas of high cost. In general, a path with the minimum representation distance D rep is not unique, and has many degrees of freedom with which to avoid obstacles or high cost areas. Observe in Figure 4-11 that the solid paths are all of minimum length under an eightconnected grid representation f A = 1, and yet avoid obstacles. The dashed path, however, covers more distance, and so has an avoidance factor greater than one.

–  –  –

For plans solved under an objective function that minimizes path length, avoidance factor will be greater than 1 only if obstacles prevent all paths yielding the minimum representation distance Drep between points. For objective functions that minimize some other quantity, like duration or energy expense, an avoidance factor greater than one may indicate a deviation in path to avoid a costly region.


4.5.2 Time In temporal planning, where actions are not necessarily mobile, plan duration is a more appropriate measure of plan length than distance. For mobile actions, the distance factors in Section 4.5.1 also encode the increase in plan duration due to increased path length. Beyond this, stationary actions inserted into a plan also cause an increase in plan

duration. If the minimum map traverse time and total duration of goal actions are defined respectively as:

–  –  –

Slower driving speed and additional stationary actions inserted into the plan motivate the following additional factor:

Loiter Factor f L : This factor encodes the ratio of the minimum plan duration, considering traverse time and goal

action durations, to the actual plan duration, such that:

–  –  –

Loiter factor expresses the degree to which a plan specifies less-than-maximum driving speed or stationary actions beyond the goal actions.

4.6 Simulation Results 4.6.1 Re-Planning We present a sample planning problem to illustrate TEMPEST behaviors. A contour map in Figure 4-12 shows the elevation profile for synthesized terrain on a mock Martian surface. Mountains form a central pattern of valleys running in a North-South (up-down) direction, and a rounded crater lies to the northeast. The rover starts in the morning at the southeast corner of the map (“Start”), and must traverse to the northwest corner (“Goal 2”). Scientists designate a Via Point goal in the valley, “Goal 1”, to promote travel through the valley en route to the final destination. Mission engineers (or an onboard planner-scheduler) require the robot to reach Goal 2 with 100 W-hr of charge left for subsequent operations.


Unfortunately, the elevation map provided to the rover is incorrect. Its preliminary map indicates a clear exit from the valley system at its northern extreme, between two peaks. The actual terrain involves a far higher and steeper pass, beyond the locomotion capability of the rover.

In this example, a simple simulation of the mission demonstrates the value of TEMPEST. At each plan step, the simulated rover plans a path from its current state, then “executes” the first step of the plan through path integration. At each new point, the rover “senses” the local environment, detecting the actual elevation, slope and lighting of all cells within two pixels. Based on this new data, TEMPEST re-plans a path and the process continues.

Figure 4-12: Initial Plan Route: TEMPEST plans a path from “Start” at the southeast of the map, to Goal 1 in the valley in the center of the map, and then through the saddle point to Goal 2 in the northwest.

Figure 4-12 shows the initial TEMPEST plan route. With the exception of a few minor path deviations, the route follows a direct path from the start through each of the goals. Subsequent re-plans during “execution” yield similar routes. The solid red curve in Figure 4-14 shows the timing for the initial plan. The slope of the curve represents the rover speed toward Goal 2. One observes that it is only slightly slower than the theoretical fastest, straight-line approach, as shown by the steep dash-dot line. The red solid line in Figure 4-15 shows the required battery energy profile for the initial plan. The plan allows the robot to begin with an empty battery, and only requires increasing


charge at the end of the plan to meet the Goal 2 requirement. This indicates that solar energy provides ample energy for locomotion.

The simulated rover reaches the Goal 1 Via Point and continues without stopping toward Goal 2. The nearest valley exit, according to its internal elevation map, lies to the northwest directly in line with its next goal. However, as it approaches the supposed low pass, the robot detects the steep, intraversible pass. Figure 4-13 shows the first substantial re-plan in the sequence, based on this discovery. With no escape to the northwest, TEMPEST selects the least expensive alternative - a detour through a narrow valley to the northeast (the blue dashed line). This new route is a significant departure from the original. The extra distance means that the robot cannot reach Goal 2 before sundown.

–  –  –

The original plan did not anticipate the extra burden of nightfall on battery reserves. However, TEMPEST determines a prolonged Charge action followed by overnight Hibernation will enable it to reach Goal 2 by late morning the following day. Figure 4-14 shows the rate of travel towards Goal 2 for the detour as a dashed blue line. Note that the robot must first reverse course, and then remains stationary for nearly 18 hours, first in sunlight (charging batteries),

–  –  –

then overnight (hibernating, in the shaded region). The following morning, the rover continues its course around the mountain, then moves to Goal 2.

Figure 4-14: Progress Distance vs. Time: The initial plan (shown in red) follows a very direct path (compare to the straight-line maximum speed curve). The re-plan detour (shown in blue) requires the rover to endure a night in hibernation, as shown by the flat region indicating no forward progress. In the morning of the following day, the rover resumes its course to Goal 2.

Pages:     | 1 |   ...   | 14 | 15 || 17 | 18 |   ...   | 26 |

Similar works:

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

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

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

«Clustering Categorical Data Using Data Summaries and Spectral Techniques By Eman Abdu A dissertation submitted to the Graduate Faculty in Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy, The City University of New York ©2009 Eman Abdu All Rights Reserved ii This manuscript has been read and accepted for the Graduate Faculty in Computer Science in satisfaction of the dissertation requirement for the degree of Doctor of Philosophy. _ _ Date...»

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

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

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

«DR. WOLFGANG THORWART Dozent für Philosophie und Literatur Goethes Naturund Gottesbegriff Johann Wolfgang Goethes (1749-1832) Lebensspanne fiel größtenteils in die allgemeine Zeitenwende des späten 18. Jahrhunderts, die man heute eine “Sattelzeit” nennt. Es ist die Epoche der Hochaufklärung mit ihrer allgemeinen Aufwertung der menschlichen Fähigkeiten, nachdem man die Menschen im Namen der göttlichen Vernunft ein Jahrtausend zur Verleugnung der menschichen Fähigkeiten gezwungen...»

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

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

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

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

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