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

DOI10.1007/s10472-009-9122-0zbMath1185.68654MaRDI QIDQ1022454

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 planning; mobile robots; competitive complexity class

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

93C85: Automated systems (robots, etc.) in control theory

11Y16: Number-theoretic algorithms; complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68T40: Artificial intelligence for robotics

68W15: Distributed algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Searching in the plane
• Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape
• Competitive on-line coverage of grid environments by a mobile robot
• Spanning-tree based coverage of continuous areas by a mobile robot
• COMPETITIVE COMPLEXITY OF MOBILE ROBOT ON-LINE MOTION PLANNING PROBLEMS