{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T09:27:01Z","timestamp":1672997221345},"reference-count":57,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[1996,8,1]],"date-time":"1996-08-01T00:00:00Z","timestamp":838857600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[1996,8]]},"abstract":" Industrial assembly involves sensing the pose (orientation and position) of a part. Efficient and reliable sensing strategies can be developed for an assembly task if the shape of the part is known in advance. In this article we investigate two problems of determining the pose of a polygonal part of known shape for the cases of a continuum and a finite number of possible poses, respectively. <\/jats:p> The first problem, named sensing by inscription, involves determining the pose of a convex n-gon from a set of m sup porting cones. An algorithm with running time O( nm) that almost always reduces to O(n + m log n) is presented to solve for all possible poses of the polygon. We prove that the number of possible poses cannot exceed 6n, given m \u2265 2 supporting cones with distinct vertices. Simulation experiments demonstrate that two supporting cones are sufficient to determine the real pose of the n-gon in most cases. Our results imply that sensing in practice can be carried out by obtaining viewing angles of a planar part at multiple exterior sites in the plane. <\/jats:p> On many occasions a parts feeder will have reduced the number of possible poses of a part to a small finite set. Our second problem, named sensing by point sampling, is con cerned with a more general version: finding the minimum number of sensing points required to distinguish between n polygonal shapes with a total of m edges. In practice this can be implemented by embedding a series of point light detectors in a feeder tray or by using a set of mechanical probes that touch the feeder at a finite number of predeter mined points. We show that this problem is equivalent to an NP-complete set-theoretic problem introduced as Discriminat ing Set, and present an O( n2<\/jats:sup>m2<\/jats:sup>) approximation algorithm to solve it with a ratio of 2 In n. Furthermore, we prove that one can use an algorithm for Discriminating Set with ratio c log n to construct an algorithm for Set Covering with ratio c log n + O(log log n). Thus the ratio 2 In n is asymptotically optimal unless NP \u2282 DTIME( npoly log<\/jats:sup> n<\/jats:sup>), a consequence of known results on approximating Set Covering. The complexity of subproblems of Discriminating Set is also analyzed, based on their relationship to a generalization of Independent Set called 3-Independent Set. Finally, simulation results suggest <\/jats:p>","DOI":"10.1177\/027836499601500405","type":"journal-article","created":{"date-parts":[[2007,3,5]],"date-time":"2007-03-05T01:24:06Z","timestamp":1173057846000},"page":"365-392","source":"Crossref","is-referenced-by-count":13,"title":["Geometric Sensing of Known Planar Shapes"],"prefix":"10.1177","volume":"15","author":[{"given":"Yan-Bin","family":"Jia","sequence":"first","affiliation":[{"name":"Robotics Institute and School of Computer Science Carnegie Mellon University Pittsburgh, Pennsylvania 15213-3891"}]},{"given":"Michael","family":"Erdmann","sequence":"additional","affiliation":[{"name":"Robotics Institute and School of Computer Science Carnegie Mellon University Pittsburgh, Pennsylvania 15213-3891"}]}],"member":"179","published-online":{"date-parts":[[2016,7,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/34.75509"},{"key":"atypb2","volume-title":"Proceedings of the Ninth Annual Symposium on Computational Geometry","author":"Arkin, E.M."},{"key":"atypb3","volume-title":"Proceedings of the Fifth Canadian Conference on Computational Geometry","author":"Arkin, E.M."},{"key":"atypb4","volume-title":"Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science","author":"Arora, S."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0035856"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90017-9"},{"key":"atypb7","volume-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing","author":"Bellare, M."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90022-X"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758849"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1177\/027836498800700101"},{"key":"atypb11","volume-title":"A \"RISC\" paradigm for industrial robotics","author":"Canny, J.F.","year":"1993"},{"key":"atypb12","unstructured":"Chazelle, B. 1983. The polygon containment problem. In Preparata, F. P. (ed.), Advances in Computing Research. Greenwich, CT: Jai Press Inc., pp. 1-32."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/147508.147511"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/34.87340"},{"issue":"3","key":"atypb15","first-page":"233","volume":"4","author":"Chv\u00e1tal, V.","year":"1979","journal-title":"Operations Res."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90025-3"},{"key":"atypb17","volume-title":"Introduction to Algorithms","author":"Cormen, T.H.","year":"1990"},{"key":"atypb18","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing","author":"Dobkin, D."},{"key":"atypb19","volume-title":"Towards a theory of information invariants for cooperating autonomous mobile robots","author":"Donald, B.R.","year":"1993"},{"key":"atypb20","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing","author":"Edelsbrunner, H."},{"key":"atypb21","volume-title":"Understanding action and sensing by designing action-based sensors","author":"Erdmann, M.","year":"1993"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/56.800"},{"key":"atypb23","unstructured":"Fortune, S. 1985. Fast algorithms for polygon containment. In Brauer, W. (ed.), Automata, Languages and Programming, New York: Springer-Verlag , pp. 189-198."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"atypb25","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey, M.R.","year":"1979"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1984.4767518"},{"key":"atypb27","volume-title":"Proceedings of the 1990 IEEE International Conference on Robotics and Automation","author":"Goldberg, K.Y."},{"key":"atypb28","volume-title":"Proceedings of the 1994 IEEE Int. Conference on Robot. and Automation","author":"Govindan, R."},{"key":"atypb29","volume-title":"Concrete Mathematics: A Foundation for Computer Science","author":"Graham, R.L.","year":"1989"},{"key":"atypb30","volume-title":"Object Recognition by Computer: the Role of Geometric Constraints","author":"Grimson, W.E.L.","year":"1990"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1975.5408381"},{"key":"atypb32","volume-title":"Proceedings of the 1994 IEEE International Conference on Robotics and Automation","author":"Jia, Y.-B."},{"key":"atypb33","volume-title":"Proceedings of the First Workshop on the Algorithmic Foundations of Robotics","author":"Jia, Y.-B."},{"issue":"3","key":"atypb34","first-page":"256","volume":"9","author":"Johnson, D.S.","year":"1974","journal-title":"Sci."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90037-7"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"atypb37","author":"Kemmotsu, K.","year":"1993","journal-title":"Science"},{"key":"atypb38","volume-title":"Proceedings of the Twentieth Annual Symposium on Foundations of Computer Science","author":"Kirkpatrick, D.G."},{"key":"atypb39","volume-title":"Proceedings of the 6th Conference on Structure in Complexity Theory","author":"Kolaitis, P.G."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90196-2"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90022-5"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1109\/34.6772"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"atypb44","volume-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing","author":"Lund, C."},{"key":"atypb45","unstructured":"Mumford. D. 1987. The problem of robust shape descriptors. Proceedings of the First International Conference on Computer Vision, London, pp. 602-606."},{"key":"atypb46","volume-title":"Proceedings of the 3rd Annual Symposium on Computational Geometry","author":"Natarajan, B.K."},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1145\/358656.358681"},{"key":"atypb48","volume-title":"Computational Geometry: An Introduction","author":"Preparata, F.P.","year":"1988"},{"key":"atypb49","volume-title":"Proceedings of the 1993 IEEE International Conference on Robotics and Automation","author":"Rao, A.S."},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1177\/027836499401300102"},{"key":"atypb51","volume-title":"Approximate testing theory","author":"Romanik, K.","year":"1992"},{"key":"atypb52","volume-title":"Proceedings of the Fourth Canadian Conference on Computational Geometry","author":"Romanik, K."},{"key":"atypb53","volume-title":"Proceedings of the 1991 IEEE International Conference on Robotics and Automation","author":"Siegel, D.M."},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1985.4767731"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553911"},{"key":"atypb56","volume-title":"Proceedings of the 1993 IEEE International Conference on Robotics and Automation","author":"Wallack, A.S."},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187890"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499601500405","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499601500405","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,25]],"date-time":"2021-03-25T11:09:15Z","timestamp":1616670555000},"score":1,"resource":{"primary":{"URL":"http:\/\/journals.sagepub.com\/doi\/10.1177\/027836499601500405"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,8]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,8]]}},"alternative-id":["10.1177\/027836499601500405"],"URL":"http:\/\/dx.doi.org\/10.1177\/027836499601500405","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":["Applied Mathematics","Artificial Intelligence","Electrical and Electronic Engineering","Mechanical Engineering","Modeling and Simulation","Software"],"published":{"date-parts":[[1996,8]]}}}