Search

The recent decadal survey report for planetary science (compiled by the National Research Council) has prioritized three main areas for planetary exploration: (1) the characterization of the early Solar system history, (2) the search for planetary habitats, and (3) an improved understanding about the nature of planetary processes. A growing number of ground and space observations suggest that small bodies are ideally suited for addressing all these three priorities. In parallel, several technological advances have been recently made for microgravity rovers, penetrators, and MEMS-based instruments. Motivated by these findings and new technologies, the objective of this paper is to study the expected science return of spatially-extended in-situ exploration at small bodies, as a function of surface covered and in the context of the key science priorities identified by the decadal survey report. Specifically, targets within the scope of our analysis belong to three main classes: main belt asteroids and irregular satellites, Near Earth Objects, and comets. For each class of targets, we identify the corresponding science objectives for potential future exploration, we discuss the types of measurements and instruments that would be required, and we discuss mission architectures (with an emphasis on spatially-extended in-situ exploration) to achieve such objectives. Then, we characterize (notionally) how the science return for two reference targets would scale with the amount (and type) of surface that is expected to be covered by a robotic mobile platform. The conclusion is that spatially-extended in-situ information about the chemical and physical heterogeneity of small bodies has the potential to lead to a much improved understanding about their origin, evolution, and astrobiological relevance. [ABSTRACT FROM PUBLISHER]

One of the most common combinatorial problems in logistics and transportation—after the Traveling Salesman Problem—is the Stacker Crane Problem (SCP), where commodities or customers are associated each with a pickup location and a delivery location, and the objective is to find a minimum-length tour ‘picking up’ and ‘delivering’ all items, while ensuring the number of items on-board never exceeds a given capacity. While vastly many SCPs encountered in practice are embedded in road or road-like networks, very few studies explicitly consider such environments. In this paper, first, we formulate an environment model capturing the essential features of a “small-neighborhood” road network, along with models for omni-directional vehicles and directed vehicles. Then, we formulate a stochastic version of the unit-capacity SCP, on our road network model, where pickup/delivery sites are random points along segments of the network. Our main contribution is a polynomial-time algorithm for the problem that is asymptotically constant-factor; i.e., it produces a solution no worse than k+o(1) times the length of the optimal one, where o(1) goes to zero as the number of items grows large, almost surely. The constant k is at most 3, and for omni-directional vehicles it is provably 1, i.e., optimal. Simulations show that with a number of pickup/delivery pairs as low as 50, the proposed algorithm delivers a solution whose cost is consistently within 10% of that of an optimal solution. [ABSTRACT FROM PUBLISHER]

This paper presents a novel risk-constrained multi-stage decision making approach to the architectural analysis of planetary rover missions. In particular, focusing on a 2018 Mars rover concept, which was considered as part of a potential Mars Sample Return campaign, we model the entry, descent, and landing (EDL) phase and the rover traverse phase as four sequential decision-making stages. The problem is to find a sequence of divert and driving maneuvers so that the rover drive is minimized and the probability of a mission failure (e.g., due to a failed landing) is below a user-specified bound. By solving this problem for several different values of the model parameters (e.g., divert authority), this approach enables rigorous, accurate and systematic trade-offs for the EDL system vs. the mobility system, and, more in general, cross-domain trade-offs for the different phases of a space mission. The overall optimization problem can be seen as a chance-constrained dynamic programming problem, with the additional complexity that 1) in some stages the disturbances do not have any probabilistic characterization, and 2) the state space is extremely large (i.e, hundreds of millions of states for trade-offs with high-resolution Martian maps). To this purpose, we solve the problem by performing an unconventional combination of average and minimax cost analysis and by leveraging high efficient computation tools from the image processing community. Preliminary trade-off results are presented. [ABSTRACT FROM PUBLISHER]

Demand-responsive transport (DRT) systems, where users generate requests for transportation from a pickup point to a delivery point, are expected to increase in usage dramatically as the inconvenience of privately-owned cars in metropolitan areas becomes excessive. However, despite the increasing role of DRT systems, there are very few rigorous results characterizing achievable performance (in terms, e.g., of stability conditions). In this paper, our aim is to bridge this gap for a rather general model of DRT systems, which takes the form of a generalized Dynamic Pickup and Delivery Problem. The key strategy is to develop analytical bounds for the optimal cost of the Euclidean Stacker Crane Problem (ESCP), which represents a general static model for DRT systems. By leveraging such bounds, we characterize a necessary and sufficient condition for the stability of DRT systems; the condition depends only on the workspace geometry, the stochastic distributions of pickup and delivery points, customers' arrival rate, and the number of vehicles. Our results exhibit some surprising features that are absent in traditional spatially-distributed queueing systems. [ABSTRACT FROM PUBLISHER]

Pickup and delivery problems (PDPs), in which objects or people have to be transported between specific locations, are among the most common combinatorial problems in real-world operations. One particular PDP is the Stacker Crane problem (SCP), where each commodity/customer is associated with a pickup location and a delivery location, and the objective is to find a minimum-length tour visiting all locations with the constraint that each pickup location and its associated delivery location are visited in consecutive order. The SCP is a route optimization problem behind several transportation systems, e.g., Transportation-On-Demand (TOD) systems. The SCP is NP-Hard and the best know approximation algorithm only provides a 9/5 approximation ratio. We present an algorithm for the stochastic SCP which: (i) is asymptotically optimal, i.e., it produces a solution approaching the optimal one as the number of pickups/deliveries goes to infinity; and (ii) has computational complexity O(n2+ε), where n is the number of pickup/delivery pairs and ε is an arbitrarily small positive constant. Our results leverage a novel connection between the Euclidean Bipartite Matching Problem and the theory of random permutations. [ABSTRACT FROM PUBLISHER]