Fetching the paper…
Reading the bibliography…
This paper studies the underlying combinatorial structure of a class of object rearrangement problems, which appear frequently in applications.
N. Christofides and S. Eilon, “ An algorithm for the vehicle-dispatching problem ,” Journal of the Operational Research Society , vol. 20, no. 3, pp. 309–318, 1969
1969
Earlier work this paper cites.
R. M. Karp, “ Reducibility among combinatorial problems ,” in Complexity of computer computations . Springer, 1972, pp. 85–103
1972
Earlier work this paper cites.
G. N. Frederickson, M. S. Hecht, and C. E. Kim, “ Approximation algorithms for some routing problems ,” in 17th Annual Symposium on Foundations of Computer Science (sfcs 1976) . IEEE, 1976, pp. 216–227
1976
Earlier work this paper cites.
C. H. Papadimitriou, “ The Euclidean travelling salesman problem is NP-complete ,” Theoretical Computer Science , vol. 4, no. 3, pp. 237–244, 1977
1977
Earlier work this paper cites.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, 1979
1979
Earlier work this paper cites.
D. Kornhauser, G. Miller, and P. Spirakis, “ Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications ,” in Proc. IEEE Symposium on Foundations of Computer Science , 1984, pp. 241–250
1984
Earlier work this paper cites.
G. Wilfong, “ Motion Planning in the Presence of Movable Obstacles ,” in Annals of Mathematics and Artificial Intelligence , 1991, pp. 131–150
1991
Earlier work this paper cites.
P. C. Chen and Y. K. Hwang, “ Practical Path Planning Among Movable Obstacles ,” in Proc. IEEE International Conference on Robotics and Automation , May 1991, pp. 444–449
1991
Earlier work this paper cites.
G. Laporte, “ The vehicle routing problem: An overview of exact and approximate algorithms ,” European Jornal of Operational Research , vol. 59, no. 3, pp. 345–358, 1992
1992
Earlier work this paper cites.
S. Anily and R. Hassin, “ The swapping problem ,” Networks , vol. 22, no. 4, pp. 419–433, 1992
1992
Earlier work this paper cites.
G. N. Frederickson and D. J. Guan, “ Nonpreemptive ensemble motion planning on a tree ,” Journal of Algorithms , vol. 15, no. 1, pp. 29–60, 1993
1993
Earlier work this paper cites.
R. H. Wilson and J.-C. Latombe, “ Geometric Reasoning about Mechanical Assembly ,” Artificial Intelligence , vol. 71, no. 2, pp. 371–396, 1994
1994
Earlier work this paper cites.
O. Ben-Shahar and E. Rivlin, “ Practical Pushing Planning for Rearrangement Tasks ,” IEEE Transactions on Robotics and Automation , vol. 14, no. 4, Aug. 1998
1998
Earlier work this paper cites.
B. Aronov, M. de Berg, A. F. van den Stappen, P. S̆vestka, and J. Vleugels, “ Motion Planning for Multiple Robots ,” Discrete and Computational Geometry , vol. 22, no. 4, pp. 505–525, 1999
1999
Earlier work this paper cites.
S. Leroy, J.-P. Laumond, and T. Siméon, “ Multiple Path Coordination for Mobile Robots: A Geometric Algorithm ,” in Proc. International Joint Conferences on Artificial Intelligence , 1999, pp. 1118–1123
1999
Earlier work this paper cites.
V. Auletta, A. Monti, D. Parente, and G. Persiano, “ A Linear Time Algorithm for the Feasibility of Pebble Motion on Trees ,” Algorthmica , vol. 23, pp. 223–245, 1999
1999
Earlier work this paper cites.
D. Halperin, J.-C. Latombe, and R. H. Wilson, “ A General Framework for Assembly Planning: the Motion Space Approach ,” Algorthmica , vol. 26, no. 3-4, pp. 577–601, 2000
2000
Earlier work this paper cites.
E. Demaine, J. O’Rourke, and M. L. Demaine, “ Pushpush and push-1 are NP-hard in 2D ,” in Proc. Candadian Conference on Computational Geometry , 2000, pp. 211–219
2000
Earlier work this paper cites.
S. Sundaram, I. Remmler, and N. M. Amato, “ Disassembly Sequencing Using a Motion Planning Approach ,” in Proc. IEEE International Conference on Robotics and Automation , Washington, D.C., May 2001, pp. 1475–1480
2001
Earlier work this paper cites.
J. Ota, “ Rearrangement Planning of Multiple Movable Objects ,” in Proc. IEEE International Conference on Robotics and Automation , 2004
2004
Earlier work this paper cites.
P. Beullens, D. van Oudheusden, and L. N. van Wassenhove, “ Collection and vehicle routing issues in reverse logistics ,” in Reverse Logistics . Springer, 2004, pp. 95–134
2004
Earlier work this paper cites.
T. Siméon, J.-P. Laumond, J. Cortés, and A. Sahbani, “ Manipulation Planning with Probabilistic Roadmaps ,” International Journal of Robotics Research , no. 23, 2004
2004
Earlier work this paper cites.
I. Dinur and S. Safra, “ On the hardness of approximating minimum vertex cover ,” Annals of Mathematics , pp. 439–485, 2005
2005
Cited alongside, same era.
J. van den Berg and M. Overmars, “ Prioritized Motion Planning for Multiple Robots ,” in Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems , 2005, pp. 2217–2222
2005
Cited alongside, same era.
D. Nieuwenhuisen, A. F. van der Stappen, and M. H. Overmars, “ An Effective Framework for Path Planning amidst Movable Obstacles ,” in Proc. Workshop on the Algorithmic Foundations of Robotics , 2006
2006
Cited alongside, same era.
A. Hoff and A. Løkketangen, “ Creating lasso-solutions for the traveling salesman problem with pickup and delivery by tabu search ,” Central European Journal of Operations Research , vol. 14, no. 2, pp. 125–140, 2006
2006
Cited alongside, same era.
K. Treleaven, M. Pavone, and E. Frazzoli, “ Asymptotically optimal algorithms for one-to-one pickup and delivery problems with applications to transportation systems ,” IEEE Transactions on Automatic Control , vol. 58, no. 9, pp. 2261–2276, 2013
2013
Later among the works it cites.
J. B. Cohen, S. Chitta, and M. Likhachev, “ Single- and Dual-arm Motion Planning with Heuristic Search ,” in International Journal of Robotics Research , 2013
2013
Later among the works it cites.
M. Zucker, N. Ratliff, A. Dragan, M. Pivtoraiko, M. Klingensmith, C. Dellin, J. A. Bagnell, and S. S. Srinivasa, “ CHOMP: Covariant Hamiltonian Optimization for Motion Planning ,” International Journal of Robotics Research , 2013
2013
Later among the works it cites.
Q. Bonnard, S. Lemaignan, G. Zufferey, A. Mazzei, S. Cuendet, N. Li, A. Özgür, and P. Dillenbourg, “ Chilitags 2: Robust Fiducial Markers for Augmented Reality and Robotics ,” 2013. [Online]. Available: http://chili.epfl.ch/software
2013
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
M. Stilman, J. Schamburek, J. J. Kuffner, and T. Asfour, “ Manipulation Planning Among Movable Obstacles ,” in Proc. IEEE International Conference on Robotics and Automation , 2007
2007
Cited alongside, same era.
G. Berbeglia, J.-F. Cordeau, I. Gribkovskaia, and G. Laporte, “ Static pickup and delivery problems: a classification scheme and survey ,” Top , vol. 15, no. 1, pp. 1–31, 2007
2007
Cited alongside, same era.
I. Gribkovskaia, Ø. Halskau, G. Laporte, and M. Vlček, “ General solutions to the single vehicle routing problem with pickups and deliveries ,” European Journal of Operational Research , vol. 180, no. 2, pp. 568–584, 2007
2007
Cited alongside, same era.
D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook, The Traveling Salesman Problem: A Computational Study . Princeton, NJ, USA: Princeton University Press, 2007
2007
Cited alongside, same era.
G. Calinescu, A. Dumitrescu, and J. Pach, “ Reconfigurations in Graphs and Grids ,” SIAM Journal on Discrete Mathematics , vol. 22, no. 1, pp. 124–138, 2008
2008
Cited alongside, same era.
J. van den Berg, M. Stilman, J. J. Kuffner, M. Lin, and D. Manocha, “ Path Planning Among Movable Obstacles: A Probabilistically Complete Approach ,” in Proc. Workshop on the Algorithmic Foundations of Robotics , 2008
2008
Cited alongside, same era.
J. van den Berg, J. Snoeyink, M. Lin, and D. Manocha, “ Centralized path planning for multiple robots: Optimal decoupling into sequential plans ,” in Proc. Robotics: Science and Systems , 2009
2009
Cited alongside, same era.
M. Ciocarlie and P. Allen, “ Hand Posture Subspaces for Dexterous Robotic Grasping ,” in International Journal of Robotics Research , vol. 28, no. 7, 2009
2009
Cited alongside, same era.
Later among the works it cites.
G. Havur, G. Ozbilgin, E. Erdem, and V. Patoglu, “ Geometric Rearrangement of Multiple Moveable Objects on Cluttered Surfaces: A Hybrid Reasoning Approach ,” in Proc. IEEE International Conference on Robotics and Automation , 2014
2014
Later among the works it cites.
S. Srivastava, E. Fang, L. Riano, R. Chitnis, S. Russell, and P. Abbeel, “ Combined Task and Motion Planning through an Extensible Planner-Independent Interface Layer ,” in Proc. IEEE International Conference on Robotics and Automation , 2014
2014
Later among the works it cites.
C. R. Garrett, T. Lozano-Pérez, and L. P. Kaelbling, “ FFRob: An efficient heuristic for task and motion planning ,” in Proc. Workshop on the Algorithmic Foundations of Robotics , 2014
2014
Later among the works it cites.
A. Krontiris, R. Shome, A. Dobson, A. Kimmel, and K. E. Bekris, “ Rearranging Similar Objects with a Manipulator using Pebble Graphs ,” in Proc. IEEE International Conference on Humanoid Robotics , Madrid, Spain, 2014
2014
Later among the works it cites.
K. Hauser, “ The Minimum Constraint Removal Problem with Three Robotics Applications ,” International Journal of Robotics Research , vol. 33, no. 1, pp. 5–17, 2014
2014
Later among the works it cites.
J. Bohg, A. Morales, T. Asfour, and D. Kragic, “ Data-driven Grasp Synthesis - A Survey ,” in IEEE Transactions on Robotics , vol. 30, no. 2, Apr. 2014
2014
Later among the works it cites.
2015
Later among the works it cites.
K. Solovey and D. Halperin, “ On the hardness of unlabeled multi-robot motion planning ,” in Proc. Robotics: Science and Systems , 2015
2015
Later among the works it cites.
G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “ Conflict-based Search for Optimal Multi-agent Pathfinding ,” in Artificial Intelligence , no. 219, 2015, pp. 40–66
2015
Later among the works it cites.
A. Krontiris and K. E. Bekris, “ Dealing with Difficult Instances of Object Rearrangement ,” in Proc. Robotics: Science and Systems , Rome, Italy, Jul. 2015
2015
Later among the works it cites.
M. Gharbi, R. Lallement, and R. Alami, “ Combining symbolic and geometric planning to synthesize human-aware plans: toward more efficient combined search ,” in Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems , 2015, pp. 6360–6365
2015
Later among the works it cites.
A. Baharev, H. Schichl, and A. Neumaier, “ a n exact method for the minimum feedback arc set problem,” University of Vienna , vol. 10, pp. 35–60, 2015
2015
Later among the works it cites.
——, “ Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics ,” IEEE Transactions on Robotics , vol. 32, no. 5, pp. 1163–1177, 2016
2016
Later among the works it cites.
——, “ Efficiently Solving General Rearrangement Tasks: A Fast Extension Primitive for an Incremental Sampling-based Planner ,” in Proc. IEEE International Conference on Robotics and Automation , Sweden, 2016
2016
Later among the works it cites.
N. T. Dantam, Z. K. Kingston, S. Chaudhuri, and L. E. Kavraki, “ Incremental Task and Motion Planning: A Constraint-Based Approach ,” in Proc. Robotics: Science and Systems , 2016
2016
Later among the works it cites.
W. Vega-Brown and N. Roy, “ Asymptotically optimal planning under piecewise-analytic constraints ,” in Proc. Workshop on the Algorithmic Foundations of Robotics , 2016
2016
Later among the works it cites.
I. Gurobi Optimization, “ Gurobi Optimizer Reference Manual ,” 2016. [Online]. Available: http://www.gurobi.com
2016
Later among the works it cites.
S. D. Han, N. M. Stiffler, A. Krontiris, K. E. Bekris, and J. Yu, “ High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods ,” in Proc. Robotics: Science and Systems , Boston, Massachusetts, U.S.A., Jul. 2017
2017
Closest in time.