Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Bayesian A* tree search with expected O(N) node expansions: applications to road tracking.

James M Coughlan1, A L Yuille

  • 1Smith-Kettlewell Eye Research Institute, San Francisco, CA 94115, USA. coughlan@ski.org

Neural Computation
|August 16, 2002
PubMed
Summary

Bayesian inference provides a framework for complex problems. Analyzing algorithms using this framework reveals linear convergence for road detection, despite exponential worst-case complexity.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

NavGraph: Enhancing Blind Travelers' Navigation Experience and Safety.

Proceedings of the ACM on interactive, mobile, wearable and ubiquitous technologies·2025
Same author

Enhancing Walk-Light Detector Usage for the Visually Impaired: A Comparison of VR Exploration and Verbal Instructions.

... International web for all conference. Web for All Conference·2025
Same author

MapIO: A Gestural and Conversational Interface for Tactile Maps.

IEEE access : practical innovations, open solutions·2025
Same author

Systematically Evaluating Digital Map Tools Based on the WCAG.

Journal on technology and persons with disabilities : ... Annual International Technology and Persons with Disabilities Conference·2025
Same author

Designing Born-Accessible Courses in Data Science and Visualization: Challenges and Opportunities of a Remote Curriculum Taught by Blind Instructors to Blind Students.

Eurographics/IEEE VGTC Symposium on Visualization : EUROVIS : [proceedings]. Eurographics/IEEE VGTC Symposium on Visualization·2025
Same author

Accessible Point-and-Tap Interaction for Acquiring Detailed Information about Tactile Graphics and 3D Models.

Computers helping people with special needs : ... International Conference, ICCHP ... : proceedings. International Conference on Computers Helping People with Special Needs·2024

Area of Science:

  • Computer Science
  • Artificial Intelligence
  • Probability Theory

Background:

  • Many complex problems in perception, reasoning, and learning can be framed as Bayesian inference.
  • Formulating problems within Bayesian inference requires defining a probability distribution over problem instances.

Purpose of the Study:

  • To analyze the expected complexity of algorithms and algorithm-independent inference limits.
  • To illustrate these concepts by examining the complexity of tree search algorithms.
  • To specifically study the road detection problem as defined by Geman and Jedynak (1996).

Main Methods:

  • Bayesian inference formulation
  • Probability distribution specification on problem instances
  • Tree search complexity analysis

Related Experiment Videos

  • Road detection problem analysis

    • Main Results:

    • Expected convergence for road detection is proven to be linear with respect to road size (tree depth).
    • Worst-case performance for road detection is shown to be exponential.
    • Bounds are established for the convergence constant and error rates.

    Conclusions:

    • Bayesian inference offers a powerful lens for analyzing algorithmic complexity and inference limits.
    • The study demonstrates efficient expected performance for road detection algorithms within a Bayesian framework.
    • The findings provide theoretical guarantees on convergence and error rates for this specific problem.