Efficient Heuristics for Solving Probabilistic Interval Algebra Networks

A probabilistic interval algebra (PIA) network is an interval algebra network with probabilities associated with the labels on an edge. The probabilities on each edge sum to 1. A solution is a consistent scenario where the product of the probabilities associated with each unique edge label is maximized. In this paper we investigate previous PIA network solution algorithms, and propose new ones. Our first algorithm is based on best first search and guarantees to output the optimal solution. However, this algorithm is only feasible for toy problems. We augment the algorithm with three heuristics. Although our proposed algorithm does not guarantee an optimal solution, it is very useful in practice. Good solutions can be generated quickly

Authors

• Kai Zhang
• André Trudel

Keywords

• Algebra
• Heuristic algorithms
• Testing
• Computer science
• Labeling
• Heuristic
• Interval Algebra
• First Search
• Product Of Probabilities
• Edge Labels
• Running Time
• Highest Probability
• Original Network
• Number Of Scenarios
• Single Label
• Probable Scenario
• Similar Labeling
• Probability In Order
• Greedy Search Algorithm