Improving a Plan Library for Real-time Systems Using Nearly Orthogonal Latin Hypercube Sampling

Robert HolderAAAI 2008

Abstract

In complex, real-time environments, computing plans from scratch is often computationally prohibitive. Plan libraries—collections of precomputed solutions—provide a viable alternative, yet their effectiveness depends heavily on how the high-dimensional parameter space of environmental conditions is sampled. This paper explores Nearly Orthogonal Latin Hypercube Sampling (NOLHS) as a method to create representative plan libraries that minimize coverage gaps while remaining scalable for high-dimensional systems.

Introduction

Real-time systems, such as autonomous sensor networks or disaster response units, must operate within strict temporal constraints. When environmental conditions change, the system must either generate a new plan or adapt an existing one. Because full plan generation is often too slow, systems rely on plan libraries. However, the space of possible scenarios is vast and high-dimensional. A poorly sampled library may leave the system in a state far from any stored plan, making real-time adaptation impossible. The core challenge lies in selecting a small, representative subset of plans that provides maximum coverage.

Sampling Methodologies

To address the coverage problem, several sampling techniques are evaluated for their ability to fill the parameter space effectively:

  • Random Sampling: While simple, it often results in clusters and large unsampled regions.
  • Latin Hypercube Sampling (LHS): Ensures that each individual parameter's range is evenly represented across its dimensions. However, it can still leave multi-dimensional "holes."
  • Orthogonal Latin Hypercube Sampling (OLHS): An extension of LHS that improves space-filling by reducing correlations between dimensions, though it becomes computationally expensive as dimensionality increases.
  • Nearly Orthogonal Latin Hypercube Sampling (NOLHS): The proposed core method. It relaxes the strict constraints of OLHS to maintain scalability in high-dimensional spaces while providing better coverage than standard LHS.
  • Exponential Sampling: Concentrates plans in regions where adaptation is known to be difficult or "brittle."
Comparison of various sampling techniques including random, exponential, LHS, and orthogonal LHS.

Application and Evaluation

The effectiveness of these sampling strategies is tested within the Flexible Adversarial Multi-agent Environment (FAME). This domain involves a map of 49 regions with approximately 600 broadcast stations and 50 mobile sensors. The system's goal is to satisfy real-time requests and manage sensor failures. Evaluation is based on the percentage of total and high-priority requests successfully met, focusing on how the "distance" between the current state and the nearest library plan affects adaptation success.

Discussion

The creation of a plan library is fundamentally an experimental design problem. The "gap" problem—the distance in parameter space between a real-time situation and the nearest precomputed plan—determines the cost of adaptation. In high-dimensional spaces, standard sampling methods fail to provide adequate coverage without becoming prohibitively large.

NOLHS offers a "Goldilocks" solution, balancing computational efficiency with robust space-filling. Furthermore, strategic density—placing more plans in difficult subregions—may be necessary for optimal performance. As systems become more complex, adding variables like sensor failure rates and timing, NOLHS becomes a vital tool for handling these expanding parameter spaces.

Conclusion

NOLHS represents a promising framework for building effective plan libraries in complex real-time systems. By providing a scalable way to sample high-dimensional parameter spaces, it ensures that systems have access to plans that are either ready for use or easily adaptable. Future work will focus on identifying the most relevant environmental variables for sampling and exploring hybrid approaches that combine NOLHS with targeted high-density sampling in critical regions.

Summary updated

BibTeX
@inproceedings{holder2008improving,
  author = {Robert Holder},
  title = {{Improving a Plan Library for Real-time Systems Using Nearly Orthogonal Latin Hypercube Sampling}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure