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

motion planningmobile robotscompetitive complexity class

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1373584 (Why is no real title available?)
• scientific article; zbMATH DE number 2085302 (Why is no real title available?)
• Competitive complexity of mobile robot on-line motion planning problems
• Competitive on-line coverage of grid environments by a mobile robot
• 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
• Competitive disconnection detection in on-line mobile robot navigation
• Competitive complexity of mobile robot on-line motion planning problems
• Multidimensional online motion planning for a spherical robot
• 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)