FREE ELECTRONIC LIBRARY - Books, abstracts, thesis

Pages:     | 1 |   ...   | 8 | 9 || 11 | 12 |   ...   | 26 |

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

-- [ Page 10 ] --

The approaches also seek optimal energy paths in totally different ways. As explained in Section 3.1.7, both approaches must either limit plan length or promote shorter plans to avoid the problems of heuristic search for nonmonotonic costs. Approach 1 (4-D BESTDPARMS) seeks an optimal energy solution indirectly, since it uses a duration-based objective function as the mechanism for limiting plan duration. The objective function tracks the duration of candidate paths, and prevents paths that exceed a maximum duration. This prevents the search from lingering at states that provide negative costs. Under this limit, ISE uses state equivalence class pruning and state dominance to remove less desirable states. Within time-energy DPARMS classes, the better ( X, Y ) function favors states that have lower required energy. Within time DPARMS classes (but across energy DPARMS classes), the dominates ( X, Y ) function also favors states with lower required energy. The optimal solution in Approach 1 is one that falls below the given maximum path duration, and whose initial state is “best”.


Approach 2 (3-D BESTPCOST) contains energy directly in its objective function. The plan length cost in the composite objective function provides incentive to avoid lingering at regions of negative cost. The objective function applies a path length penalty K at every step in the path. This contrasts with Approach 1, which does not penalize extra steps as long as the plan duration is shorter than the given maximum. At any step in the Approach 2 search, the plan length cost K can potentially cancel out the resource cost ∆e. Consequently, there is no admissible heuristic to focus the search. Finally, in Approach 2, with energy removed from the DPARMS, no state dominance relationship exists. So, despite the advantage of having fewer dimensions to search, Approach 2 has fewer other mechanisms to help focus the search and to prune unnecessary states.

Approach 2 has some other disadvantages. Any arc transition must be a function of state (IPARMS and DPARMS) and action alone. Since the energy parameter e is not in the DPARMS, costs in Approach 2 cannot depend on energy.

In this particular domain, there are no costs that depend on energy, but in general this could be limiting. For example, it would be impossible to model a battery whose discharge rate is a function of its state of charge in the Approach 2 formulation.

More importantly, Approach 2 is incomplete (in the planning sense) with respect to energy. Reasoning about state, defined by position and time, does not consider energy. In the event that one branch of a search does not yield feasible paths, it cannot backtrack to different regions of the energy space, since it is not represented in the IPARMSDPARMS state. Paths that are eliminated due to high cost cannot be regenerated. In Approach 1, states that are dominated (and deleted) can be regenerated if it is discovered that the originally dominant states do not lead to a feasible solution. In practice, the incompleteness of Approach 2 does not interfere with finding paths in a wide range of situations.

Having introduced the example planning domain and the two candidate ISE approaches, the remaining sections assess the performance of ISE in response to various parameter changes. The tests to determine performance scaling with map size, DPARMS class resolution and branching factor (Sections 3.4.3 - 3.4.5) and to compare planning and re-planning (Section 3.4.6) all used Approach 2 (3-D BESTPCOST mode). Sections 3.4.7 and 3.4.8 compare the Approaches in terms of performance and solution quality. All tests were run on a Pentium 4, 2.99 GHz processor, with 1 GB of RAM.

3.4.3 Scaling With Map Size or Start-Goal Separation Map size refers to the number of IPARMS levels - the IPARMS dimensions of the 2-D spatial portion of the space.

The experiment varied the size of square maps ( x and y axes 50, 100, 150 and 200 cells each), with start and goal positions at opposite map corners. Tests measured the time required to solve the planning problem under increasingly large map sizes and start-goal separation, using Approach 2 described above. Twenty tests were run for each map


size, each on a different independently and pseudo-randomly-generated cost map. Figure 3-3 plots the ISE initial planning duration as a function of map size and confirms the intuition that a larger map size results in greater planning time. For each doubling of map dimension (quadrupling the number of IPARMS sets), the planning time increases roughly by a factor of 10. Computation should, in theory, be O ( N log N ) in the size of the search space.

However, this study does not examine increasing the IPARMS resolution but rather increasing the span of the IPARMS.

On the surface, doubling the span of IPARMS would be appear to quadruple the state space. However, the DPARMS time dimension is open ended; the DPARMS time dimension grows to contain all the states expanded in the search.

By expanding the size of the map, the distance between the start and goal increases, as does the duration of plans considered by a search. The size of the DPARMS time dimension is coupled to the distance between the start and goal position. An increase in the IPARMS dimensions actually increases the DPARMS span proportionally. The extra multiplicative effect seen in planning computation in Figure 3-3 may be explained by this coupling.

3.4.4 Scaling With Resolution An ISE user can vary the resolution for DPARMS equivalence classes. Recall that DPARMS equivalence classes group states that are considered sufficiently similar for resolution equivalence pruning (Section 3.2.2) and state dominance (Section 3.2.3) at each step in the search. They also define the resolution at which goal states can be specified, and the accuracy with which planning can match start state DPARMS parameters to actual initial conditions.

Tests in this study varied the resolution of the time variable DPARMS for various map sizes. As with the map size study, each combination of map size and resolution was tested 20 times, using 20 independently, randomly-generated cost maps. Figure 3-3 shows the performance benefit of decreasing resolution in the DPARMS. Given base time units, the study examined DPARMS equivalence class resolutions of 30, 60, 120 and 240 units per bin. Each curve in the plot corresponds to one of the resolutions. Each map size results in a different mean plan duration (the time the plan requires to travel from the start to the goal). Therefore, bin size represents a different fraction of the entire time DPARMS axis depending on the separation between goal and start. The number of 30 unit bins required to span the mean duration of plans was 27.7 for the 50-by-50 map, 62.8 for the 100-by-100 map, and 85.3 for the 150-by-150 map. The search will tend to populate approximately the number of time DPARMS bins required to span the solution. As shown in the plot, by halving the resolution at a given map size, the planning time decreases by a factor of between 2.4 and 2.7.

–  –  –

3.4.5 Scaling with Branching Factor The number of available transition arcs from each IPARMS state is application-specific. This number equates to a branching factor in the search graph that affects both performance and path cost. For Approach 2 (3-D BESTPCOST) planning, experiments recorded the time required to solve for a plan under two transition arc models - the original, eight-neighbor arc set, and a reduced, four-neighbor arc set in which arcs were restricted to horizontal and vertical motions. In both cases, the start and goal positions were on opposite corners of a square map. Twenty experiments were run for each combination of map size, DPARMS time resolution and branching factor.

In a standard state representation, with a fine resolution in the dependent variable, the branching factor determines the exponential rate of state proliferation. A larger branching factor would lead to exponentially more states. Figure 3-4 demonstrates the power of state resolution pruning, with the eight-connected planning shown in solid lines and the four-connected planning shown in dotted lines. Somewhat counter-intuitively, Figure 3-4 shows that the eight-connected state space requires nearly the same time as the four-connected case. For ISE, branching factor does not sub



stantially affect the time complexity of the search, because at each step, state resolution pruning discards states that are deemed inferior in each DPARMS state resolution bin. At each expansion step, the number of states in each IPARMS set remains roughly constant over the search, regardless of the branching factor. The number of states to expand depends more on the number of DPARMS equivalence bins are spanned by the search. ISE prevents the state explosion that would have occurred in a standard search, and yet represents dependent state variables at a fine resolution.

Figure 3-4: Time for Four and Eight Connected State Spaces for Approach 2 (BESTPCOST).

3.4.6 Re-Planning Performance ISE re-planning was designed to efficiently repair plans in response to changes in arc costs near the start state. A set of tests compared the time required to plan from scratch versus re-planning in response to changes on an existing cost map. Cost map updates were restricted to four modifications within 4 x 4 cell windows for various map sizes and DPARMS resolutions (30, 60, 120 and 240 time units). In each test, planning was first conducted on a base cost map.

The modifications were made to the costs on the original map, and re-planning repaired the initial ISE graph. The time required for the re-plan was compared against the time required to plan from scratch on the modified cost map.


Figure 3-5 compares the time to re-plan in comparison to planning from scratch, in response to cost updates near the start position. All cases show improvement over planning from scratch, especially at lower resolution. For larger map sizes, re-planning enables a factor of better than 100 speedup relative to initial planning. For smaller maps, modifications affect a greater portion of the entire map. The work of re-planning comes closer to replicating the work of initial planning, explaining the reduced benefits shown in the left side of the figure. Lower resolution in DPARMS axes reduces the influence of changes in the cost map on other DPARMS equivalence classes, thereby reducing the work to repair the graph.

Figure 3-5: Ratio of Re-Plan Time to Initial Plan Time for Approach 2 (3-D BESTPCOST). Re-planning shows one to two orders of magnitude improvement on speed over initial planning.

3.4.7 Scaling With Solution Approach Tests compared the time demands for the BESTDPARMS (4-D) mode and BESTPCOST (3-D) modes. Experiments demonstrate that varying the number of state parameter dimensions strongly affects the time demands of the algorithm. For these experiments, a set of 50 cost maps was generated for each combination of map size (50, 100 and 150 cells per IPARMS dimension) and DPARMS time resolution (60, 120 and 240 time units). First, the experiments ran Approach 2 on 50 maps to record the planning performance for 3-D search, as well as the durations of the resulting plan solutions for each cost map. The experiments then ran Approach 1 on the same 50 cost maps, using the Approach 2 solution plan duration as an upper bound on plan cost1.


Figure 3-6 compares the time demands of Approach 1 (4-D BESTDPARMS) and Approach 2 (3-D BESTPCOST) for these experiments. The dotted lines correspond to Approach 1, and solid lines, to Approach 2. We immediately observe that the lower dimensionality of Approach 2 yields a sizeable time performance gain - for a given resolution and map size, Approach 2 is several times faster than Approach 1. This conforms to the notion that adding a dimension exponentially increases the number of states that a search must expand and represent in the search graph.

Figure 3-6: Comparison of Approach 1 and Approach 2 Time Performance

3.4.8 Qualitative Comparison of Approaches Figure 3-7 and Figure 3-8 illustrate the qualitative differences between Approach 1 (BESTDPARMS) and Approach 2 (BESTPCOST) through plots of path, energy and progress distance. The path plots show the physical route in XY space taken by the plan, starting at the start position in the upper right corner, to the goal in the lower left corner. In line with the description of ISE resource variables in Section 3.1.5, each energy plot shows the profile of minimum required energy in the battery in order to reach the goal, as a function of plan step. Progress distance is a measure of the direct progress made to toward the goal. It is calculated as the Euclidean distance between the start and goal,

1. Admittedly, this may have disadvantaged Approach 1 in terms of minimum energy solution, but provided a way to more evenly compare the two approaches. Section 3.4.8 suggests that Approach 1 is able to find shorter duration solutions than Approach 2 (making this a viable test strategy for performance tests), but that the shorter duration solutions are typically far inferior in terms of energy.


minus the Euclidean distance remaining to the goal from the current robot position (for a more detailed definition, consult Appendix 2). Under this definition, progress is only made when the radius between the robot and the goal is reduced. The progress plots show progress distance as a function of plan step.

Figure 3-7 compares the BESTPCOST mode (the left column of plots - Figure 3-7a, b, c) to the BESTDPARMS mode (the right column of plots - Figure 3-7d, e, f). In this experiment, the upper bound on plan duration for the BESTDPARMS approach was set to the duration of the BESTPCOST solution (5150 time units), as in the performance comparison of Section 3.4.7. This is the BESTDPARMS Case A.

Pages:     | 1 |   ...   | 8 | 9 || 11 | 12 |   ...   | 26 |

Similar works:

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

«Proceedings von Nachdenken und Vordenken – Herausforderungen an die Philosophie Herausgeber: Oliver Petersen, Dagmar Borchers, Thomas Spitzley, Manfred Stöckler Proceedings von GAP.7 Nachdenken und Vordenken – Herausforderungen an die Philosophie Herausgeber: Oliver Petersen, Dagmar Borchers, Thomas Spitzley, Manfred Stöckler Online-Veröffentlichung der Universität Duisburg-Essen (DuEPublico) ISBN 978-3-00-036440-2 Vorwort Vom 14.-17.9.2009 fand in Bremen der siebte Internationale...»

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

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

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

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

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

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

«Studia Lingüistica Germanica Herausgegeben von Stefan Sonderegger Walter de Gruyter • Berlin • New York Elisabeth Leiss Die Verbalkategorien des Deutschen Ein Beitrag zur Theorie der sprachlichen Kategorisierung Walter de Gruyter • Berlin • New York UniversitaxsBibüothek I ; ^ ^ J f N Q. / 1/ ( München 1 J •^ Als Habilitationsschrift auf Empfehlung der Philosophischen Fakultät II der Universität Erlangen-Nürnberg gedruckt mit Unterstützung der Deutschen Forschungsgemeinschaft...»

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

«Photopoetry and the Bioscopic Book: Russian and Czech Avant-Garde Experiments of the 1920s by Aleksandar Bošković A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Slavic Languages and Literatures) in the University of Michigan Doctoral Committee Professor Jindřich Toman, Co-Chair Assistant Professor Tatjana Aleksić, Co-Chair Professor Matthew Nicholas Biro Professor Yuri Tsivian, University of Chicago © Aleksandar Bošković For my...»

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