Predicting the Performance of Distributed Knowledge-Based Systems: A Modeling Approach

Jasmina PavlinAAAI 1983

Introduction

In the early 1980s, designing and tuning Distributed Knowledge-Based Systems (DKBS), such as the HEARSAY-II speech understanding system, was often considered more of an art than a science. These systems are characterized by asynchronous processing, the handling of uncertain or incomplete data, and the dynamic creation of tasks. Traditional control theory and static modeling approaches frequently fail to capture the complex temporal interactions and data quality shifts inherent in such distributed environments. This paper proposes a modeling framework based on augmented Petri nets to predict DKBS performance, enabling system optimization prior to full-scale implementation.

Methodology: Augmented Petri Nets

The core of the proposed approach is an extension of Petri nets, a mathematical language for describing distributed systems. Standard Petri nets typically use simple tokens to represent state; however, to model DKBS, the author "augments" these tokens to carry three critical attributes:

  1. Volume ($V$): Representing the amount of work or number of hypotheses.
  2. Accuracy ($A$): Representing the belief or certainty associated with the data.
  3. Time ($T$): Representing the arrival time of the data.

Activities within the system are modeled as transitions. Each transition is associated with three functions ($f_v, f_a, f_t$) that calculate the output token's attributes based on its inputs. This allows the model to simulate the "focus of attention" problem—deciding which tasks to prioritize—by implementing execution rules that reflect AI scheduling policies. Performance is quantitatively evaluated using an objective function $J = \text{Accuracy} / \text{Elapsed Time}$.

Evaluation and Validation

The model was validated using the Distributed Vehicle Monitoring Testbed (DVMT), a simulation environment where distributed nodes track vehicles using acoustic signals. The study tested six different communication configurations (labeled a through f), which varied the level of abstraction at which information was shared between nodes (e.g., raw signals vs. high-level patterns).

Key Results

The primary goal of the model was not necessarily absolute numerical precision, but rather the ability to correctly predict the relative performance of different system configurations.

Figure 7: Solution accuracy comparison between the model and the testbed across configurations a-f.

As shown in Figure 7, the model's predictions for solution accuracy closely track the actual results obtained from the DVMT testbed. Both the model and the testbed show a significant increase in accuracy starting from configuration c.

Figure 8: Solution time comparison between the model and the testbed across configurations a-f.

Similarly, Figure 8 demonstrates that the model accurately captures the trends in solution time. Configuration f, which involves communicating information at a high level of abstraction, was identified by both the model and the testbed as the most efficient configuration, balancing high accuracy with low solution time.

Conclusion

The augmented Petri net approach provides a robust tool for DKBS designers. By focusing on the interactions between components and using volume as a proxy for processing effort, the model can predict the relative merits of various communication policies. While determining the specific transition functions remains a challenge, the model's ability to mirror testbed results suggests it could eventually serve as a real-time component for self-optimizing distributed AI systems.

Summary updated

BibTeX
@inproceedings{pavlin1983predicting,
  author = {Jasmina Pavlin},
  title = {{Predicting the Performance of Distributed Knowledge-Based Systems: A Modeling Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}

Loading related content...

Figure