DocumentCode :
1865693
Title :
Minimum time point assignment for coverage by two constrained robots
Author :
Chakraborty, Nilanjan ; Akella, Srinivas ; Wen, John T.
Author_Institution :
Rensselaer Polytech. Inst., Troy, NY
fYear :
2008
fDate :
19-23 May 2008
Firstpage :
1378
Lastpage :
1383
Abstract :
This paper focuses on the assignment of discrete points to two robots, in the presence of geometric and kinematic constraints between the robots. The individual points have differing processing times, and the goal is to identify an assignment of points to the robots so that the total processing time is minimized. The assignment of points to the robots is the first step in the path generation process for the robots. This work is motivated by an industrial microelectronics manufacturing system with two robots, with square footprints, that are constrained to translate along a common line while satisfying proximity and collision avoidance constraints. The N points lie on a planar base plate that can translate along the plane normal to the direction of motion of the robots. The geometric constraints on the motions of the two robots lead to constraints on points that can be processed simultaneously. We show that the point assignment for processing problem can be converted to a maximum weighted matching problem on a graph and solved optimally in O(N3) time. Since this is too slow for large datasets, we present a O(N2) time greedy algorithm and prove that the greedy solution is within a factor of 3/2 of the optimal solution. Finally, we provide computational results for the greedy algorithm on typical industrial datasets.
Keywords :
geometry; mobile robots; robot kinematics; constrained robots; geometric constraints; greedy algorithm; kinematic constraints; maximum weighted matching problem; minimum time point assignment; path generation process; robots motion; square footprints; Circuit testing; Computer industry; Drilling; Greedy algorithms; Manufacturing industries; Path planning; Robot sensing systems; Robotics and automation; Service robots; USA Councils;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on
Conference_Location :
Pasadena, CA
ISSN :
1050-4729
Print_ISBN :
978-1-4244-1646-2
Electronic_ISBN :
1050-4729
Type :
conf
DOI :
10.1109/ROBOT.2008.4543395
Filename :
4543395
Link To Document :
بازگشت