Classifying the multi robot path finding problem into a quadratic competitive complexity class

DOI10.1007/S10472-009-9122-0MaRDI QIDQ1022454zbMATH OpenOpenAlexFDO

Authors Shahar Sarid, Amir Shapiro

Publication date 22 June 2009

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10472-009-9122-0

zbMATH Keywords

competitive complexity classmobile robotsmotion planning

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Artificial intelligence for robotics (68T40) Distributed algorithms (68W15) Analysis of algorithms (68W40) Automated systems (robots, etc.) in control theory (93C85)

Recommendations

• Competitive complexity of mobile robot on-line motion planning problems
• A competitive analysis of nearest neighbor based algorithms for searching unknown scenes
• A competitive analysis of algorithms for searching unknown scenes
• Models and algorithms for online exploration and search.
• Motion planning for multiple robots

Cites work

• Competitive complexity of mobile robot on-line motion planning problems
• Competitive on-line coverage of grid environments by a mobile robot
• scientific article; zbMATH DE number 1373584 (Why is no real title available?)
• scientific article; zbMATH DE number 2085302 (Why is no real title available?)
• Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape
• Searching in the plane
• Spanning-tree based coverage of continuous areas by a mobile robot

Cited in

(5)

• Multi-goal motion planning using traveling salesman problem in belief space
• Multidimensional online motion planning for a spherical robot
• Competitive disconnection detection in on-line mobile robot navigation
• Competitive complexity of mobile robot on-line motion planning problems
• A competitive analysis of nearest neighbor based algorithms for searching unknown scenes

This page was built for publication: Classifying the multi robot path finding problem into a quadratic competitive complexity class

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1022454)