Robot Packing with Known Items and Nondeterministic Arrival Order

Fan Wang, Kris Hauser

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper formulates two variants of packing problems in which the set of items is known but the arrival order is unknown. The goal is to certify that the items can be packed in a given container, and/or to optimize the size or cost of a container so that that the items are guaranteed to be packable, regardless of arrival order. The Nondeterministically ordered packing (NDOP) variant asks to generate a certificate that a packing plan exists for every ordering of items. Quasi-online packing (QOP) asks to generate a partially-observable packing policy that chooses the item location as each subsequent item is revealed. Theoretical analysis demonstrates that even the simple subproblem of verifying feasibility of a packing policy is NP-complete. Despite this worst-case complexity, practical solvers for both NDOP and QOP are developed, and experiments demonstrate their application to packing irregular 3D shapes with manipulator loading constraints.

Original languageEnglish (US)
Title of host publicationRobotics
Subtitle of host publicationScience and Systems XV
EditorsAntonio Bicchi, Hadas Kress-Gazit, Seth Hutchinson
PublisherMIT Press Journals
ISBN (Print)9780992374754
StatePublished - 2019
Externally publishedYes
Event15th Robotics: Science and Systems, RSS 2019 - Freiburg im Breisgau, Germany
Duration: Jun 22 2019Jun 26 2019

Publication series

NameRobotics: Science and Systems
ISSN (Electronic)2330-765X


Conference15th Robotics: Science and Systems, RSS 2019
CityFreiburg im Breisgau

ASJC Scopus subject areas

  • Artificial Intelligence
  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Robot Packing with Known Items and Nondeterministic Arrival Order'. Together they form a unique fingerprint.

Cite this