Steven M. LaValle - US grants

The project focuses on general purpose trajectory design algorithms for high dimensional, highly nonlinear systems evolving in complex environments. The goal is to solve the currently intractable problem of trajectory generation and optimization for high-fidelity models of various types of autonomous vehicles, using an approach that combines methods from differential geometry, nonlinear control theory, robot motion planning, randomized algorithms, and mathematical programming.

Frazzoli - Branicky Abstract

This project is aimed at the development of new tools and techniques for the design and analysis of high-confidence software for complex, distributed, reconfigurable aerospace embedded systems, and to transfer these methods to undergraduate and graduate students, other researchers, and industry.
Problems of direct interest include those arising in the control and coordination of multiple autonomous air and space vehicles, and in the detection and resolution of conflicts in Air Traffic Control. The techniques developed in this project are also applicable to other systems which require similar levels of reliability and performance, such as highway traffic automation systems, health care systems, power networks, and
financial services.

The primary goal of this project is a better understanding of the interactions between real-time software and dynamical systems. This will lead to new and powerful tools and techniques for the design and analysis of embedded systems, as well as an improved approach to the requirement specification for real-time systems.
The core of the research is aimed at dramatically reducing the complexity of embedded and hybrid systems design and verification by exploiting the geometric structure of the underlying physical system in the modelling effort, and by preserving this structure in the design of control laws and algorithms. This will make feasible the analysis of the complete system (including its physical and software components) by otherwise poorly scalable techniques such as abstract interpretation and model checking, and will provide
the means for the effective use of techniques based on compositional reasoning. For example, group symmetries in vehicle dynamics give rise to families of equivalent controlled trajectories: such sets are called motion primitives for single vehicles, and motion coordination primitives for groups of vehicles. A maneuver automaton is a collection of a finite number of motion primitives. It provides a discrete model of the vehicle dynamics, which leads to a dramatic reduction of the complexity of describing and controlling the vehicle behavior, by providing a high level of abstraction, and at the same time providing invariants which ensure that the physical state remains within some known bounds.

The educational part of the project is implemented through new course and curriculum development, and student mentoring. The main educational objective is to provide both undergraduate and graduate students with the knowledge and the skills to understand the key issues and to ensure technical leadership in the current and future aerospace information technology arenas. Finally, an interactive web site is being developed, where it is possible to access information and software developed in the research project and for the courses.

Efficient reasoning about three-dimensional visibility is a challenging problem in many research areas and applications, including computer graphics (radiosity, virtual reality walkthroughs), robotics (sensor-based navigation, visual surveillance), computer vision (recognition, model building), architecture, urban planning, and visualization in computational biology. Visibility issues have been considered for four decades in these areas however, most early work has focused on computing visibility from a single viewpoint, while modern techniques require more global visibility information. Global visibility describes the visibility relationships etween objects that are more complex than points: visibility from a volumetric region of space, limits of umbra and penumbra with respect to an extended light source, mutual visibility etween pairs of objects, and loci of structural changes of visibility.

Although great strides have een made in understanding visibility through the introduction of visibility space partitions and the visibility complex, they have so far had little impact on applications. This is due to several reasons: 1) worst-case theoretical complexity bounds are discouraging 2) there are many degenerate cases that must be handled, making it difficult to make robust implementations 3) equivalences in visibility lead to a four-dimensional cell decomposition, which is difficult to visualize 4) cells can be extremely complicated (some include holes).

This work will make 3D visibility computations practical by approaching the problem in two parallel, integrated tracks. One involves the investigation of several key issues that will make 3D visibility algorithms more attractive and practical in applications: 1) performing practical complexity analysis that captures the expected performance for models that are typically used in applications, as opposed to theoretical worst-case ounds derived from uncommon pathological cases 2) rather than taking a generic "precompute and return everything" approach, we would like the amount of precomputation, information stored in data structures, and extraction algorithms to be nicely tailored to the number of queries and the type of information arises in a particular application 3) traversal through the space of visibility rays will be facilitated through the development of decomposition algorithms based on critical events and Morse theory 4) we will develop techniques for reasoning about the evolving shadow space (set of points not visible), which is required for many problems that involve moving viewpoints.

The second track involves the development of a 3D visibility library ased on robust visibility primitives. We expect to make an immediate impact on applications by making this library available for free to other researchers. The library will serve both as a helpful visualization and evaluation tool during the development of the research, and as a way to stimulate other interest and applications of 3D visibility after the work is completed. This effort, combined with the understanding gained from investigating the key visibility issues, is expected to make a broad impact on a wide array of applications that depend on efficient processing of visibility information.

This proposal describes an aggressive program of research in computational topology with a focus on computing and characterizing shortest paths in a variety of domains relevant to applications in robotics, coordination, and locomotion. We will investigate efficient descriptions of shortest-path information and geodesic structures in spaces with different types of constraints. The three main goals of our project are (1) developing algorithms to compute optimal paths, cycles, and other one-dimensional substructures, primarily in two-dimensional surfaces; (2) applying tools from Alexandrov geometry and topology to more efficiently characterize and compute shortest paths in non-positively curved spaces; and (3) developing languages to characterize spaces of optimal paths for motion systems with mechanical and/or nonholonomic constraints. Our proposed work draws on techniques from low-dimensional geometric and algebraic topology, combinatorial group theory, computational geometry, and non-holonomic motion planning.

At a high level, our research focuses on techniques for computing the cheapest way to move from one point to another in a variety of interesting spaces. Consider, for example, a collection of robots moving around a factory floor. The positions of the robots can be encoded as a single point in a high-dimensional configuration space. The geometry of this space is governed by certain mechanical and/or kinematic constraints; for example, robots must never collide with each other, and they have a limited rate of acceleration. A shortest path in the configuration space describes a set of motions of the robots from one set of locations to another that is as efficient as possible. We plan to develop algorithms that compute such shortest paths quickly, by exploiting the overall ``shape" of the underlying space.

The field of motion planning has recently enjoyed numerous successes both in terms of understanding the critical issues and in applications throughout robotics and related fields. Its algorithms have found use in disparate areas such as humanoid robotics, automotive manufacturing, spacecraft navigation, architecture, computational geography, computer graphics, and computational biology. This project expands the basic motion-planning problem to include critical concerns that are not covered by the motion
Planning algorithms that are in widespread use. The work considers a combination of feedback, differential constraints, and resolution completeness, along with the traditional obstacle-avoidance concerns of motion planning. Long-term, broad impact is expected from this work by leveraging off of the successes of existing motion planning algorithms in applications. Educational impact will also arise through the training of doctoral students, the development of graduate-level courses, the involvement of undergraduates in research, and attempts to recruit women and minorities.

"This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5)."

This project addresses fundamental and challenging questions that are common to robotic systems that build their own maps and solve monitoring tasks. In particular, the work contributes to our general understanding of the interplay between sensing, control, and computation as people attempt to design systems that minimize costs and maximize robustness.

Powerful new abstractions, planning algorithms, and control laws that accomplish basic mapping and monitoring operations are being developed in this effort. This is expected to lead to improved technologies in numerous settings where mapping and monotoring are basic components.
Ample motivation is provided by technological challenges that involve searching, tracking, and monitoring the behavior of people, wildlife, and robots. Examples include search-and-rescue, security sweeps, mapping abandoned mines, scientific study of endangered species, assisted living, ground-based military operations, and even analysis of shopping habits.

The work is particularly transformative because it lives outside of the traditional boundaries of algorithms, computational geometry, sensor networks, control theory, and robotics. Furthermore, national interest continues to grow in the direction of developing distributed robotic systems that combine sensing, actuation, and computation. By helping to break down traditional academic and scientific barriers, it is expected that the work will transform the way we think about robotics algorithms, the engineering design process, and the education of students across the robotics, computational geometry, and control disciplines.

Using the newly introduced idea of a sensor lattice, this project conducts a systematic study of the ``granularity'' at which the world can be sensed and how that affects the ability to accomplish common tasks with cyberphysical systems (CPSs). A sensor is viewed as a device that partitions the physical world states into measurement-invariant equivalence classes, and the sensor lattice indicates how all sensors are related. Several distinctive characteristics of the pursued approach are: 1) Virtual sensor models are developed, which correspond to minimal information requirements of common tasks and are independent of particular physical sensor implementations. 2) Uncertainty is decoupled into disturbances and preimages, the latter of which yields the measurement-invariant equivalence classes and sensor lattice. 3) The development of particular spatial and temporal filters that are based on minimal information requirements of a task. 4) Formally establishing the conditions that enable sensors in a CPS to be interchanged, and then determining the relative complexity tradeoffs.

The intellectual merit is to understand how mappings from the physical world to sensor outputs affect the solvability and complexity of commonly occurring tasks. This is a critical step in the development of mathematical and computational CPS foundations. Broader impact is expected by improving design methodologies for CPS solutions to societal problems such as assisted living, environmental monitoring, and automated agriculture. The sensor lattice approach is transformative because it represents a new paradigm with which to address basic sensor-based inference issues, which extend well beyond the traditional academic boundaries.

Motivated by the complementary abilities of humans and humanoids, the objective of this proposal is to develop the science and technology necessary for realizing human-robot cooperative object manipulation and transportation. The key concepts that this research seeks to promote are adaptability to human activity under minimal communication, and robustness to variability and uncertainty in the environment, achieved through a layered representation and deliberate processing of the available information. Moreover, this project aims to make maximum use of a minimal set of sensors to plan and control the actions of the robot, while ensuring safe and efficient cooperative transportation. The embodiment of this research is a humanoid co-worker that bears most of the load, when helping a person to carry an object, without requiring excessive communication, or prior training on the part of the human.

By introducing concrete methods for human-robot physical collaboration in semi-structured environments, this project enables a unique synergy between robots and humans that has the potential to increase productivity, and reduce accidents and injuries. In doing so, it also promotes the advancement of new practical applications of robots in construction, manufacturing, logistics, and home services. By developing open-source, portable algorithms for humanoid robots and mobile manipulators, this effort results in cost and time savings for researchers, developers, educators, and end-users in robotics. Finally, through an aggressive educational and community outreach plan, and by actively engaging K-12 students in an exciting RoboTech Fellows program, this project seeks to increase diversity and attract underrepresented groups to STEM.

This project will develop an immersive, interactive, room-scale virtual reality (VR) archaeological site that will achieve two overarching classroom objectives: (1) teach the physical methods of archaeological excavation by providing the setting and tools for a student to actively engage in field work; and (2) teach archaeological concepts using a scientific approach to problem solving by couching them within a scientist's context. While the specific problem domain is archaeology, this research will provide learning methodology and technology that is widely applicable to other disciplines and subject areas, resulting in the widespread development of VR curricula that promote scientific thinking and problem-solving skills. Archaeology has an inherent physical component and deals largely with three-dimensional objects, making it challenging to present in a traditional classroom or on traditional computer screens, tablets, or smartphones. Having excavation experience is critical, but field opportunities are available to few students for financial and logistical reasons. These challenges are well met by the unique capabilities of virtual reality (VR), computer technology that creates a simulated three-dimensional world, thereby transforming data analysis into a sensory and cognitive experience. The technological results of the research will provide a learning experience that can engage underserved populations who are interested in archaeology and who have previously been unable to participate in similar activities.

This research will provide empirical foundations for immersive, VR-based learning, an approach that is well-suited to various educational settings and scientific subjects, identifying specific features that are associated with student motivation and positive learning outcomes. Using evaluations and iterative refinement of the virtual environment and activities, this research aims to (1) optimize the interaction of the learner with the VR technology; and (2) evaluate learning outcomes to gauge the effectiveness of VR learning within this specific test case. This exploratory project will leverage the ongoing revolution in consumer electronics as a low-cost platform for social science education, beginning with a prototype for a virtual archaeological excavation, that will be broadly applicable across disciplines and subject areas. At the same time, research will assess the efficacy of this technology and its integration into a larger archaeology curriculum. Given the widespread interest in archaeology and cultural heritage, the results of this research are adaptable and applicable to learners of all ages in formal and informal educational settings like museums, science centers, and cultural heritage sites.