The three a priori intuitions are related — infinite and undirected space, infinite and directed time, finite and undirected probability. Physics knows of uncertainty principle, we are uncertain about relation of time and space: both time and space cannot be intuited with certainty. Probability is as basic and fundamental as time and space for our cognition.

Just like geometry deals with a priori intuition of space, and mathematical analysis — with intuition of time, theory of probability deals with intuition of probability. There is philosophical justification for studying uncertainty, probability, and bayesian inference.

We introduce an approximate search algorithm for fast maximum a posteriori probability estimation in probabilistic programs, which we call Bayesian ascent Monte Carlo (BaMC). Probabilistic programs represent probabilistic models with varying number of mutually dependent finite, countable, and continuous random variables. BaMC is an anytime MAP search algorithm applicable to any combination of random variables and dependencies. We compare BaMC to other MAP estimation algorithms and show that BaMC is faster and more robust on a range of probabilistic models.

Abstract

We introduce a new approach to solving path-finding problems under uncertainty by representing them as probabilistic models and applying domain-independent inference algorithms to the models. This approach separates problem representation from the inference algorithm and provides a framework for efficient learning of path-finding policies. We evaluate the new approach on the Canadian Traveller Problem, which we formulate as a probabilistic model, and show how probabilistic inference allows efficient stochastic policies to be obtained for this problem.

We suggest a justification for the use of a fixed threshold on the number of conflicts based on the analysis of a model problem. Following the suggested justification, we introduce a new algorithm, which differs in the ways when and how meta-agents are created and handled during search. The new algorithm exhibits considerably better performance compared to the original algorithm. The new algorithm is evaluated on several sets of problems, chosen to highlight different aspects of the algorithm.

Full PDF

This is a short version of Justifying and Improving MA-CBS.

Most objective functions assume that the probability distributions have short tails, and few probabilistic models provide accurate representations of long tails: Newton’s laws of mechanics assume that an object does not move too fast, and most objects comply with the assumption.

Occasionally long tails matter. Negative consequences of a highly improbable event outweigh benefits of good behaviour in an average case. A model in which very rare events are neglected leads to designs optimized towards wrong goals; but discovering and analyzing a model which takes care of rare but harmful disasters properly isn’t easy.

Since long tails are difficult to handle, they should be avoided. Chances of rare bad luck grow with the complexity of design: an iron hammer with a wooden handle is slow in application, but almost nothing can inpair its ability of hitting nails. On the other hand, an electronically controlled high power nail gun is very efficient, but a failure in the electronic circuit renders the tool useless.

Speed, resource consumption, ergonomics are important most of the time; but simplicity is the only reliable mean to achieve robustness — the promise that a tool or a system remains usable when things go wrong.