Matching Items (39)
Filtering by
- Member of: Theses and Dissertations
Description
In this dissertation I develop a deep theory of temporal planning well-suited to analyzing, understanding, and improving the state of the art implementations (as of 2012). At face-value the work is strictly theoretical; nonetheless its impact is entirely real and practical. The easiest portion of that impact to highlight concerns the notable improvements to the format of the temporal fragment of the International Planning Competitions (IPCs). Particularly: the theory I expound upon here is the primary cause of--and justification for--the altered (i) selection of benchmark problems, and (ii) notion of "winning temporal planner". For higher level motivation: robotics, web service composition, industrial manufacturing, business process management, cybersecurity, space exploration, deep ocean exploration, and logistics all benefit from applying domain-independent automated planning technique. Naturally, actually carrying out such case studies has much to offer. For example, we may extract the lesson that reasoning carefully about deadlines is rather crucial to planning in practice. More generally, effectively automating specifically temporal planning is well-motivated from applications. Entirely abstractly, the aim is to improve the theory of automated temporal planning by distilling from its practice. My thesis is that the key feature of computational interest is concurrency. To support, I demonstrate by way of compilation methods, worst-case counting arguments, and analysis of algorithmic properties such as completeness that the more immediately pressing computational obstacles (facing would-be temporal generalizations of classical planning systems) can be dealt with in theoretically efficient manner. So more accurately the technical contribution here is to demonstrate: The computationally significant obstacle to automated temporal planning that remains is just concurrency.
ContributorsCushing, William Albemarle (Author) / Kambhampati, Subbarao (Thesis advisor) / Weld, Daniel S. (Committee member) / Smith, David E. (Committee member) / Baral, Chitta (Committee member) / Davalcu, Hasan (Committee member) / Arizona State University (Publisher)
Created2012
Description
Research indicates that projected increases in global urban populations are not adequately addressed by current food production and planning. In the U.S., insufficient access to food, or the inability to access enough food for an active, healthy life affects nearly 15% of the population. In the face of these challenges, how are urban planners and other food system professionals planning for more resilient food systems? The purpose of this qualitative case study is to understand the planning and policy resources and food system approaches that might have the ability to strengthen food systems, and ultimately, urban resiliency. It proposes that by understanding food system planning in this context, planning approaches can be developed to strengthen urban food systems. The study uses the conceptual framework of urban planning for food, new community food systems, urban resiliency, and the theory of Panarchy as a model for urban planning and creation of new community food systems. Panarchy theory proposes that entrenched, non-diverse systems can change and adapt, and this study proposes that some U.S. cities are doing just that by planning for new community food systems. It studied 16 U.S. cities considered to be leaders in sustainability practices, and conducted semi-structured interviews with professionals in three of those cities: Portland, OR; San Francisco, CA; and Seattle, WA. The study found that these cities are using innovative methods in food system work, with professionals from many different departments and disciplines bringing interdisciplinary approaches to food planning and policy. Supported by strong executive leadership, these cities are creating progressive urban agriculture zoning policies and other food system initiatives, and using innovative educational programs and events to engage citizens at all socio-economic levels. Food system departments are relatively new, plans and policies among the cities are not consistent, and they are faced with limited resources to adequately track food system-related data. However they are still moving forward with programming to increase food access and improve their food systems. Food-system resiliency is recognized as an important goal, but cities are in varying stages of development for resiliency planning.
ContributorsTaylor, Constance M (Author) / Talen, Emily (Thesis advisor) / Crewe, Katherine (Committee member) / Pijawka, David (Committee member) / Arizona State University (Publisher)
Created2014
Description
Current work in planning assumes that user preferences and/or domain dynamics are completely specified in advance, and aims to search for a single solution plan to satisfy these. In many real world scenarios, however, providing a complete specification of user preferences and domain dynamics becomes a time-consuming and error-prone task. More often than not, a user may provide no knowledge or at best partial knowledge of her preferences with respect to a desired plan. Similarly, a domain writer may only be able to determine certain parts, not all, of the model of some actions in a domain. Such modeling issues requires new concepts on what a solution should be, and novel techniques in solving the problem. When user preferences are incomplete, rather than presenting a single plan, the planner must instead provide a set of plans containing one or more plans that are similar to the one that the user prefers. This research first proposes the usage of different measures to capture the quality of such plan sets. These are domain-independent distance measures based on plan elements if no knowledge of the user preferences is given, or the Integrated Preference Function measure in case incomplete knowledge of such preferences is provided. It then investigates various heuristic approaches to generate plan sets in accordance with these measures, and presents empirical results demonstrating the promise of the methods. The second part of this research addresses planning problems with incomplete domain models, specifically those annotated with possible preconditions and effects of actions. It formalizes the notion of plan robustness capturing the probability of success for plans during execution. A method of assessing plan robustness based on the weighted model counting approach is proposed. Two approaches for synthesizing robust plans are introduced. The first one compiles the robust plan synthesis problems to the conformant probabilistic planning problems. The second approximates the robustness measure with lower and upper bounds, incorporating them into a stochastic local search for estimating distance heuristic to a goal state. The resulting planner outperforms a state-of-the-art planner that can handle incomplete domain models in both plan quality and planning time.
ContributorsNguyễn, Tuấn Anh (Author) / Kambhampati, Subbarao (Thesis advisor) / Baral, Chitta (Committee member) / Do, Minh (Committee member) / Lee, Joohyung (Committee member) / Smith, David E. (Committee member) / Arizona State University (Publisher)
Created2014
Description
As robotic technology and its various uses grow steadily more complex and ubiquitous, humans are coming into increasing contact with robotic agents. A large portion of such contact is cooperative interaction, where both humans and robots are required to work on the same application towards achieving common goals. These application scenarios are characterized by a need to leverage the strengths of each agent as part of a unified team to reach those common goals. To ensure that the robotic agent is truly a contributing team-member, it must exhibit some degree of autonomy in achieving goals that have been delegated to it. Indeed, a significant portion of the utility of such human-robot teams derives from the delegation of goals to the robot, and autonomy on the part of the robot in achieving those goals. In order to be considered truly autonomous, the robot must be able to make its own plans to achieve the goals assigned to it, with only minimal direction and assistance from the human.
Automated planning provides the solution to this problem -- indeed, one of the main motivations that underpinned the beginnings of the field of automated planning was to provide planning support for Shakey the robot with the STRIPS system. For long, however, automated planners suffered from scalability issues that precluded their application to real world, real time robotic systems. Recent decades have seen a gradual abeyance of those issues, and fast planning systems are now the norm rather than the exception. However, some of these advances in speedup and scalability have been achieved by ignoring or abstracting out challenges that real world integrated robotic systems must confront.
In this work, the problem of planning for human-hobot teaming is introduced. The central idea -- the use of automated planning systems as mediators in such human-robot teaming scenarios -- and the main challenges inspired from real world scenarios that must be addressed in order to make such planning seamless are presented: (i) Goals which can be specified or changed at execution time, after the planning process has completed; (ii) Worlds and scenarios where the state changes dynamically while a previous plan is executing; (iii) Models that are incomplete and can be changed during execution; and (iv) Information about the human agent's plan and intentions that can be used for coordination. These challenges are compounded by the fact that the human-robot team must execute in an open world, rife with dynamic events and other agents; and in a manner that encourages the exchange of information between the human and the robot. As an answer to these challenges, implemented solutions and a fielded prototype that combines all of those solutions into one planning system are discussed. Results from running this prototype in real world scenarios are presented, and extensions to some of the solutions are offered as appropriate.
Automated planning provides the solution to this problem -- indeed, one of the main motivations that underpinned the beginnings of the field of automated planning was to provide planning support for Shakey the robot with the STRIPS system. For long, however, automated planners suffered from scalability issues that precluded their application to real world, real time robotic systems. Recent decades have seen a gradual abeyance of those issues, and fast planning systems are now the norm rather than the exception. However, some of these advances in speedup and scalability have been achieved by ignoring or abstracting out challenges that real world integrated robotic systems must confront.
In this work, the problem of planning for human-hobot teaming is introduced. The central idea -- the use of automated planning systems as mediators in such human-robot teaming scenarios -- and the main challenges inspired from real world scenarios that must be addressed in order to make such planning seamless are presented: (i) Goals which can be specified or changed at execution time, after the planning process has completed; (ii) Worlds and scenarios where the state changes dynamically while a previous plan is executing; (iii) Models that are incomplete and can be changed during execution; and (iv) Information about the human agent's plan and intentions that can be used for coordination. These challenges are compounded by the fact that the human-robot team must execute in an open world, rife with dynamic events and other agents; and in a manner that encourages the exchange of information between the human and the robot. As an answer to these challenges, implemented solutions and a fielded prototype that combines all of those solutions into one planning system are discussed. Results from running this prototype in real world scenarios are presented, and extensions to some of the solutions are offered as appropriate.
ContributorsTalamadupula, Kartik (Author) / Kambhampati, Subbarao (Thesis advisor) / Baral, Chitta (Committee member) / Liu, Huan (Committee member) / Scheutz, Matthias (Committee member) / Smith, David E. (Committee member) / Arizona State University (Publisher)
Created2014
Description
The uncertainty of change inherent in issues such as climate change and regional growth has created a significant challenge for public decision makers trying to decide what adaptation actions are needed to respond to these possible changes. This challenge threatens the resiliency and thus the long term sustainability of our social-ecological systems. Using an empirical embedded case study approach to explore the application of advanced scenario analysis methods to regional growth visioning projects in two regions, this dissertation provides empirical evidence that for issues with high uncertainty, advanced scenario planning (ASP) methods are effective tools for helping decision makers to anticipate and prepare to adapt to change.
ContributorsQuay, Ray (Author) / Pijawka, David (Thesis advisor) / Shangraw, Ralph (Committee member) / Holway, James (Committee member) / Arizona State University (Publisher)
Created2011
Description
The ability to plan, execute, and control goal oriented reaching and grasping movements is among the most essential functions of the brain. Yet, these movements are inherently variable; a result of the noise pervading the neural signals underlying sensorimotor processing. The specific influences and interactions of these noise processes remain unclear. Thus several studies have been performed to elucidate the role and influence of sensorimotor noise on movement variability. The first study focuses on sensory integration and movement planning across the reaching workspace. An experiment was designed to examine the relative contributions of vision and proprioception to movement planning by measuring the rotation of the initial movement direction induced by a perturbation of the visual feedback prior to movement onset. The results suggest that contribution of vision was relatively consistent across the evaluated workspace depths; however, the influence of vision differed between the vertical and later axes indicate that additional factors beyond vision and proprioception influence movement planning of 3-dimensional movements. If the first study investigated the role of noise in sensorimotor integration, the second and third studies investigate relative influence of sensorimotor noise on reaching performance. Specifically, they evaluate how the characteristics of neural processing that underlie movement planning and execution manifest in movement variability during natural reaching. Subjects performed reaching movements with and without visual feedback throughout the movement and the patterns of endpoint variability were compared across movement directions. The results of these studies suggest a primary role of visual feedback noise in shaping patterns of variability and in determining the relative influence of planning and execution related noise sources. The final work considers a computational approach to characterizing how sensorimotor processes interact to shape movement variability. A model of multi-modal feedback control was developed to simulate the interaction of planning and execution noise on reaching variability. The model predictions suggest that anisotropic properties of feedback noise significantly affect the relative influence of planning and execution noise on patterns of reaching variability.
ContributorsApker, Gregory Allen (Author) / Buneo, Christopher A (Thesis advisor) / Helms Tillery, Stephen (Committee member) / Santello, Marco (Committee member) / Santos, Veronica (Committee member) / Si, Jennie (Committee member) / Arizona State University (Publisher)
Created2012
Description
Power generation in remote isolated places is a tough problem. Presently, a common source for remote generation is diesel. However, diesel generation is costly and environmental unfriendly. It is promising to replace the diesel generation with some clean and economical generation sources. The concept of renewable generation offers a solution to remote generation. This thesis focuses on evaluation of renewable generation penetration in the remote isolated grid. A small town named Coober Pedy in South Australia is set as an example. The first task is to build the stochastic models of solar irradiation and wind speed based on the local historical data. With the stochastic models, generation fluctuations and generation planning are further discussed. Fluctuation analysis gives an evaluation of storage unit size and costs. Generation planning aims at finding the relationships between penetration level and costs under constraint of energy sufficiency. The results of this study provide the best penetration level that makes the minimum energy costs. In the case of Coober Pedy, cases of wind and photovoltaic penetrations are studied. The additional renewable sources and suspended diesel generation change the electricity costs. Results show that in remote isolated grid, compared to diesel generation, renewable generation can lower the energy costs.
ContributorsZhu, Yujia (Author) / Holbert, Keith E. (Thesis advisor) / Karady, George G. (Committee member) / Tylavsky, Daniel J (Committee member) / Arizona State University (Publisher)
Created2012
Description
Measuring the success of a transportation project as it is envisioned in the Regional Transportation Plan (RTP) and is detailed in an Environmental Impact Statement (EIS) is not part of any current planning process, for a post construction analysis may have political consequences for the project participants, would incur additional costs, and may be difficult to define in terms of scope. With local, state and federal budgets shrinking, funding sources are demanding that the performance of a project be evaluated and project stakeholders be held accountable. The Transportation Research Board (TRB) developed a framework that allows transportation agencies to customize their reporting so that a project's performance can be measured. In the case of the Red Mountain Freeway, the selected performance measure allows for comparing the population forecasts, the traffic volumes, and the project costs defined in the final EIS to actual population growth, actual average annual daily traffic (ADT), and actual project costs obtained from census data, the City of Mesa, and contractor bids, respectively. The results show that population projections for both Maricopa County and the City of Mesa are within less than half a percent of the actual annual population growth. The traffic analysis proved more difficult due to inconsistencies within the EIS documents, variations in the local arterials used to produce traffic volume, and in the projection time-spans. The comparison for the total increase in traffic volume generated a difference of 11.34 percent and 89.30 percent. An adjusted traffic volume equal to all local arterials and US 60 resulted in a difference of 40 percent between the projected and actual ADT values. As for the project cost comparison, not only were the costs within the individual documents inconsistent, but they were underestimated by as much as 75 percent. Evaluating the goals as described in an EIS document using the performance measure guidelines provided by the TRB may provide the tool that can help promote conflict resolution for political issues that arise, streamline the planning process, and measure the performance of the transportation system, so that lessons learned can be applied to future projects.
ContributorsKizior, Angelika (Author) / Golub, Aaron (Thesis advisor) / Kuby, Michael (Committee member) / Wentz, Elizabeth (Committee member) / Arizona State University (Publisher)
Created2012
Description
This dissertation presents a portable methodology for holistic planning and optimization of right of way infrastructure rehabilitation that was designed to generate monetary savings when compared to planning that only considers single infrastructure components. Holistic right of way infrastructure planning requires simultaneous consideration of the three right of way infrastructure components that are typically owned and operated under the same municipal umbrella: roads, sewer, and water. The traditional paradigm for the planning of right way asset management involves operating in silos where there is little collaboration amongst different utility departments in the planning of maintenance, rehabilitation, and renewal projects. By collaborating across utilities during the planning phase, savings can be achieved when collocated rehabilitation projects from different right of way infrastructure components are synchronized to occur at the same time. These savings are in the form of shared overhead and mobilization costs, and roadway projects providing open space for subsurface utilities. Individual component models and a holistic model that utilize evolutionary algorithms to optimize five year maintenance, rehabilitation, and renewal plans for the road, sewer, and water components were created and compared. The models were designed to be portable so that they could be used with any infrastructure condition rating, deterioration modeling, and criticality assessment systems that might already be in place with a municipality. The models attempt to minimize the overall component score, which is a function of the criticality and condition of the segments within each network, by prescribing asset management activities to different segments within a component network while subject to a constraining budget. The individual models were designed to represent the traditional decision making paradigm and were compared to the holistic model. In testing at three different budget levels, the holistic model outperformed the individual models in the ability to generate five year plans that optimized prescribed maintenance, rehabilitation and renewal for various segments in order to achieve the goal of improving the component score. The methodology also achieved the goal of being portable, in that it is compatible with any condition rating, deterioration, and criticality system.
ContributorsCarey, Brad David (Author) / Lueke, Jason S (Thesis advisor) / Ariaratnam, Samuel (Committee member) / Bashford, Howard (Committee member) / Arizona State University (Publisher)
Created2012
Description
Automated planning problems classically involve finding a sequence of actions that transform an initial state to some state satisfying a conjunctive set of goals with no temporal constraints. But in many real-world problems, the best plan may involve satisfying only a subset of goals or missing defined goal deadlines. For example, this may be required when goals are logically conflicting, or when there are time or cost constraints such that achieving all goals on time may be too expensive. In this case, goals and deadlines must be declared as soft. I call these partial satisfaction planning (PSP) problems. In this work, I focus on particular types of PSP problems, where goals are given a quantitative value based on whether (or when) they are achieved. The objective is to find a plan with the best quality. A first challenge is in finding adequate goal representations that capture common types of goal achievement rewards and costs. One popular representation is to give a single reward on each goal of a planning problem. I further expand on this approach by allowing users to directly introduce utility dependencies, providing for changes of goal achievement reward directly based on the goals a plan achieves. After, I introduce time-dependent goal costs, where a plan incurs penalty if it will achieve a goal past a specified deadline. To solve PSP problems with goal utility dependencies, I look at using state-of-the-art methodologies currently employed for classical planning problems involving heuristic search. In doing so, one faces the challenge of simultaneously determining the best set of goals and plan to achieve them. This is complicated by utility dependencies defined by a user and cost dependencies within the plan. To address this, I introduce a set of heuristics based on combinations using relaxed plans and integer programming formulations. Further, I explore an approach to improve search through learning techniques by using automatically generated state features to find new states from which to search. Finally, the investigation into handling time-dependent goal costs leads us to an improved search technique derived from observations based on solving discretized approximations of cost functions.
ContributorsBenton, J (Author) / Kambhampati, Subbarao (Thesis advisor) / Baral, Chitta (Committee member) / Do, Minh B. (Committee member) / Smith, David E. (Committee member) / Langley, Pat (Committee member) / Arizona State University (Publisher)
Created2012