The challenging timeline for DARPA’s Orbital Express mission demanded a flexible, responsive, and (above all) safe approach to mission planning. Mission planning for space is challenging because of the mixture of goals and constraints. Every space mission tries to squeeze all of the capacity possible out of the spacecraft. For Orbital Express, this means performing as many experiments as possible, while still keeping the spacecraft safe. Keeping the spacecraft safe can be very challenging because we need to maintain the correct thermal environment (or batteries might freeze), we need to avoid pointing cameras and sensitive sensors at the sun, we need to keep the spacecraft batteries charged, and we need to keep the two spacecraft from colliding... made more difficult as only one of the spacecraft had thrusters. Because the mission was a technology demonstration, pertinent planning information was learned during actual mission execution. For example, we didn’t know for certain how long it would take to transfer propellant from one spacecraft to the other, although this was a primary mission goal. The only way to find out was to perform the task and monitor how long it actually took. This information led to amendments to procedures, which led to changes in the mission plan. In general, we used the ASPEN planner scheduler to generate and validate the mission plans. ASPEN is a planning system that allows us to enter all of the spacecraft constraints, the resources, the communications windows, and our objectives. ASPEN then could automatically plan our day. We enhanced ASPEN to enable it to reason about uncertainty. We also developed a model generator that would read the text of a procedure and translate it into an ASPEN model. Note that a model is the input to ASPEN that describes constraints, resources, and activities. These technologies had a significant impact on the success of the Orbital Express mission. Finally, we formulated a technique for converting procedural information to declarative information by transforming procedures into models of hierarchical task networks (HTNs). The impact of this effort on the mission was a significant reduction in (1) the execution time of the mission, (2) the daily staff required to produce plans, and (3) planning errors. Not a single miss-configured command was sent during operations.

This article describes the DSN scheduling wngine (DSE) component of a new scheduling system being deployed for NASA's deep space network. The DSE provides core automation functionality for scheduling the network, including the interpretation of scheduling requirements expressed by users, their elaboration into tracking passes, and the resolution of conflicts and constraint violations. The DSE incorporates both systematic search and repair-based algorithms, used for different phases and purposes in the overall system. It has been integrated with a web application which provides DSE functionality to all DSN users through a standard web browser, as part of a peer-to-peer schedule negotiation process for the entire network. The system has been deployed operationally and is in routine use, and is in the process of being extended to support long-range planning and forecasting, and near-real-time scheduling.

We are pleased to introduce the space application issue articles in this issue of AI Magazine. The exploration of space is a testament to human curiosity and the desire to understand the universe that we inhabit. As many space agencies around the world design and deploy missions, it is apparent that there is a need for intelligent, exploring systems that can make decisions on their own in remote, potentially hostile environments. At the same time, the monetary cost of operating missions, combined with the growing complexity of the instruments and vehicles being deployed, make it apparent that substantial improvements can be made by the judicious use of automation in mission operations.

Bayes-adaptive planning offers a principled solution to the explorationexploitation trade-offunder model uncertainty. It finds the optimal policy in belief space, which explicitly accounts for the expected effect on future rewards of reductions in uncertainty. However, the Bayes-adaptive solution is typically intractable indomains with large or continuous state spaces. We present a tractable method for approximating the Bayes-adaptive solution by combining simulationbased searchwith a novel value function approximation technique that generalises appropriately over belief space. Our method outperforms prior approaches in both discrete bandit tasks and simple continuous navigation and control tasks.

Symbolic search using binary decision diagrams (BDDs) can often save large amounts of memory due to its concise representation of state sets. A decisive factor for this method's success is the chosen variable ordering. Generally speaking, it is plausible that dependent variables should be brought close together in order to reduce BDD sizes. In planning, variable dependencies are typically captured by means of causal graphs, and in preceding work these were taken as the basis for finding BDD variable orderings. Starting from the observation that the two concepts of "dependency" are actually quite different, we introduce a framework for assessing the strength of variable ordering heuristics in sub-classes of planning. It turns out that, even for extremely simple planning tasks, causal graph based variable orders may be exponentially worse than optimal. Experimental results on a wide range of variable ordering variants corroborate our theoretical findings. Furthermore, we show that dynamic reordering is much more effective at reducing BDD size, but it is not cost-effective due to a prohibitive runtime overhead. We exhibit the potential of middle-ground techniques, running dynamic reordering until simple stopping criteria hold.

Knowledge Discovery in Databases is a complex process that involves many different data processing and learning operators. Today's Knowledge Discovery Support Systems can contain several hundred operators. A major challenge is to assist the user in designing workflows which are not only valid but also -- ideally -- optimize some performance measure associated with the user goal. In this paper we present such a system. The system relies on a meta-mining module which analyses past data mining experiments and extracts meta-mining models which associate dataset characteristics with workflow descriptors in view of workflow performance optimization. The meta-mining model is used within a data mining workflow planner, to guide the planner during the workflow planning. We learn the meta-mining models using a similarity learning approach, and extract the workflow descriptors by mining the workflows for generalized relational patterns accounting also for domain knowledge provided by a data mining ontology. We evaluate the quality of the data mining workflows that the system produces on a collection of real world datasets coming from biology and show that it produces workflows that are significantly better than alternative methods that can only do workflow selection and not planning.

Low-level motion planning techniques must be combined with high-level task planning formalisms in order to generate realistic plans that can be carried out by humans and robots. Previous attempts to integrate these two planning formalisms mostly used either Classical Planning or HTN Planning. Recently, we developed Hierarchical Goal Networks (HGNs), a new hierarchical planning formalism that combines the advantages of HTN and Classical planning, while mitigating some of the disadvantages of each individual formalism. In this paper, we describe our ongoing research on designing a planning formalism and algorithm that exploits the unique features of HGNs to better integrate task and motion planning. We also describe how the proposed planning framework can be instantiated to solve assembly planning problems involving human-robot teams.

We present an algorithm providing a heuristic solution to the NP-hard optimization problem known as the watchman route problem (WRP) within a 3D virtual environment testbed populated by simulated unmanned vehicles (UVs). The contribution made by our algorithm is three-fold. First, we utilize photon mapping as our means of representing the information sensed by a UV. Second, we use the photon map to generate an online solution to the closely-related NP-hard art gallery problem (AGP). Third, we use a 3D Chan-Vese segmentation algorithm initialized by our AGP-solver to produce a candidate set of path-planning waypoints. The use of photon mapping with our online AGP solver allows us to adapt UV operation to accommodate variable, less-than-ideal environmental circumstances. The use of our 3D Chan-Vese segmentation algorithm creates a set of candidate waypoints that yield greater visibility coverage when computing the WRP than would be obtainable otherwise. Our algorithm provides for quick learning among the unmanned vehicles operating within the testbed’s virtual environment by generating easily-transferrable WRP-solving waypoints.

AI and robotics researchers aim at having robots in our environments coexisting with humans, as artificial creatures that will help humans and collaborate with humans to improve our societies. There will be more than one robot. Robots will not interact with some humans just once, or a few times, but many times. Humans will interact with robots to change their requests and to teach and correct their behaviors. This abstract briefly discusses a few issues for AI and HRI for such challenging repeated interactions in space and time between robots and humans. We have made different levels of research progress on these issues, as we discuss. Our presentation is motivated by our work with the CoBot mobile service robots, which have been running in our environments for the last three years, and for more than 500kms.

We study the scheduling of human-robot teams where the human and robotic agents share decision-making authority over scheduling decisions. Our goal is to design AI scheduling techniques that account for how people make decisions under different control schema.