We address the bin packing problem (BPP), which aims to maximize bin utilization when packing a variety of items. The offline problem, where the complete information about the item set and their sizes is known in advance, is proven to be NP-hard. The semi-online and online variants are even more challenging, as full information about incoming items is unavailable. While existing methods have tackled both 2D and 3D BPPs, the 2D BPP remains underexplored in terms of fully maximizing utilization. We propose a hierarchical approach for solving the 2D online and semi-online BPP by combining deep reinforcement learning (RL) with heuristic search. The heuristic search selects which item to pack or unpack, determines the packing order, and chooses the orientation of each item, while the RL agent decides the precise position within the bin. Our method is capable of handling diverse scenarios, including repacking, varying levels of item information, differing numbers of accessible items, and coordination of dual manipulators. Experimental results demonstrate that our approach achieves near-optimal utilization across various practical scenarios, largely due to its repacking capability. In addition, the algorithm is evaluated in a physics-based simulation environment, where execution time is measured to assess its real-world performance.

We address the motion planning problem for multiple robotic manipulators in packed environments where shared workspace can result in goal positions occupied or blocked by other robots unless those other robots move away to make the goal positions free. While planning in a coupled configuration space (C-space) is straightforward, it struggles to scale with the number of robots and often fails to find solutions. Decoupled planning is faster but frequently leads to conflicts between trajectories. We propose a conflict resolution approach that inserts pauses into individually planned trajectories using an$A^{*}$search strategy to minimize the makespan–the total time until all robots complete their tasks. This method allows some robots to stop, enabling others to move without collisions, and maintains short distances in the C-space. It also effectively handles cases where goal positions are initially blocked by other robots. Experimental results show that our method successfully solves challenging instances where baseline methods fail to find feasible solutions.

We tackle the challenges of decentralized multi-robot navigation in environments with nonconvex obstacles, where complete environmental knowledge is unavailable. While reactive methods like Artificial Potential Field (APF) offer simplicity and efficiency, they suffer from local minima, causing robots to become trapped due to their lack of global environmental awareness. Other existing solutions either rely on inter-robot communication, are limited to single-robot scenarios, or struggle to overcome nonconvex obstacles effectively. Our proposed methods enable collision-free navigation using only local sensor and state information without a map. By incorporating a wall-following (WF) behavior into the APF approach, our method allows robots to escape local minima, even in the presence of nonconvex and dynamic obstacles including other robots. We introduce two algorithms for switching between APF and WF: a rule-based system and an encoder network trained on expert demonstrations. Experimental results show that our approach achieves substantially higher success rates compared to state-of-the-art methods, highlighting its ability to overcome the limitations of local minima in complex environments.

We propose a hybrid approach for decentralized multi-robot navigation that ensures both safety and deadlock prevention. Building on a standard control formulation, we add a lightweight deadlock prevention mechanism by forming temporary "roundabouts" (circular reference paths). Each robot relies only on local, peer-to-peer communication and a controller for base collision avoidance; a roundabout is generated or joined on demand to avert deadlocks. Robots in the roundabout travel in one direction until an escape condition is met, allowing them to return to goal-oriented motion. Unlike classical decentralized methods that lack explicit deadlock resolution, our roundabout maneuver ensures system-wide forward progress while preserving safety constraints. Extensive simulations and physical robot experiments show that our method consistently outperforms or matches the success and arrival rates of other decentralized control approaches, particularly in cluttered or high-density scenarios, all with minimal centralized coordination.

In this article, we propose a new measure that evaluates the semantic errors of camera poses in visual odometry (VO) and visual simultaneous localization and mapping (VSLAM). Traditionally, VO/VSLAM methods have used photometric images to estimate camera poses, but they suffer from varying illumination and viewpoint changes. Thus, methods using semantic images have been an alternative to increase consistency, as semantic information has shown its robustness even in hostile environments. Our measure compares semantic classes of map point reprojection pairs between images to improve the camera pose estimation accuracy in VO/VSLAM. To evaluate the difference between semantic classes, we adopt the normalized information distance from information theory. Furthermore, we suggest a weight parameter to balance the existing error of VO/VSLAM with the semantic error introduced by our approach. Our experimental results, obtained from the VKITTI and KITTI benchmark datasets, show that the proposed semantic error measure reduces both the relative pose error and absolute trajectory error of camera pose estimation compared to the existing photometric image-based errors of indirect and direct VO/VSLAM.

We present a coordination method for multiple mobile manipulators to sort objects in clutter. We consider the object rearrangement problem in which the objects must be sorted into different groups in a particular order. In clutter, the order constraints could not be easily satisfied since some objects occlude other objects so the occluded ones are not directly accessible to the robots. Those objects occluding others need to be moved more than once to make the occluded objects accessible. Such rearrangement problems fall into the class of nonmonotone rearrangement problems which are computation-ally intractable. While the nonmonotone problems with order constraints are harder, involving with multiple robots requires another computation for task allocation. In this work, we aim to develop a fast method, albeit sub-optimally, for the multi-robot coordination for ordered sorting in clutter. The proposed method finds a sequence of objects to be sorted using a search such that the order constraint in each group is satisfied. The search can solve nonmonotone instances that require temporal relocation of some objects to access the next object to be sorted. Once a complete sorting sequence is found, the objects in the sequence are assigned to multiple mobile manipulators using a greedy task allocation method. We develop four versions of the method with different search strategies. In the experiments, we show that our method can find a sorting sequence quickly (e.g., 4.6 sec with 20 objects sorted into five groups) even though the solved instances include hard nonmonotone ones. The extensive tests and the experiments in simulation show the ability of the method to solve the real-world sorting problem using multiple mobile manipulators.

We consider the problem of retrieving a target object from a confined space by two robotic manipulators where overhand grasps are not allowed. If other movable obstacles occlude the target, more than one object should be relocated to clear the path to reach the target object. With two robots, the relocation could be done efficiently by simultaneously performing relocation tasks. However, the precedence constraint between the tasks (e.g, some objects at the front should be removed to manipulate the objects in the back) makes the simultaneous task execution difficult. We propose a coordination method that determines which robot relocates which object so as to perform tasks simultaneously. Given a set of objects to be relocated, the objective is to maximize the number of switches between the robots in performing relocation tasks. Thus, one robot can pick an object in the clutter while the other robot places an object in hand to the outside of the clutter. However, the object to be relocated may not be accessible to all robots, so switching could not always be achieved. Our method is based on the uniform-cost search so the number of switches can be maximized. We also propose a greedy variant whose computation time is shorter. From experiments, we show that our method reduces the completion time of the mission by at least 22.9% (at most 27.3%) compared to the methods with no consideration of switching.

We consider the problem of rearranging objects in a cluttered and confined space using a robotic manipulator. The goal is to retrieve a target object from the clutter where the target is occluded by other objects. In situations where overhand grasps are not allowed, the robot needs to remove some objects to make the target accessible. In the course of removing the objects, the robot also needs to determine the locations to place the removed objects. If the robot can access enough empty spaces around or inside the clutter, the placement of the objects is trivially simple. If empty spaces are scarce, placing objects should be done in a principled way as an incorrect placement would deplete the empty spaces quickly.In this work, we propose a method that solves the problems of what and where to relocate objects inside the clutter to retrieve the target. Previously, there have been several efficient methods proposed that deal with each of the what and where to relocate problems separately. We solve the problems together using a graph structure constructed from an object configuration. Also, the method runs fast so scalable in the number of objects. Compared to a state-of-the-art method, our method reduces task and motion planning time up to 74.9% (at least 56.7%) and has a higher success rate under a short time limit for planning, which is 3 minutes.

We propose a tree search-based planning algorithm for a robot manipulator to rearrange objects and grasp a target in a dense space. We consider environments where tasks cannot be completed with prehensile planning only. As assuming that a manipulator is only allowed to grasp from the top, we aim to minimize the number of rearrangement actions and the total execution time, which affects the efficiency of manipulation. The proposed search algorithm determines the optimal sequence of object rearrangement with prehensile and non-prehensile grasping until grasping a target. For non-prehensile grasping, a heuristic function is employed to model frictions and contacts between objects and a table. Experimental results in a realistic simulated environment show that the proposed algorithm can reduce the number of rearranged obstacles up to 27% and the total execution time up to 15% with 14 objects compared to the previous work.

In this paper, we present an automatic collection method of image data for neuro-symbolic task planning for robot navigation. Collecting images for robot task planning would often be overwhelmed by laborious chores to operate the robot, change the environment, and repeatedly capture quality-assured images. We propose a method using a robotic simulator to perform a series of repetitive processes for data collection automatically. It generates (i) a random instance of the navigation problem, (ii) a simulation environment that depicts the instance, (iii) a planning problem instance described in a classical planning language, (iv) a task plan that solves the planning problem, (v) control inputs for the robot to execute the task plan, and (vi) a sequence of cropped images capturing the evolving states of the robot and the world while the robot performs the plan. We use one of the state-of-the-art neuro-symbolic planning models to validate our method. From the evaluation, the model achieves at most 92.6% of the success rate in generating task plans successfully from only a pair of images showing the initial and the desired state.

In this article, we present a task and motion planning method for retrieving a target object from clutter using a robotic manipulator. We consider dense and cluttered environments where some objects must be removed in order to retrieve the target without collisions. To ensure a successful execution, the interplay between task planning (what to remove in what order) and motion planning (how to remove) is crucial. Thus, the task and motion planning approach combining a symbolic task planner and a geometric motion planner becomes one of the major paradigms in manipulation planning. However, motion planning in dense clutter often leads to frequent failures, so repetitive task replanning is inevitable. Although symbolic task planners are general and domain-independent, they do not scale; so we need an efficient task planner specialized for dense clutter for fast completion of tasks. We propose a polynomial-time task planner for object manipulation in clutter that can be combined with any motion planner. We aim to optimize the number of pick-and-place actions which often determines the efficiency of object manipulation tasks. We consider common situations that could occur in clutter: 1) all object locations are known, 2) some hidden objects are revealed while relocating some front objects, and 3) the target is hidden until some objects are removed. Our method is shown to reduce the number of pick-and-place actions compared to baseline methods (e.g., at least 28.0% of reduction in a known static environment with 20 objects). We also deploy the proposed method to two physical robots with vision systems to show that our method can solve real-world problems.

We present an algorithm determining where to relocate objects inside a cluttered and confined space while rearranging objects to retrieve a target object. Although methods that decide what to remove have been proposed, planning for the placement of removed objects inside a workspace has not received much attention. Rather, removed objects are often placed outside the workspace, which incurs additional laborious work (e.g., motion planning and execution of the manipulator and the mobile base, perception of other areas). Some other methods manipulate objects only inside the workspace but without a principle so the rearrangement becomes inefficient.In this work, we consider both monotone (each object is moved only once) and non-monotone arrangement problems which have shown to be $\mathcal{N}\mathcal{P}$-hard. Once the sequence of objects to be relocated is given by any existing algorithm, our method aims to minimize the number of pick-and-place actions to place the objects until the target becomes accessible. From extensive experiments, we show that our method reduces the number of pick-and-place actions and the total execution time (the reduction is up to 23.1% and 28.1% respectively) compared to baseline methods while achieving higher success rates.

This paper presents a task and motion planning (TAMP) framework for a robotic manipulator in order to retrieve a target object from clutter. We consider a configuration of objects in a confined space with a high density so no collision-free path to the target exists. The robot must relocate some objects to retrieve the target without collisions. For fast completion of object rearrangement, the robot aims to optimize the number of pick-and-place actions which often determines the efficiency of a TAMP framework.We propose a task planner incorporating motion planning to generate executable plans which aims to minimize the number of pick-and-place actions. In addition to fully known and static environments, our method can deal with uncertain and dynamic situations incurred by occluded views. Our method is shown to reduce the number of pick-and-place actions compared to baseline methods (e.g., at least 28.0% of reduction in a known static environment with 20 objects).

In this paper, we study human trust and its computational models in supervisory control of swarm robots with varied levels of autonomy (LOA) in a target foraging task. We implement three LOAs: manual, mixed-initiative (MI), and fully autonomous LOA. While the swarm in the MI LOA is controlled by a human operator and an autonomous search algorithm collaboratively, the swarms in the manual and autonomous LOAs are fully directed by the human and the search algorithm, respectively. From user studies, we find that humans tend to make their decisions based on physical characteristics of the swarm rather than its performance since the task performance of swarms is not clearly perceivable by humans. Based on the analysis, we formulate trust as a Markov decision process whose state space includes the factors affecting trust. We develop variations of the trust model for different LOAs. We employ an inverse reinforcement learning algorithm to learn behaviors of the operator from demonstrations where the learned behaviors are used to predict human trust. Compared to an existing model, our models reduce the prediction error by at most 39.6%, 36.5%, and 28.8% in the manual, MI, and auto-LOA, respectively.

In this article, we study multirobot task allocation problems where task costs vary. The variation may be, for example, due to the revelation of new information or other dynamic circumstances. As robots update their cost estimates, typically they will update task assignments to reflect the new information using additional communication and computation. In dynamic settings, the robots are continually repairing the optimality of the system's task assignments, which can incur substantial communication and computation. We investigate how one can reduce communication and centralized computation expense during execution by using a prior model of how costs may change and performing upfront computation of possible robot-task assignments. First, we develop an algorithm that partitions a team of robots into several independent subteams that are able to maintain global optimality by communicating entirely amongst themselves. Second, we propose a method for computing the worst-case cost suboptimality if robots persist with the initial assignment and perform no further communication and computation. Finally, we introduce an algorithm to assess whether cost changes affect the optimality of the current assignment through a succession of local communication exchanges. Experimental results show that the proposed methods are helpful in reducing the degree of centralization needed by a multirobot system (e.g., the third method gave at least 45% reduction of global communication across all scenarios studied). The methods are valuable in transitioning multirobot techniques, which have met with success in structured applications (such as factories and warehouses) to the broader, wilder world.

We present an algorithm that produces a plan for relocating obstacles in order to grasp a target in clutter by a robotic manipulator without collisions. We consider configurations where objects are densely populated in a constrained and confined space. Thus, there exists no collision-free path for the manipulator without relocating obstacles. Since the problem of planning for object rearrangement has shown to be NP-hard, it is difficult to perform manipulation tasks efficiently which could frequently happen in service domains (e.g., taking out a target from a shelf or a fridge). Our proposed planner employs a collision avoidance scheme which has been widely used in mobile robot navigation. The planner determines an obstacle to be removed quickly in real time. It also can deal with dynamic changes in the configuration (e.g., changes in object poses). Our method is shown to be complete and runs in polynomial time. Experimental results in a realistic simulated environment show that our method improves up to 31% of the execution time compared to other competitors.

The interaction between swarm robots and human operators is significantly different from the traditional humanrobot interaction due to unique characteristics of the system, such as high cognitive complexity and difficulties in state estimation. In this paper, we concentrated on the method of conveying input from the operator to the swarm. Previous research has shown that control through switching between behaviors offers the greatest flexibility but is particularly difficult for human operators. A recently developed method for finding optimal sequences for composing behaviors offered a potential tool for aiding human operators controlling swarms through behavior switching. This paper compared participants performing a navigation task with and without the availability of the optimal sequencing aid. Results showed that the task of preplanning a sequence of behaviors and durations appeared more difficult for participants than switching between executing behaviors to navigate. Users who used the aid frequently was found to create shorter paths than infrequent users and the control group. In the trails that the aid was used, participants tended to generate more complicated sequences and achieve the first attempt more rapidly, compared to the trails that the aid was not used.

In this paper, we study trust-related human factors in supervisory control of swarm robots with varied levels of autonomy (LOA) in a target foraging task. We compare three LOAs: manual, mixed-initiative (MI), and fully autonomous LOA. In the manual LOA, the human operator chooses headings for a flocking swarm, issuing new headings as needed. In the fully autonomous LOA, the swarm is redirected automatically by changing headings using a search algorithm. In the mixed-initiative LOA, if performance declines, control is switched from human to swarm or swarm to human. The result of this work extends the current knowledge on human factors in swarm supervisory control. Specifically, the finding that the relationship between trust and performance improved for passively monitoring operators (i.e., improved situation awareness in higher LOAs) is particularly novel in its contradiction of earlier work. We also discover that operators switch the degree of autonomy when their trust in the swarm system is low. Last, our analysis shows that operator's preference for a lower LOA is confirmed for a new domain of swarm control.

In this paper, we study the model of human trust where an operator controls a robotic swarm remotely for a search mission. Existing trust models in human-in-the-loop systems are based on task performance of robots. However, we find that humans tend to make their decisions based on physical characteristics of the swarm rather than its performance since task performance of swarms is not clearly perceivable by humans. We formulate trust as a Markov decision process whose state space includes physical parameters of the swarm. We employ an inverse reinforcement learning algorithm to learn behaviors of the operator from a single demonstration. The learned behaviors are used to predict the trust level of the operator based on the features of the swarm.

We address the problem of finding the optimal assignment of tasks to a team of robots when the associated costs may vary, which arises when robots deal with uncertain or dynamic situations. We detail how to compute a sensitivity analysis that characterizes how much costs may change before optimality is violated. Using this analysis, robots are able to avoid unnecessary re-assignment computations and reduce global communication. First, given a model of how costs may evolve, we develop an algorithm to partition the robots into independent cliques, each of which maintains global optimality by communicating only amongst themselves. Second, we propose a method for computing the worst-case sub-optimality if robots persist with the initial assignment, performing no further communication/computation. Lastly, we develop an algorithm that assesses whether cost changes affect the optimality through an escalating succession of local checks. Experiments show that the methods reduce the degree of centralization needed by a multi-robot system.

This paper considers multirobot task allocation problems where the estimated costs for performing tasks are interrelated, and the overall team objective need not be a standard sum-of-costs (or utilities) model, enabling straightforward treatment of the additional costs incurred by resource contention. In the model we introduce, a team may choose one of a set of shared resources to perform a task (e.g., several routes to reach a destination), and interference is modeled when multiple robots use the same resource. We show that the general problem is NP-hard, and investigate specialized subinstances with particular cost structures. For the general problem, we describe an exact algorithm which finds an optimal assignment in a reasonable time on small instances. Aiming at larger problems, we turn two particular subinstances, introducing an two algorithms that find assignments quickly even for problems of considerable size, the first being optimal, the second being an approximation algorithm but also producing high-quality solutions with bounded suboptimality.

We consider optimization of the multi-robot task-allocation problem when the overall performance of the team need not be a standard sum-of-cost model. We introduce a generalization that allows for the additional cost incurred by resource contention to be treated in a straightforward manner. In this variant, robots may choose one of shared resources to perform a task, and interference may be modeled as occurring when multiple robots use the same resource. We investigate the general NP-hard problem and instances where the interference results in linear or convex penalization functions. We propose an exact algorithm for the general problem and polynomial-time algorithms for the other problems. The exact algorithm finds an optimal assignment in a reasonable time on small instances. The other two algorithms quickly find an optimal and a high-quality approximation assignment even if a problem is of considerable size. In contrast to conventional approximation methods, our algorithm provides the performance guarantee.

This paper deals with a path planning problem for turning motion of a car-like vehicle. We propose a turning method which finds a curvature continuous optimal path between two positions for a car-like vehicle.

In this paper, we propose a new design of a flexible enveloping grasper for pick and place tasks with the low complexity in manipulation and task planning for the purpose of practical use in the near future. Flexible material for the grasper has many advantageous characteristics inherently including robustness against manipulation errors and the ability to increase contact area with a grasped object and the grasping force. Compliance of the grasper material also contributes to reduction in complexity of the processes such as the force control, sensor-motor coordination, and manipulation by self-adaptation. Two properties, flexibility and compliance, mentioned above help the proposed grasper minimize the internal forces in a passive manner and achieve the successful force distribution with self-adaptivity when performing enveloping grasping. In order to demonstrate our work, we have constructed 2 different prototypes of flexible enveloping grasper. Experimental results validate robust performances of the proposed grasper.

In this paper, we propose an algorithmic compass that yields the heading information of a mobile robot using the vanishing point in indoor environments: VPass. With the VPass, a loop-closing effect (which is a significant reduction of errors by revisiting a known place through a loop) can be achieved even for a loop-less environment. From the implementation point of view, the VPass is useful because it can be appended upon any existing navigation algorithms. Experimental results show that the VPass yields accurate angle information in indoor environments for paths with lengths of around 200 m.