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

DOI10.1007/s10472-009-9122-0zbMath1185.68654OpenAlexW2088502025MaRDI 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 planningmobile robotscompetitive complexity class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Automated systems (robots, etc.) in control theory (93C85) Number-theoretic algorithms; complexity (11Y16) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) 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)

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

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