More Like this

1. Anytime Integrated Task and Motion Policies for Stochastic Environments

   https://doi.org/10.1109/ICRA40945.2020.9197574  

   Shah, Naman; Kala Vasudevan, Deepak; Kumar, Kislay; Kamojjhala, Pranav; Srivastava, Siddharth (May 2020, IEEE International Conference on Robotics and Automation)

   null (Ed.)

   In order to solve complex, long-horizon tasks, intelligent robots need to carry out high-level, abstract planning and reasoning in conjunction with motion planning. However, abstract models are typically lossy and plans or policies computed using them can be unexecutable. These problems are exacerbated in stochastic situations where the robot needs to reason about, and plan for multiple contingencies. We present a new approach for integrated task and motion planning in stochastic settings. In contrast to prior work in this direction, we show that our approach can effectively compute integrated task and motion policies whose branching structures encoding agent behaviors handling multiple execution-time contingencies. We prove that our algorithm is probabilistically complete and can compute feasible solution policies in an anytime fashion so that the probability of encountering an unresolved contingency decreases over time. Empirical results on a set of challenging problems show the utility and scope of our methods. 

   more » « less
2. Termination analysis without the tears

   https://doi.org/10.1145/3453483.3454110  

   Zhu, Shaowei; Kincaid, Zachary (June 2021, Programming Language Design and Implementation)

   Determining whether a given program terminates is the quintessential undecidable problem. Algorithms for termination analysis may be classified into two groups: (1) algorithms with strong behavioral guarantees that work in limited circumstances (e.g., complete synthesis of linear ranking functions for polyhedral loops), and (2) algorithms that are widely applicable, but have weak behavioral guarantees (e.g., Terminator). This paper investigates the space in between: how can we design practical termination analyzers with useful behavioral guarantees? This paper presents a termination analysis that is both compositional (the result of analyzing a composite program is a function of the analysis results of its components) and monotone (“more information into the analysis yields more information out”). The paper has two key contributions. The first is an extension of Tarjan’s method for solving path problems in graphs to solve infinite path problems. This provides a foundation upon which to build compositional termination analyses. The second is a collection of monotone conditional termination analyses based on this framework. We demonstrate that our tool ComPACT (Compositional and Predictable Analysis for Conditional Termination) is competitive with state-of-the-art termination tools while providing stronger behavioral guarantees. 

   more » « less
3. Research-Focused Approach for Introducing Undergraduate Students to Aromatic Organic Synthesis at a Community College

   https://doi.org/10.1021/acs.jchemed.2c00662  

   Boette, Jessica T.; Daniel, Kira M.; Lietzke, Josephine W.; Amorde, Shawn M.; Roberts, Sean T. (February 2023, Journal of Chemical Education)

   The addition of research-focused experiences to undergraduate chemistry laboratory courses has been shown to bolster student learning, enhance student retention in STEM, and improve student self-identity as scientists. In the area of synthetic organic chemistry, the preparation of libraries of compounds with novel optical and electronic properties can provide a natural motivational goal for research-focused exercises that can be undertaken by individual students or collectively as a class. However, integrating such experiences into a community college teaching laboratory setting can face challenges imposed by the cost of supplies, limited laboratory space, and access to characterization facilities. To address these challenges, we have devised a sequence of inquiry-driven, research-focused laboratory exercises that can be readily integrated into an organic chemistry laboratory course with minimal cost. This sequence consists of a multistep synthesis of perylenediimide dyes that introduces students to advanced synthetic techniques, such as organometallic coupling reactions, column purification, and reactions performed under inert atmosphere. This high-yield, three-part synthesis can be easily varied by individual students or small groups within a class to form a broad library of compounds with potential utility for applications in light harvesting, molecular electronics, catalysis, and medicine. We describe the design of low-cost workstations for chemical synthesis under inert atmosphere and provide auxiliary lesson plans that can be used to expand the scope of a laboratory course beyond synthetic organic chemistry by introducing students to concepts in molecular spectroscopy. 

   more » « less
4. A Logic-Based Explanation Generation Framework for Classical and Hybrid Planning Problems

   https://doi.org/10.1613/jair.1.13431  

   Vasileiou, Stylianos Loukas; Yeoh, William; Cao Son, Tran; Kumar, Ashwin; Cashmore, Michael; Magazzeni, Dianele (January 2022, Journal of Artificial Intelligence Research)

   In human-aware planning systems, a planning agent might need to explain its plan to a human user when that plan appears to be non-feasible or sub-optimal. A popular approach, called model reconciliation, has been proposed as a way to bring the model of the human user closer to the agent’s model. To do so, the agent provides an explanation that can be used to update the model of human such that the agent’s plan is feasible or optimal to the human user. Existing approaches to solve this problem have been based on automated planning methods and have been limited to classical planning problems only. In this paper, we approach the model reconciliation problem from a different perspective, that of knowledge representation and reasoning, and demonstrate that our approach can be applied not only to classical planning problems but also hybrid systems planning problems with durative actions and events/processes. In particular, we propose a logic-based framework for explanation generation, where given a knowledge base KBa (of an agent) and a knowledge base KBh (of a human user), each encoding their knowledge of a planning problem, and that KBa entails a query q (e.g., that a proposed plan of the agent is valid), the goal is to identify an explanation ε ⊆ KBa such that when it is used to update KBh, then the updated KBh also entails q. More specifically, we make the following contributions in this paper: (1) We formally define the notion of logic-based explanations in the context of model reconciliation problems; (2) We introduce a number of cost functions that can be used to reflect preferences between explanations; (3) We present algorithms to compute explanations for both classical planning and hybrid systems planning problems; and (4) We empirically evaluate their performance on such problems. Our empirical results demonstrate that, on classical planning problems, our approach is faster than the state of the art when the explanations are long or when the size of the knowledge base is small (e.g., the plans to be explained are short). They also demonstrate that our approach is efficient for hybrid systems planning problems. Finally, we evaluate the real-world efficacy of explanations generated by our algorithms through a controlled human user study, where we develop a proof-of-concept visualization system and use it as a medium for explanation communication. 

   more » « less
5. Co-Optimization of Design and Fabrication Plans for Carpentry

   https://doi.org/10.1145/3508499  

   Zhao, Haisen; Willsey, Max; Zhu, Amy; Nandi, Chandrakana; Tatlock, Zachary; Solomon, Justin; Schulz, Adriana (June 2022, ACM Transactions on Graphics)

   Past work on optimizing fabrication plans given a carpentry design can provide Pareto-optimal plans trading off between material waste, fabrication time, precision, and other considerations. However, when developing fabrication plans, experts rarely restrict to a single design , instead considering families of design variations , sometimes adjusting designs to simplify fabrication. Jointly exploring the design and fabrication plan spaces for each design is intractable using current techniques. We present a new approach to jointly optimize design and fabrication plans for carpentered objects. To make this bi-level optimization tractable, we adapt recent work from program synthesis based on equality graphs (e-graphs), which encode sets of equivalent programs. Our insight is that subproblems within our bi-level problem share significant substructures. By representing both designs and fabrication plans in a new bag of parts (BOP) e-graph, we amortize the cost of optimizing design components shared among multiple candidates. Even using BOP e-graphs, the optimization space grows quickly in practice. Hence, we also show how a feedback-guided search strategy dubbed Iterative Contraction and Expansion on E-graphs (ICEE) can keep the size of the e-graph manageable and direct the search towards promising candidates. We illustrate the advantages of our pipeline through examples from the carpentry domain. 

   more » « less