Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Autonomous Robots
Published in: Autonomous Robots 1-2/2014

01-01-2014

Object search by manipulation

Authors: Mehmet R. Dogar, Michael C. Koval, Abhijeet Tallavajhula, Siddhartha S. Srinivasa

Published in: Autonomous Robots | Issue 1-2/2014

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We investigate the problem of a robot searching for an object. This requires reasoning about both perception and manipulation: some objects are moved because the target may be hidden behind them, while others are moved because they block the manipulator’s access to other objects. We contribute a formulation of the object search by manipulation problem using visibility and accessibility relations between objects. We also propose a greedy algorithm and show that it is optimal under certain conditions. We propose a second algorithm which takes advantage of the structure of the visibility and accessibility relations between objects to quickly generate plans. Our empirical evaluation strongly suggests that our algorithm is optimal under all conditions. We support this claim with a partial proof. Finally, we demonstrate an implementation of both algorithms on a real robot using a real object detection system.
previous article Autonomously learning to visually detect where manipulation will succeed
next article Analyzing dexterous hands using a parallel robots framework

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
We use two-dimensional examples, e.g. Fig. 2, throughout the paper for clarity of illustration. Our actual formulation and implementation uses complete three-dimensional models of the scene, objects, and volumes.
 
2
In the rare event that that multiple sequences share the maximum utility, the algorithm breaks the tie by choosing the sequence with the maximum utility prefix recursively.
 
3
We use \(\Lambda ^\pi \) in place of \(V^\pi \) to denote the value function to avoid confusion with revealed volume \(V_s\).
 
Literature
Anand, A., Koppula, H. S., Joachims, T., & Saxena, A. (2013). Contextually guided semantic labeling and search for three-dimensional point clouds. International Journal of Robotics Research, 32(1), 19–34.CrossRef
Baird, D. (1995). Experimentation: An introduction to measurement theory and experiment design. Englewood Cliffs: Prentice-Hall.
Ben-Shahar, O., & Rivlin, E. (1998). Practical pushing planning for rearrangement tasks. IEEE Transactions on Robotics and Automation, 14, 549–565.CrossRef
Chen, P., & Hwang, Y. (1991). Practical path planning among movable obstacles. IEEE: In IEEE International Conference on Robotics and Automation.
de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008). Computational geometry: Algorithms and applications. Berlin: Springer.
Diankov, R., & Kuffner, J. (2008). OpenRAVE: A planning architecture for autonomous robotics. Technical Report CMU-RI-TR-08-34, Robotics Institute.
Dogar, M., & Srinivasa, S. (2012). A planning framework for non-prehensile manipulation under clutter and uncertainty. Autonomous Robots, 33(3), 217–236.CrossRef
Espinoza, J., Sarmiento, A., Murrieta-Cid, R., & Hutchinson, S. (2011). Motion planning strategy for finding an object with a mobile manipulator in three-dimensional environments. Advanced Robotics, 25, 1627–1650.CrossRef
Gupta, M., & Sukhatme, G. (2012). Interactive perception in clutter. In R. S. S. The (Ed.), 2012. Workshop on Robots in Clutter: Manipulation, Perception and Navigation in Human Environments.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.CrossRef
Hauser, K. (2012). The minimum constraint removal problem with three robotics applications. In Workshop on the Algorithmic Foundations of Robotics (WAFR).
Hopcroft, J., & Tarjan, R. (1973). Algorithm 447: Efficient algorithms for graph manipulation. Communications of the ACM, 16(6), 372–378.CrossRef
Kaelbling, L. P., Littman, M. L., & Moore, A. W. (1996). Reinforcement learning: A survey. Journal of Artificial Intelligence Researc, 4, 237–285.
Kaelbling, L., & Lozano-Perez, T. (2012). Unifying perception, estimation and action for mobile manipulation via belief space planning. IEEE: In IEEE International Conference on Robotics and Automation.
Kollar, T., & Roy, N. (2009). Utilizing object-object and object-scene context when planning to find things. IEEE: In IEEE International Conference on Robotics and Automation.
Ma, J., Chung, T. H., & Burdick, J. (2011). A probabilistic framework for object search with 6-dof pose estimation. International Journal of Robotics Research, 30(10), 1209–1228.CrossRef
Martinez, M., llet, A., & Srinivasa, S. (2010). MOPED: A scalable and low latency object recognition and pose estimation system. In IEEE International Conference on Robotics and Automation. IEEE.
Ota, J. (2009). Rearrangement planning of multiple movable objects by a mobile robot. Advanced Robotics, 23, 1–18.CrossRef
Overmars, M. H., Nieuwenhuisen, D., Nieuwenhuisen, D., Frank, A., & Overmars, H. (2006). An effective framework for path planning amidst movable obstacles. In International Workshop on the Algorithmic Foundations of Robotics.
Shubina, K., & Tsotsos, J. (2010). Visual search for an object in a 3D environment using a mobile robot. Computer Vision and Image Understanding, 114, 535–547.CrossRef
Sjo, K., Lopez, D., Paul, C., Jensfelt, P., & Kragic, D. (2009). Object search and localization for an indoor mobile robot. Journal of Computing and Information Technology, 17, 67–80.
Srinivasa, S., Berenson, D., Cakmak, M., Dogar, M., Dragan, A., Knepper, R. A., et al. (2012). Herb 2.0: Lessons learned from developing a mobile manipulator for the home. Proceedings of the IEEE, 100(8), 1–19.CrossRef
Stilman, M., Schamburek, J. U., Kuffner, J., & Asfour, T. (2007). Manipulation planning among movable obstacles. In IEEE International Conference on Robotics and Automation. IEEE.
van den Berg, J. P., Stilman, M., Kuffner, J., Lin, M. C., & Manocha, D. (2008). Path planning among movable obstacles: A probabilistically complete approach. In International Workshop on the Algorithmic Foundations of Robotics (pp. 599–614).
van Hoof, H., Kroemer, O., Amor, H. B., & Peters, J. (2012). Maximally informative interaction learning for scene exploration. In IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 5152–5158). IEEE.
Wilfong, G. (1988). Motion planning in the presence of movable obstacles. In Proceedings of the Fourth Annual Symposium on Computational Geometry (pp. 279–288).
Wong, L. L., Kaelbling, L. P., & Lozano-Pérez, T. (2013). Manipulation-based active search for occluded objects. In IEEE International Conference on Robotics and Automation. IEEE.
Ye, Y., & Tsotsos, J. (1995). Where to look next in 3D object search. In IEEE International Symposium on Computer Vision. IEEE.
Ye, Y., & Tsotsos, J. (1999). Sensor planning for 3D object search. Computer Vision and Image Understanding, 73(2), 145–168.CrossRef
Metadata
Title
Object search by manipulation
Authors
Mehmet R. Dogar
Michael C. Koval
Abhijeet Tallavajhula
Siddhartha S. Srinivasa
Publication date
01-01-2014
Publisher
Springer US
Published in
Autonomous Robots / Issue 1-2/2014
Print ISSN: 0929-5593
Electronic ISSN: 1573-7527
DOI
https://doi.org/10.1007/s10514-013-9372-x

Other articles of this Issue 1-2/2014

Autonomous Robots 1-2/2014 Go to the issue

OriginalPaper

Autonomously learning to visually detect where manipulation will succeed

OriginalPaper

An autonomous manipulation system based on force control and optimization

OriginalPaper

Learning of grasp selection based on shape-templates

OriginalPaper

Analyzing dexterous hands using a parallel robots framework

OriginalPaper

Design and control of a three-fingered tendon-driven robotic hand with active and passive tendons

OriginalPaper

A compliant self-adaptive gripper with proprioceptive haptic feedback