Adaptive Sampling for Multi-RobotWide Area ProspectingKian Hsiang Low Geoffrey J. Gordon John M. DolanPradeep KhoslaOctober 2005CMU-RI-TR-05-51October 2005Robotics InstituteCarnegie Mellon UniversityPittsburgh, Pennsylvania 15213c Carnegie Mellon UniversityAbstractProspecting for in situ mineral resources is essential for establishing settlements onthe Moon and Mars. To reduce human effort and risk, it is desirable to build roboticsystems to perform this prospecting. An important issue in designing such systems isthe sampling strategy: how do the robots choose where to prospect next? This paper ar-gues that a strategy called Adaptive Cluster Sampling (ACS) has a number of desirableproperties: compared to conventional strategies, (1) it reduces the total mission timeand energy consumption of a team of robots, and (2) returns a higher mineral yieldand more information about the prospected region by directing exploration towards ar-eas of high mineral density, thus providing detailed maps of the boundaries of suchareas. Due to the adaptive nature of the sampling scheme, it is not immediately obvi-ous how the resulting sampled data can be used to provide an unbiased, low-varianceestimate of the regional mineral density. This paper therefore investigates new min-eral density estimators, which have lower error than previously-developed estimators;they are derived from the older estimators via a process called Rao-Blackwellization.Since the efficiency of estimators depends on the type of mineralogical population sam-pled, the population characteristics that favor ACS estimators are also analyzed. TheACS scheme and our new estimators are evaluated empirically in a detailed simulationof the prospecting task, and the quantitative results show that our approach can yieldmore minerals with less resources and provide more accurate mineral density estimatesthan previous methods.IContents1 Introduction 12 Robot Supervision Architecture 23 Adaptive Cluster Sampling 34 Unbiased ACS Estimators 44.1 Modified Horvitz-Thompson Estimator . . . . . . . . . . . . . . . . 44.2 Modified Hansen-Hurwitz Estimator . . . . . . . . . . . . . . . . . . 75 Improved Unbiased Rao-Blackwellized ACS Estimators 75.1 Rao-Blackwellized HT Estimator . . . . . . . . . . . . . . . . . . . . 95.2 Rao-Blackwellized HH Estimator . . . . . . . . . . . . . . . . . . . 116 Efficiency Analysis of ACS Estimators 137 Experiments and Discussion 148 Conclusion and Future Work 17A Proof of Theorem 1 18B Proof of Corollary 1 19C Derivation: var[ˆµHT| D] 19D Significance levels from t-tests on similarity inRMSEs between estimators 21III1 IntroductionThe establishment of large, self-sufficient lunar and Martian settlements will require anextensive use of in situ mineral resources. Prospecting for these resources is thereforecrucial to planning these settlements [19] (e.g., site selection, processing equipment,and manufactured products). Although orbiting spacecraft can remotely survey the lu-nar surface for the distribution of minerals, their sensing data are limited in resolutionand the types of minerals/elements sensed [13]. Hence, surface prospecting is neces-sary to determine the specific regions of highest abundance (in particular, geographi-cally rare minerals and minerals not sensed by orbiters) for mining and to extract themost geologically interesting samples for detailed analysis and calibration of orbiters’data [12].Surface prospecting can be conducted by either robots or spacesuited humans. Thebenefits of robot prospectors include a wider range of sensory capabilities for mineralidentification, elimination of safety and life support issues, operation in harsh environ-ments, and greater strength and endurance [6, 18]. Their deployment may increase theefficiency of sampling in large prospecting regions and relieve the humans for moresophisticated tasks such as real-time perception and planning, and detailed geologicfield study.Traditionally, conventional sampling methods such as Raster Scanning (RS) [1],Simple Random Sampling (SRS) [14], and stratified random sampling [1] have beenused in prospecting with robots. The first approach acquires measurements at uniformintervals, thus incurring high sampling and travel costs to achieve adequate samplingdensity. The second approach selects a random sample of locations and makes mea-surements at each of the selected locations. However, it ignores the fact that mineraldeposits are usually clustered [3, 20] and sometimes rare [19]. This results in an impre-cise estimate of the mineral density in the prospecting region (i.e., large variance) [17].Stratified random sampling requires prior knowledge of the mineral distribution for al-locating the appropriate sampling effort among strata [17]. Without such information,its efficiency degrades to that of SRS. There is one other conventional sampling schemecalled Systematic Sampling (SS) [20], which has not been utilized in robot prospecting.It will be used as a method of comparison in our paper.This paper presents adaptive sampling techniques for wide area prospecting witha team of robots (Fig. 1). Assume that the prospecting region (Fig. 2a) is discretizedinto a grid of N sampling units. Adaptive sampling refers to sampling strategies inwhich the procedure for selecting units to be included in the sample depends on themineral concentration observed during prospecting. In contrast, conventional samplinghas no such dependence. The main objective of adaptive sampling is to exploit the pop-ulation characteristics of mineral deposits (e.g., spatial clustering or patchiness shownin Fig. 2b) to obtain more precise estimates of the regional density than conventionalstrategies for a given sample size or cost.This paper describes a specific adaptive sampling scheme known as ACS (Sec-tion 3), which has a number of desirable benefits for multi-robot wide area prospecting:(1) it returns a higher mineral yield and more information about the prospected regionby directing robot exploration towards areas of high mineral density, thus providingdetailed maps of the boundaries of such areas, and (2) it reduces the total mission time1Figure 1: Multi-robot mineral prospecting task.and energy consumption of the robot team (Section 7).The adaptive nature of this scheme incurs a considerable bias in conventional es-timators due to a large proportion of high mineral content data in the sample. Conse-quently, two unbiased estimators are proposed in [20] for