I'm wondering what the correct term for an algorithm that is probabilistically complete is. An algorithm is probabilistically complete if the probability of finding a solution, should a solution exist, approaches one as the runtime goes to infinity.

A motion planner such as PRM will eventually find a solution if one exists, but cannot show that that no motion exists. This would be similar to an algorithm that semi-decides a problem, but the "yes" output is a trajectory, so it's not really a decision problem. Is there an accepted term for such algorithms? (Something like, PRM is semi-deciding)?

  • $\begingroup$ This is somewhat similar to a Las Vegas algorithm, without the asymmetry between the true and false instances. $\endgroup$ – Yuval Filmus May 17 '18 at 17:58
  • $\begingroup$ Are you sure your algorithm is probabilistic? This term has a specific meaning in mathematics and computer science, which is different than its normal meaning. $\endgroup$ – Yuval Filmus May 17 '18 at 17:59
  • $\begingroup$ I know the term probabilistic completeness is the standard for the field (en.wikipedia.org/wiki/Motion_planning). I'm not sure what the specific meaning you're referring to is. $\endgroup$ – Andrew W May 17 '18 at 18:16
  • $\begingroup$ It seems that probabilistic completeness is indeed very similar to being a Las Vegas algorithm. I imagine that in motion planning the goal is to produce a plan, so if the term probabilistic complete is used there, it probably refers to what you are looking for. Different terms are used elsewhere. $\endgroup$ – Yuval Filmus May 17 '18 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.