NDLI: Minimum time point assignment for coverage by two constrained robots

Content Provider	IEEE Xplore Digital Library
Author	Chakraborty, N. Akella, S. Wen, J.T.
Copyright Year	2008
Description	Author affiliation: Rensselaer Polytech. Inst., Troy, NY (Chakraborty, N.; Akella, S.; Wen, J.T.)
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(N^{3})$ time. Since this is too slow for large datasets, we present a $O(N^{2})$ 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.
Starting Page	1378
Ending Page	1383
File Size	197159
Page Count	6
File Format	PDF
ISBN	9781424416462
ISSN	10504729
DOI	10.1109/ROBOT.2008.4543395
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-05-19
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Service robots Greedy algorithms Drilling Robotics and automation Manufacturing industries Computer industry Robot sensing systems Circuit testing Path planning USA Councils
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Control and Systems Engineering Electrical and Electronic Engineering Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in