Author name cluster

Nilanjan Chakraborty

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

46 papers

2 author rows

ICRA Conference 2025 Conference Paper

On the Synthesis of Reactive Collision-Free Whole-Body Robot Motions: A Complementarity-Based Approach

Haowen Yao
Riddhiman Laha
Anirban Sinha
Jonas Hall
Luis F. C. Figueredo
Nilanjan Chakraborty
Sami Haddadin

This paper is about generating motion plans for high degree-of-freedom systems that account for both static and dynamic collisions along the entire body. A particular class of mathematical programs with complementarity constraints become useful in this regard. Optimization-based planners can tackle confined space trajectory planning while being cognizant of robot and (mostly static) obstacle constraints. However, handling moving obstacles is non-trivial in a real-time setting. To this end, we present the FLIQC (Fast LInear Quadratic Complementarity based) motion planner. Our reactive planner employs a novel motion model that captures the entire rigid robot as well as the obstacle geometry and ensures nonpenetration between the surfaces due to the imposed constraint. We perform thorough comparative studies with the state-of-the-art, which demonstrate improved performance. Extensive simulation and hardware experiments validate our claim of generating continuous and real-time motion plans at 1 kHz for modern collaborative robots with constant minimal parameters.

ICRA Conference 2025 Conference Paper

Point Cloud Decomposition for Task-Oriented Grasping

Khiem Phi
Aditya Patankar
Dasharadhan Mahalingam
Nilanjan Chakraborty
I. V. Ramakrishnan

Accurate localization of graspable regions within a single object point cloud is critical to enable task-based robot grasps. State-of-the-art task-based robot grasp synthesis methods fit over-approximated 3D bounding boxes that, in some cases, fail to isolate graspable regions even if they exist. While deep learning or geometrical shape decomposition methods can offer improved approximations, they lack guarantees for the graspability of segmented regions, require prior knowledge of the object, and/or demand large annotated datasets for fine-tuning. In this paper, we overcome these limitations to introduce ITSI (Iterative Slicing). ITSI is a complete, taskoriented grasp synthesis approach that functions independently of object-specific knowledge. ITSI effectively segments multiple graspable regions that conform to the constraints of robot grippers, thereby enabling compatibility with any object a robot seeks to grasp and any robot gripper size. Our extensive realworld and simulation experiments on diverse object datasets demonstrate how ITSI dramatically increases the number of discoverable robot grasps by up to 44 % when compared to the state-of-the-art. We also expand ITSI's capabilities beyond task-based robot grasp synthesis to highlight its performance in human affordance segmentation, where our performance is comparable to fully supervised deep-learning based methods (in fact, we outperform them by 1 %).

ICRA Conference 2025 Conference Paper

Provable Methods for Searching with an Imperfect Sensor

Prahlad Narasimhan Kasthurirangan
Linh Nguyen 0004
Michael Perk
Nilanjan Chakraborty
Joseph S. B. Mitchell

Assume that a target is known to be present at an unknown point among a finite set of locations in the plane. We search for it using a mobile robot that has imperfect sensing capabilities. It takes time for the robot to move between locations and search a location; we have a total time budget within which to conduct the search. We study the problem of computing a search path/strategy for the robot that maximizes the probability of detection of the target. Considering non-uniform travel times between points (e. g. , based on the distance between them) is crucial for search and rescue applications; such problems have been investigated to a limited extent due to their inherent complexity. In this paper, we describe fast algorithms with performance guarantees for this search problem and some variants, complement them with complexity results, and perform experiments to characterize their performance.

ICRA Conference 2025 Conference Paper

Synthesizing Grasps and Regrasps for Complex Manipulation Tasks

Aditya Patankar
Dasharadhan Mahalingam
Nilanjan Chakraborty

In complex manipulation tasks, e. g. , manipulation by pivoting, the motion of the object being manipulated has to satisfy path constraints that can change during the motion. Therefore, a single grasp may not be sufficient for the entire path, and the object may need to be regrasped. Additionally, geometric data for objects from a sensor are usually available in the form of point clouds. The problem of computing grasps and regrasps from point-cloud representation of objects for complex manipulation tasks is a key problem in endowing robots with manipulation capabilities beyond pick-and-place. In this paper, we formalize the problem of grasping/regrasping for complex manipulation tasks with objects represented by (partial) point clouds and present an algorithm to solve it. We represent a complex manipulation task as a sequence of constant screw motions. Using a manipulation plan skeleton as a sequence of constant screw motions, we use a grasp metric to find graspable regions on the object for every constant screw segment. The overlap of the graspable regions for contiguous screws are then used to determine when and how many times the object needs to be regrasped. We present experimental results on point cloud data collected from RGB-D sensors to illustrate our approach.

IROS Conference 2025 Conference Paper

Transferring Kinesthetic Demonstrations across Diverse Objects for Manipulation Planning

Dibyendu Das
Aditya Patankar
Nilanjan Chakraborty
C. R. Ramakrishnan 0001
I. V. Ramakrishnan

Given a demonstration of a complex manipulation task, such as pouring liquid from one container to another, we seek to generate a motion plan for a new task instance involving objects with different geometries. This is nontrivial since we need to simultaneously ensure that the implicit motion constraints are satisfied (glass held upright while moving), that the motion is collision-free, and that the task is successful (e. g. , liquid is poured into the target container). We solve this problem by identifying the positions of critical locations and associating a reference frame (called motion transfer frames) on the manipulated object and the target, selected based on their geometries and the task at hand. By tracking and transferring the path of the motion transfer frames, we generate motion plans for arbitrary task instances with objects of different geometries and poses. We show results from simulation as well as robot experiments on physical objects to evaluate the effectiveness of our solution. A video supplement is available on YouTube: https://youtu.be/RuG9zMXnfR8

IROS Conference 2024 Conference Paper

A General Formulation for Path Constrained Time-Optimized Trajectory Planning with Environmental and Object Contacts

Dasharadhan Mahalingam
Aditya Patankar
Riddhiman Laha
Srinivasan Lakshminarayanan
Sami Haddadin
Nilanjan Chakraborty

A typical manipulation task consists of a manipulator equipped with a gripper to grasp and move an object with constraints on the motion of the hand-held object, which may be due to the nature of the task itself or from object-environment contacts. In this paper, we study the problem of computing joint torques and grasping forces for time-optimal motion of an object, while ensuring that the grasp is not lost and any constraints on the motion of the object, either due to dynamics, environment contact, or no-slip requirements, are also satisfied. We present a second-order cone program (SOCP) formulation of the time-optimal trajectory planning problem that considers nonlinear friction cone constraints at the hand-object and object-environment contacts. Since SOCPs are convex optimization problems that can be solved optimally in polynomial time using interior point methods, we can solve the trajectory optimization problem efficiently. We present simulation results on three examples, including a non-prehensile manipulation task, which shows the generality and effectiveness of our approach.

ICRA Conference 2024 Conference Paper

Containerized Vertical Farming Using Cobots

Dasharadhan Mahalingam
Aditya Patankar
Khiem Phi
Nilanjan Chakraborty
Ryan McGann
I. V. Ramakrishnan

Containerized vertical farming is a type of vertical farming practice using hydroponics in which plants are grown in vertical layers within a mobile shipping container. Space limitations within shipping containers make the automation of different farming operations challenging. In this paper, we explore the use of cobots (i. e. , collaborative robots) to automate two key farming operations, namely, the transplantation of saplings and the harvesting of grown plants. Our method uses a single demonstration from a farmer to extract the motion constraints associated with the tasks, namely, transplanting and harvesting, and can then generalize to different instances of the same task. For transplantation, the motion constraint arises during insertion of the sapling within the growing tube, whereas for harvesting, it arises during extraction from the growing tube. We present experimental results to show that using RGBD camera images (obtained from an eye-in-hand configuration) and one demonstration for each task, it is feasible to perform transplantation of saplings and harvesting of leafy greens using a cobot, without task-specific programming.

ICRA Conference 2023 Conference Paper

Human-Guided Planning for Complex Manipulation Tasks Using the Screw Geometry of Motion

Dasharadhan Mahalingam
Nilanjan Chakraborty

In this paper, we present a novel method of motion planning for performing complex manipulation tasks by using human demonstration and exploiting the screw geometry of motion. We consider complex manipulation tasks where there are constraints on the motion of the end effector of the robot. Examples of such tasks include opening a door, opening a drawer, transferring granular material from one container to another with a spoon, and loading dishes to a dishwasher. Our approach consists of two steps: First, using the fact that a motion in the task space of the robot can be approximated by using a sequence of constant screw motions, we segment a human demonstration into a sequence of constant screw motions. Second, we use the segmented screws to generate motion plans via screw-linear interpolation for other instances of the same task. The use of screw segmentation allows us to capture the invariants of the demonstrations in a coordinate-free fashion, thus allowing us to plan for different task instances from just one example. We present extensive experimental results on a variety of manipulation scenarios showing that our method can be used across a wide range of manipulation tasks.

IROS Conference 2023 Conference Paper

Task-Oriented Grasping with Point Cloud Representation of Objects

Aditya Patankar
Khiem Phi
Dasharadhan Mahalingam
Nilanjan Chakraborty
I. V. Ramakrishnan

In this paper, we study the problem of task-oriented grasp synthesis from partial point cloud data using an eye-in-hand camera configuration. In task-oriented grasp synthesis, a grasp has to be selected so that the object is not lost during manipulation, and it is also ensured that adequate force/moment can be applied to perform the task. We formalize the notion of a gross manipulation task as a constant screw motion (or a sequence of constant screw motions) to be applied to the object after grasping. Using this notion of task, and a corresponding grasp quality metric developed in our prior work, we use a neural network to approximate a function for predicting the grasp quality metric on a cuboid shape. We show that by using a bounding box obtained from the partial point cloud of an object, and the grasp quality metric mentioned above, we can generate a good grasping region on the bounding box that can be used to compute an antipodal grasp on the actual object. Our algorithm does not use any manually labeled data or grasping simulator, thus making it very efficient to implement and integrate with screw linear interpolation-based motion planners. We present simulation as well as experimental results that show the effectiveness of our approach. Website: https://irsl-sbu.github.io/Task-Oriented-Grasping-from-Point-Cloud-Representation/.

ICRA Conference 2022 Conference Paper

Coordinate Invariant User-Guided Constrained Path Planning with Reactive Rapidly Expanding Plane-Oriented Escaping Trees

Riddhiman Laha
Ruiai Sun
Wenxi Wu
Dasharadhan Mahalingam
Nilanjan Chakraborty
Luis F. C. Figueredo
Sami Haddadin

As collaborative robots move closer to human environments, motion generation and reactive planning strategies that allow for elaborate task execution with minimal easy-to-implement guidance whilst coping with changes in the environment is of paramount importance. In this paper, we present a novel approach for generating real-time motion plans for point-to-point tasks using a single successful human demonstration. Our approach is based on screw linear interpolation, which allows us to respect the underlying geometric constraints that characterize the task and are implicitly present in the demonstration. We also integrate an original reactive collision avoidance approach with our planner. We present extensive experimental results to demonstrate that with our approach, by using a single demonstration of moving one block, we can generate motion plans for complex tasks like stacking multiple blocks (in a dynamic environment). Analogous generalization abilities are also shown for tasks like pouring and loading shelves. For the pouring task, we also show that a demonstration given for one-armed pouring can be used for planning pouring with a dual-armed manipulator of different kinematic structure.

ICRA Conference 2021 Conference Paper

Chance Constrained Simultaneous Path Planning and Task Assignment with Bottleneck Objective

Fan Yang
Nilanjan Chakraborty

We present a novel algorithm for combined task assignment and path planning on a roadmap with stochastic costs. In this problem, the initially unassigned robots and tasks are located at known positions in a roadmap. We want to assign a unique task to each robot and compute a path for the robot to go to the task location. Given the means and variances of travel cost, our goal is to develop algorithms that guarantee that for each robot, with high probability, the total travel cost is below a minimum value in any realization of the stochastic travel costs. We prove that the solution can be obtained by solving (a) a chance-constrained shortest path problems for all robot-task pairs and (b) a linear bottleneck assignment problem in which the cost of an assignment is equal to the optimal objective value of the former problem. We propose algorithms for solving the chance-constrained shortest path problem either optimally or approximately by solving a number of deterministic shortest path problems that minimize some linear combination of means and variances of edge costs. We present simulation results on randomly generated networks and data to demonstrate that our algorithm is scalable with the number of robots (or tasks) and the size of the network.

IROS Conference 2021 Conference Paper

Computing a Task-Dependent Grasp Metric Using Second-Order Cone Programs

Amin Fakhari
Aditya Patankar
Jiayin Xie
Nilanjan Chakraborty

Evaluating a grasp generated by a set of hand-object contact locations is a key component of many grasp planning algorithms. In this paper, we present a novel second-order cone program (SOCP) based optimization formulation for evaluating a grasps’ ability to apply wrenches to generate a linear motion along a given direction and/or an angular motion about the given direction. Our quality measure can be computed efficiently since the SOCP is a convex optimization problem, which can be solved optimally with interior point methods. A key feature of our approach is that we can consider the effect of contact wrenches from any contact of the object with the environment. This is different from the extant literature where only the effect of finger-object contacts is considered. Exploiting the environmental contact is useful in many manipulation scenarios either to enhance the dexterity of simple hands or improve the payload capability of the manipulator. In contrast to most existing approaches, our approach also takes into account the practical constraint that the maximum contact force that can be applied at a finger-object contact can be different for each contact. We can also include the effect of external forces like gravity, as well as the joint torque constraints of the fingers/manipulators. Furthermore, for a given motion path as a constant screw motion or a sequence of constant screw motions, we can discretize the path and compute a global grasp metric to accomplish the whole task with a chosen set of finger-object contact locations.

IROS Conference 2021 Conference Paper

Motion and Force Planning for Manipulating Heavy Objects by Pivoting

Amin Fakhari
Aditya Patankar
Nilanjan Chakraborty

Manipulation of objects by exploiting their contact with the environment can enhance both the dexterity and payload capability of robotic manipulators. A common way to manipulate heavy objects beyond the payload capability of a robot is to use a sequence of pivoting motions, wherein, an object is moved while some contact points between the object and a support surface are kept fixed. The goal of this paper is to develop an algorithmic approach for automated plan generation for object manipulation with a sequence of pivoting motions. A plan for manipulating a heavy object consists of a sequence of joint angles of the manipulator, the corresponding object poses, as well as the joint torques required to move the object. The constraint of maintaining object contact with the ground during manipulation results in nonlinear constraints in the configuration space of the robot, which is challenging for motion planning algorithms. Exploiting the fact that pivoting motion corresponds to movements in a subgroup of the group of rigid body motions, SE(3), we present a novel task-space based planning approach for computing a motion plan for both the manipulator and the object while satisfying contact constraints. We also combine our motion planning algorithm with a grasping force synthesis algorithm to ensure that friction constraints at the contacts and actuator torque constraints are satisfied. We present simulation results with a dual-armed Baxter robot to demonstrate our approach.

IROS Conference 2020 Conference Paper

Algorithm for Multi-Robot Chance-Constrained Generalized Assignment Problem with Stochastic Resource Consumption

Fan Yang
Nilanjan Chakraborty

We present a novel algorithm for the multi-robot generalized assignment problem (GAP) with stochastic resource consumption. In this problem, each robot has a resource (e. g. , battery life) constraint and it consumes a certain amount of resource to perform a task. In practice, the resource consumed for performing a task can be uncertain. Therefore, we assume that the resource consumption is a random variable with known mean and variance. The objective is to find an assignment of the robots to tasks that maximizes the team payoff. Each task is assigned to at most one robot and the resource constraint for each robot has to be satisfied with very high probability. We formulate the problem as a chance-constrained combinatorial optimization problem and call it the chance-constrained generalized assignment problem (CC-GAP). This problem is an extension of the deterministic generalized assignment problem, which is a NP-hard problem. We design an iterative algorithm for solving CC-GAP in which each robot maximizes its own objective by solving a chance-constrained knapsack problem in an iterative manner. The approximation ratio of our algorithm is (1+α), assuming that the deterministic knapsack problem is solved by an α-approximation algorithm. We present simulation results to demonstrate that our algorithm is scalable with the number of robots and tasks.

ICRA Conference 2020 Conference Paper

Chance Constrained Simultaneous Path Planning and Task Assignment for Multiple Robots with Stochastic Path Costs

Fan Yang
Nilanjan Chakraborty

We present a novel algorithm for simultaneous task assignment and path planning on a graph (or roadmap) with stochastic edge costs. In this problem, the initially unassigned robots and tasks are located at known positions in a roadmap. We want to assign a unique task to each robot and compute a path for the robot to go to its assigned task location. Given the mean and variance of travel cost of each edge, our goal is to develop algorithms that, with high probability, the total path cost of the robot team is below a minimum value in any realization of the stochastic travel costs. We formulate the problem as a chance-constrained simultaneous task assignment and path planning problem (CC-STAP). We prove that the optimal solution of CC-STAP can be obtained by solving a sequence of deterministic simultaneous task assignment and path planning problems in which the travel cost is a linear combination of mean and variance of the edge cost. We show that the deterministic problem can be solved in two steps. In the first step, robots compute the shortest paths to the task locations and in the second step, the robots solve a linear assignment problem with the costs obtained in the first step. We also propose a distributed algorithm that solves CC-STAP near-optimally. We present simulation results on randomly generated networks and data to demonstrate that our algorithm is scalable with the number of robots (or tasks) and the size of the network.

IROS Conference 2020 Conference Paper

Hand-Object Contact Force Synthesis for Manipulating Objects by Exploiting Environment

Aditya Patankar
Amin Fakhari
Nilanjan Chakraborty

In this paper, we study the problem of computing grasping forces for quasi-static manipulation of large and heavy objects, by exploiting object-environment contacts. We present a general formulation of this problem as a Second-Order Cone Program (SOCP) that considers (i) contact friction constraints at the object-manipulator contacts and object-environment contacts, (ii) force/moment equilibrium constraints, and (iii) manipulator joint torque constraints. The SOCP formulation implies that the optimal grasping forces for manipulating objects with the help of the environment can be computed efficiently. Different optimization objectives like minimizing contact forces at the object-manipulator contacts or minimizing joint torques of manipulators can be considered. We evaluated our method by simulations of single-handed and dual-handed manipulation scenarios.

IROS Conference 2020 Conference Paper

Minimally Disruptive Connectivity Enhancement for Resilient Multi-Robot Teams

Wenhao Luo
Nilanjan Chakraborty
Katia P. Sycara

In this work, we focus on developing algorithms to maintain and enhance the connectivity of a multi-robot system with minimal disruption to the primary tasks that the robots are performing. Such algorithms are useful for collaborating robots to be resilient to reduction in connectivity of the communication graph of the robot team when robots can arrive or leave. These algorithms are also useful in a supervisory control setting when an operator wants to enhance the connectivity of the robot team. In contrast to many existing works that can only maintain the current connectivity of the multi-robot graph, we propose a generalized connectivity control framework that allows for reconfiguration of the multi-robot system to provably satisfy any connectivity demand, while minimally disrupting the execution of their original tasks. In particular, we propose a novel k-Connected Minimum Resilient Graph (k-CMRG) algorithm to compute an optimal k-connectivity graph that minimally constrains the robots' original task-related motion, and employ the Finite-Time Convergence Control Barrier Function (FCBF) to enforce the pairwise robot motion constraints defined by the edges of the graph. The original controllers are minimally modified to drive the robots and form the k-CMRG. We demonstrate the effectiveness of our approach via simulations in the presence of multiple tasks and robot failures.

IROS Conference 2020 Conference Paper

On Screw Linear Interpolation for Point-to-Point Path Planning

Anik Sarker
Anirban Sinha
Nilanjan Chakraborty

Robot motion is controlled in the joint space whereas the robots have to perform tasks in their task space. Many tasks like carrying a glass of liquid, pouring liquid, opening a drawer requires constraints on the end-effector during the motion. The forward and inverse kinematic mappings between joint space and task space are highly nonlinear and multi-valued (for IK). Consequently, modeling task space constraints like keeping the orientation of the end-effector fixed while changing its position (which is required for carrying a cup of liquid without dropping it) is quite complex in the joint space. In this paper, we show that the use of screw linear interpolation to plan motions in the task space combined with resolved motion rate control to compute the corresponding joint space path, allows one to satisfy many common task space motion constraints in motion planning, without explicitly modeling them. In particular, any motion constraint that forms a subgroup of the group of rigid body motions can be incorporated in our planning scheme, without explicit modeling. We present simulation and experimental results on Baxter robot for different tasks with task space constraints that demonstrates the usefulness of our approach.

ICRA Conference 2019 Conference Paper

Geometric Search-Based Inverse Kinematics of 7-DoF Redundant Manipulator with Multiple Joint Offsets

Anirban Sinha
Nilanjan Chakraborty

We propose a geometric method to solve inverse kinematics (IK) problems of 7-DoF manipulators with joint offsets at shoulder, elbow, and wrist. Traditionally, inverse position kinematics for redundant manipulators are solved by using an iterative method based on the pseudo-inverse of the manipulator Jacobian. This provides a single solution among the infinitely many possible solutions for the IK problem of redundant manipulators. There are no closed-form IK solutions for redundant manipulators with multiple joint offsets. Using our method we can compute multiple IK solutions using two-parameter search by exploiting geometry of the structure of a redundant manipulator. Our proposed IK algorithm can handle multiple joint offsets and is mathematically simple to implement in a few lines of code. We apply our algorithm to compute IK solutions for 7-DoF redundant Baxter robot (that has joint offsets at shoulder, wrist, and elbow joints) for end-effector configurations where existing geometry-based IK solvers fail to find solutions. We also demonstrate the use of our algorithm in an application where we want to compute an IK solution (among the infinitely many possible solutions) that has minimum error bound in end-effector position, in the presence of random joint actuation and sensing uncertainties.

ICRA Conference 2019 Conference Paper

Rigid Body Motion Prediction with Planar Non-convex Contact Patch

Jiayin Xie
Nilanjan Chakraborty

We present a principled method for motion prediction via dynamic simulation for rigid bodies in intermittent contact with each other where the contact is assumed to be a planar non-convex contact patch. The planar non-convex contact patch can either be a topologically connected set or disconnected set. Such algorithms are useful in planning and control for robotic manipulation. Most work in rigid body dynamic simulation assume that the contact between objects is a point contact, which may not be valid in many applications. In this paper, by using the convex hull of the contact patch, we build on our recent work on simulating rigid bodies with convex contact patches, for simulating motion of objects with planar non-convex contact patches. We formulate a discrete-time mixed complementarity problem where we solve the contact detection and integration of the equations of motion simultaneously. Thus, our method is a geometrically-implicit method and we prove that in our formulation, there is no artificial penetration between the contacting rigid bodies. We solve for the equivalent contact point (ECP) and contact impulse of each contact patch simultaneously along with the state, i. e. , configuration and velocity of the objects. We provide empirical evidence to show that our method can seamlessly capture transition between different contact modes like patch contact to multiple or single point contact during simulation.

ICRA Conference 2018 Conference Paper

Algorithm for Optimal Chance Constrained Knapsack Problem with Applications to Multi-Robot Teaming

Fan Yang
Nilanjan Chakraborty

Motivated by applications in multirobot team selection, in this paper, we present a novel algorithm for computing optimal solution of chance-constrained 0-1 knapsack problem. In this variation of the knapsack problem, the objective function is deterministic but the weights of the items are stochastic and therefore the knapsack constraint is stochastic. We convert the chance-constrained knapsack problem to a two-dimensional discrete optimization problem on the variance-mean plane, where each point on the plane can be identified with an assignment of items to the knapsack. By exploiting the geometry of the non-convex feasible region of the chance-constrained knapsack problem in the variance-mean plane, we present a novel deterministic technique to find an optimal solution by solving a sequence of deterministic knapsack problems (called risk-averse knapsack problem). We apply our algorithm to a multirobot team selection problem to cover a given route, where the length of the route is much larger than the length each individual robot can fly and the length that an individual robot can fly is a random variable (with known mean and variance). We present simulation results on randomly generated data to demonstrate that our approach is scalable with both the number of robots and increasing uncertainty of the distance an individual robot can travel.

ICRA Conference 2017 Conference Paper

Algorithm for optimal chance constrained linear assignment

Fan Yang
Nilanjan Chakraborty

In this paper, we design provably-good algorithms for task allocation in multi-robot systems in the presence of payoff uncertainty. We consider a group of robots that has to perform a given set of tasks where each robot performs at most one task. The payoffs of the robots doing the tasks are assumed to be Gaussian random variables with known mean and variances. The total payoff of the robots is a sum of the individual payoffs of all the robots. The goal is to find an assignment with maximum payoff that can be achieved with a specified probability irrespective of the realization of the random variable. This problem can be formulated as a chance constrained combinatorial optimization problem. We develop a novel deterministic technique to solve this chance constrained optimization problem that ensures that the chance constraints are always satisfied. Adopting the notion of risk-aversion from the economics literature, we formulate a risk-averse task allocation problem, which is a deterministic integer optimization problem. We prove that by repeatedly solving the risk-averse task allocation problem using a one-dimensional search on the risk aversion parameter we find a solution for the chance constrained optimization formulation of the linear assignment problem with uncertain payoffs. We provide simulation results on randomly generated data to demonstrate our approach and also compare our method to existing approaches.

ICRA Conference 2017 Conference Paper

Automated sequencing of swarm behaviors for supervisory control of robotic swarms

Sasanka Nagavalli
Nilanjan Chakraborty
Katia P. Sycara

Robotic swarms are distributed systems that exhibit global behaviors arising from local interactions between individual robots. Each robot can be programmed with several local control laws that can be activated depending on an operator's choice of global swarm behavior. While some simple behaviors (e. g. rendezvous) with guaranteed performance on known objectives under strict assumptions have been studied in the literature, real missions occur in uncontrolled environments with dynamically arising objectives and require combinations of behaviors. Given a library of swarm behaviors, a supervisory operator commanding the swarm must choose a sequence of behaviors to execute in order to accomplish a particular task during a mission composed of many dynamically arising tasks. In this paper, we formalize the problem of finding an optimal behavior sequence to maximize swarm performance on a complex task. Given the swarm behavior library, a set of decision time points and a performance criterion, we present an informed search algorithm that computes the maximum performance behavior sequence. The algorithm is proven to be optimal and complete. A relevant modification is presented that generates bounded suboptimal solutions more quickly. We apply the algorithm to a swarm navigation application and a dynamic area coverage application, demonstrating the utility of our algorithm even in situations where the behaviors in the library have not been designed for the task at hand.

IROS Conference 2016 Conference Paper

Distributed knowledge leader selection for multi-robot environmental sampling under bandwidth constraints

Wenhao Luo
Shehzaman S. Khatib
Sasanka Nagavalli
Nilanjan Chakraborty
Katia P. Sycara

In many multi-robot applications such as target search, environmental monitoring and reconnaissance, the multi-robot system operates semi-autonomously, but under the supervision of a remote human who monitors task progress. In these applications, each robot collects a large amount of task-specific data that must be sent to the human periodically to keep the human aware of task progress. It is often the case that the human-robot communication links are extremely bandwidth constrained and/or have significantly higher latency than inter-robot communication links, so it is impossible for all robots to send their task-specific data together. Thus, only a subset of robots, which we call the knowledge leaders, can send their data at a time. In this paper, we study the knowledge leader selection problem, where the goal is to select a subset of robots with a given cardinality that transmits the most informative task-specific data for the human. We prove that the knowledge leader selection is a submodular function maximization problem under explicit conditions and present a novel distributed submodular optimization algorithm that has the same approximation guarantees as the centralized greedy algorithm. The effectiveness of our approach is demonstrated using numerical simulations.

IJCAI Conference 2015 Conference Paper

A Crowdfunding Model for Green Energy Investment

Ronghuo Zheng
Ying Xu
Nilanjan Chakraborty
Katia Sycara

This paper studies a new renewable energy investment model through crowdfunding, which is motivated by emerging community solar farms. In this paper we develop a sequential game theory model to capture the interactions among crowdfunders, the solar farm owner, and an electricity company who purchases renewable energy generated by the solar farm in a multi-period framework. By characterizing a unique subgame-perfect equilibrium, and comparing it with a benchmark model without crowdfunding, we find that under crowdfunding although the farm owner reduces its investment level, the overall green energy investment level is increased due to the contribution of crowdfunders. We also find that crowdfunding can increase the penetration of green energy in consumption and thus reduce the energy procurement cost of the electricity company. Finally, the numerical results based on real data indicates crowdfunding is a simple but effective way to boost green generation.

ICRA Conference 2015 Conference Paper

Multi-robot long-term persistent coverage with fuel constrained robots

Derek Mitchell
Micah Corah
Nilanjan Chakraborty
Katia P. Sycara
Nathan Michael

In this paper, we present an algorithm to solve the Multi-Robot Persistent Coverage Problem (MRPCP). Here, we seek to compute a schedule that will allow a fleet of agents to visit all targets of a given set while maximizing the frequency of visitation and maintaining a sufficient fuel capacity by refueling at depots. We also present a heuristic method to allow us to compute bounded suboptimal results in real time. The results produced by our algorithm will allow a team of robots to efficiently cover a given set of targets or tasks persistently over long periods of time, even when the cost to transition between tasks is dynamic.

IROS Conference 2015 Conference Paper

Multi-Robot Persistent Coverage with stochastic task costs

Derek Mitchell
Nilanjan Chakraborty
Katia P. Sycara
Nathan Michael

We propose the Stochastic Multi-Robot Persistent Coverage Problem (SMRPCP) and correspondant methodology to compute an optimal schedule that enables a fleet of energy-constrained unmanned aerial vehicles to repeatedly perform a set of tasks while maximizing the frequency of task completion and preserving energy reserves via recharging depots. The approach enables online modeling of uncertain task costs and yields a schedule that adapts according to an evolving energy expenditure model. A fast heuristic method is formulated that enables online generation of a schedule that concurrently maximizes task completion frequency and avoids the risk of individual robot energy-depletion and consequential platform failure. Failure mitigation is introduced through a recourse strategy that routes robots based on acceptable levels of risk. Simulation and experimental results evaluate the efficacy of the proposed methodology and demonstrate online system-level adaptation due to increasingly certain costs models acquired during the deployment execution.

IJCAI Conference 2015 Conference Paper

Nonnegative Matrix Tri-Factorization with Graph Regularization for Community Detection in Social Networks

Yulong Pei
Nilanjan Chakraborty
Katia Sycara

Community detection on social media is a classic and challenging task. In this paper, we study the problem of detecting communities by combining social relations and user generated content in social networks. We propose a nonnegative matrix tri-factorization (NMTF) based clustering framework with three types of graph regularization. The NMTF based clustering framework can combine the relations and content seamlessly and the graph regularization can capture user similarity, message similarity and user interaction explicitly. In order to design regularization components, we further exploit user similarity and message similarity in social networks. A unified optimization problem is proposed by integrating the NMTF framework and the graph regularization. Then we derive an iterative learning algorithm for this optimization problem. Extensive experiments are conducted on three real-world data sets and the experimental results demonstrate the effectiveness of the proposed method.

IROS Conference 2014 Conference Paper

Aligning coordinate frames in multi-robot systems with relative sensing information

Sasanka Nagavalli
Andrew Lybarger
Lingzhi Luo
Nilanjan Chakraborty
Katia P. Sycara

In this paper, we present both centralized and distributed algorithms for aligning coordinate frames in multi-robot systems based on inter-robot relative position measurements. Robot orientations are not measured, but are computed by our algorithms. Our algorithms are robust to measurement error and are useful in applications where a group of robots need to establish a common coordinate frame based on relative sensing information. The problem of establishing a common coordinate frame is formulated in a least squares error framework minimizing the total inconsistency of the measurements. We assume that robots that can sense each other can also communicate with each other. In this paper, our key contribution is a novel asynchronous distributed algorithm for multi-robot coordinate frame alignment that does not make any assumptions about the sensor noise model. After minimizing the least squares error (LSE) objective for coordinate frame alignment of two robots, we develop a novel algorithm that out-performs state-of-the-art centralized optimization algorithms for minimizing the LSE objective. Furthermore, we prove that for multi-robot systems (a) with redundant noiseless relative sensing information, we will achieve the globally optimal solution (this is non-trivial because the LSE objective is non-convex for our problem), (b) with noisy information but no redundant sensing (e. g. sensing graph has a tree topology), our algorithm will optimally minimize the LSE objective. We also present preliminary results of the real-world performance of our algorithm on TurtleBots equipped with Kinect sensors.

ICRA Conference 2014 Conference Paper

Explicit vs. Tacit leadership in influencing the behavior of swarms

Saman Amirpour Amraii
Phillip M. Walker
Michael Lewis 0001
Nilanjan Chakraborty
Katia P. Sycara

Many researchers have employed some form of teleoperated leader to influence a robotic swarm; however, the way in which this influence is conveyed has not been well studied. Some researchers employ designated leaders that are known to be leaders by other members of the swarm and hence followed. Others do not impose a leader/follower distinction on the swarm's algorithms and instead choose to influence the swarm indirectly through controlling one or more of its members. Because the robustness of swarm behavior arises from its many distributed interactions, influence through designated leaders might render it susceptible to noise or disrupt its coherence by overriding these mechanisms. Conversely, limiting human influence to indirect control through the local effects of a leader might prove too sluggish to allow effective human control. This paper compares leader-based methods of each type, designated as Tacit leadership via consensus (no explicit leader/follower distinction) and Explicit leadership via flooding (influence propagating from leader takes precedence). These methods were compared in simulation and in human experiments finding that explicit leadership led to faster convergence in simulation and better performance in the experiments. Effects of noise were slightly more pronounced for Explicit leaders and cohesion slightly poorer.

IROS Conference 2014 Conference Paper

Human control of robot swarms with dynamic leaders

Phillip M. Walker
Saman Amirpour Amraii
Nilanjan Chakraborty
Michael Lewis 0001
Katia P. Sycara

Controlling a swarm of robots after deployment is difficult, due to the unpredictable and emergent behavior of swarm algorithms. Past work has focused on influencing the swarm via statically selected leaders—swarm members that the operator directly controls—that are pre-selected and remain leaders throughout the scenario execution. This paper investigates the use of dynamically selected leaders that are directly controlled by the human operator to guide the rest of the swarm, which is operating under a flocking-style algorithm. The goal of the operator is to move the swarm to goal regions that arise dynamically in the environment. We experimentally investigated (a) the effect of density of leaders on the ease of human control and system performance, and (b) how restriction of information communicated to the human operator affects the ability to guide the swarm to goal regions. The density of leaders is computed based on an extension of the random competition clustering (RCC) algorithm used in wireless sensor networks to select cluster heads. In particular, we studied the effect of different guarantees of the maximum number of hops in the communication graph from any robot to the nearest leader. Increasing the maximum hop guarantee effectively lowers the density of leaders in the swarm. Our results show that, while there was a large drop in the number of goals reached when moving from a 1-hop to a 2-hop guarantee, the difference between a 2-hop and 3-hop guarantee was not statistically significant. Furthermore, we found that performance was just as good when the information returned to the operator was restricted, showing that operators can still navigate a swarm even when they have imperfect information.

ICRA Conference 2014 Conference Paper

Neglect Benevolence in human control of robotic swarms

Sasanka Nagavalli
Lingzhi Luo
Nilanjan Chakraborty
Katia P. Sycara

Robotic swarms are distributed systems whose members interact via local control laws to achieve different behaviors. Practical missions may require a combination of different swarm behaviors, where these behavioral combinations are not known a priori but could arise dynamically due to changes in mission goals. Therefore, human interaction with the swarm (HIS) is needed. In this paper, we introduce, formally define and characterize a novel concept, Neglect Benevolence, that captures the idea that it may be beneficial for system performance if the human operator, after giving a command, waits for some time before giving a subsequent command to the swarm. This raises the important question of the existence and means of calculation of the optimal time for the operator to give input to the swarm in order to optimize swarm behavior. Human operators are limited in their ability to estimate the best time to give input to the swarm. Therefore, automated aids that calculate the optimal input time could help the human operator achieve the best system performance. Our contributions are as follows. First, we formally define the new notion of Neglect Benevolence. Second, we prove the existence of Neglect Benevolence for a class of linear dynamical systems. Third, we provide an analytic characterization and an algorithm for calculating the optimal input time. Fourth, we apply the analysis to the human control of swarm configuration.

IROS Conference 2013 Conference Paper

Distributed algorithm design for multi-robot generalized task assignment problem

Lingzhi Luo
Nilanjan Chakraborty
Katia P. Sycara

We present a provably-good distributed algorithm for generalized task assignment problem in the context of multirobot systems, where robots cooperate to complete a set of given tasks. In multi-robot generalized assignment problem (MR-GAP), each robot has its own resource constraint (e. g. , energy constraint), and needs to consume a certain amount of resource to obtain a payoff for each task. The objective is to find a maximum payoff assignment of tasks to robots such that each task is assigned to at most one robot while respecting robots' resource constraints. MR-GAP is a NP-hard problem. It is an extension of multi-robot linear assignment problem since different robots can use different amount of resource for doing a task (due to the heterogeneity of robots and tasks). We first present an auction-based iterative algorithm for MR-GAP assuming the presence of a shared memory (or centralized auctioneer), where each robot uses a knapsack algorithm as a subroutine to iteratively maximize its own objective (using a modified payoff function based on an auxiliary variable, called price of a task). Our iterative algorithm can be viewed as (an approximation of) best response assignment update rule of each robot to the assignment of other robots at that iteration. We prove that our algorithm converges to an assignment (approximately) at equilibrium under the assignment update rule, with an approximation ratio of 1+α (where α is the approximation ratio for the Knapsack problem). We also combine our algorithm with a message passing mechanism to remove the requirement of a shared memory and make our algorithm totally distributed assuming the robots' communication network is connected. Finally, we present simulation results to depict our algorithm's performance.

ICRA Conference 2013 Conference Paper

Distributed algorithm design for multi-robot task assignment with deadlines for tasks

Lingzhi Luo
Nilanjan Chakraborty
Katia P. Sycara

In this paper, we present provably-good algorithms for multi-robot task assignment, where each task has to be completed within its deadline. Each robot has a upper limit on the maximum number of tasks that it can perform due to its limited battery life, and each task takes the same amount of time to complete. Each robot has a different payoff (or cost) for the tasks and the objective is to assign the tasks to the robots such that the total payoff (cost) is maximized (minimized) while respecting the task deadline constraints. This problem is an extension of a special generalized assignment problem (where each task consumes the same time resource and must be finished), with additional deadline constraints for the time resource assignment. We show that the problem can be reduced to a problem of assigning tasks to robots, where the tasks are organized in overlapping sets, and each robot has a limit on the number of tasks it can perform from each set, which is a variant of multi-robot assignment problem with set precedence constraint (SPC-MAP) discussed in [1]. We present a distributed auction-based algorithm for this problem and prove that the solution is almost-optimal. We also present simulation results to depict the performance of our algorithm.

ICRA Conference 2013 Conference Paper

Energy efficient data collection with mobile robots in heterogeneous sensor networks

Jared Goerner
Nilanjan Chakraborty
Katia P. Sycara

In this paper, we study the problem of constructing a path for a mobile data collecting robot such that the total data collection cost (i. e. , sum of transmission energy of the sensor nodes and movement energy of the robot) in a sensor network is minimized. We assume that the sensor nodes can transmit within a certain region around their position, which is called the communication set. We model the communication set as a convex set to take into account asymmetric transmission systems (like directional antennas). We derive a necessary condition for the optimality of a mobile robot tour through the communication sets. Based on this condition, we design a three-step approach to compute a local minimum of the optimization problem. We prove that our solution is guaranteed to be within a constant factor of the global optimal solution. Our algorithm works for both 2-dimensional and 3-dimensional sensor networks where the sensor nodes are heterogeneous and can have directional communication properties. In contrast, existing algorithms for computing data collecting routes are for planar sensor networks and assume the communication sets to be discs. We also present simulation results depicting the performance of our algorithm.

AAAI Conference 2013 Conference Paper

Multiagent Coordination for Energy Consumption Scheduling in Consumer Cooperatives

Andreas Veit
Ying Xu
Ronghuo Zheng
Nilanjan Chakraborty
Katia Sycara

A key challenge to create a sustainable and energyefficient society is in making consumer demand adaptive to energy supply, especially renewable supply. In this paper, we propose a partially-centralized organization of consumers, namely, a consumer cooperative for purchasing electricity from the market. We propose a novel multiagent coordination algorithm to shape the energy consumption of the cooperative. In the cooperative, a central coordinator buys the electricity for the whole group and consumers make their own consumption decisions based on their private consumption constraints and preferences. To coordinate individual consumers under incomplete information, we propose an iterative algorithm in which a virtual price signal is sent by the coordinator to induce consumers to shift demand. We prove that our algorithm converges to the central optimal solution. Additionally we analyze the convergence rate of the algorithm via simulations on randomly generated instances. The results indicate scalability with respect to the number of agents and consumption slots.

AAMAS Conference 2013 Conference Paper

Multiagent Negotiation on Multiple Issues with Incomplete Information

Ronghuo Zheng
Nilanjan Chakraborty
Tinglong Dai
Katia Sycara

We present a reactive offer generation method for general multiagent multi-attribute negotiation, where the agents have non-linear utility functions and no information about the utility functions of other agents. We prove the convergence of the proposing method and characterize the convergence rate under a finite negotiation time. We also prove that rational agents do not have any incentive to deviate from the proposed strategy. We further present simulation results to demonstrate that on randomly generated problem instances the solution obtained from our protocol is quite close to the Nash bargaining solution.

AAMAS Conference 2012 Conference Paper

A cognitive architecture for emergency response

Felipe Meneguzzi
Siddharth Mehrotra
James Tittle
Jean Oh
Nilanjan Chakraborty
Katia Sycara
Michael Lewis

Plan recognition, cognitive workload estimation and human assistance have been extensively studied in the AI and human factors communities, but have seldom been integrated and evaluated as complete systems. In this paper, we develop an assistant agent architecture integrating plan recognition, current and future user information needs, workload estimation and adaptive information presentation to aid an emergency response manager in making high quality decisions under time stress, while avoiding cognitive overload. We describe its main components as well as results for en experiment simulating various possible executions of the emergency response plans used in the real world, comparing reaction time of an assisted versus an unassisted human.

ICRA Conference 2012 Conference Paper

Competitive analysis of repeated greedy auction algorithm for online multi-robot task assignment

Lingzhi Luo
Nilanjan Chakraborty
Katia P. Sycara

We study an online task assignment problem for multi-robot systems where robots can do multiple tasks during their mission and the tasks arrive dynamically in groups. Each robot can do at most one task from a group and the total number of tasks a robot can do is bounded by its limited battery life. There is a payoff for assigning each robot to a task and the objective is to maximize the total payoff. A special case, where each group has one task and each robot can do one task is the online maximum weighted bipartite matching problem (MWBMP). For online MWBMP, it is known that, under some assumptions on the payoffs, a greedy algorithm has a competitive ratio of 1 over 3. Our key result is to prove that for the general problem, under the same assumptions on the payoff as in MWBMP and an assumption on the number of tasks arising in each group, a repeated auction algorithm, where each group of tasks is (near) optimally allocated to the available group of robots has a guaranteed competitive ratio. We also prove that (a) without the assumptions on the payoffs, it is impossible to design an algorithm with any performance guarantee and (b) without the assumption on the task profile, the algorithms that can guarantee a feasible allocation (if one exists) have arbitrarily bad performance in the worst case. Additionally, we present simulation results depicting the average case performance of the repeated greedy auction algorithm.

ICRA Conference 2011 Conference Paper

Coverage control for mobile anisotropic sensor networks

Bruno Hexsel
Nilanjan Chakraborty
Katia P. Sycara

Distributed algorithms for (re)configuring mobile sensors to cover a given area are important for autonomous multi-robot operations in application areas such as surveillance and environmental monitoring. Depending on the assumptions about the choice of the environment, the sensor models, the coverage metric, and the motion models of sensor nodes, there are different versions of the problem that have been formulated and studied. In this paper, we consider a system of holonomic mobile robots equipped with anisotropic sensors (e. g. , limited field of view cameras) that are required to cover a polygonal region with polygonal obstacles to detect interesting events. We assume a given probability distribution of the events over a region. Motivated by scenarios where the sensing performance not only depends on the resolution of sensing but also on the relative orientation between the sensing axis and the event, we assume that the probability of detection of an event depends on both sensing parameters and the orientation of observation. We present a distributed gradient-ascent algorithm for reconfiguring the system of mobile robots so that the joint probability of detection of events over the whole region is maximized (i. e. , positioning the mobile robots and determining their sensor parameters). As an example case study, we use a system of mobile robots equipped with limited field of view cameras with pan and zoom capabilities. We present simulation results demonstrating the performance of our algorithm.

ICRA Conference 2011 Conference Paper

Multi-robot assignment algorithm for tasks with set precedence constraints

Lingzhi Luo
Nilanjan Chakraborty
Katia P. Sycara

In this paper, we present task allocation (assignment) algorithms for a multi-robot system where the tasks are divided into disjoint groups and there are precedence constraints between the task groups. Existing auction-based algorithms assume the task independence and hence can not be used directly to solve the class of multi-robot task assignment problems that we consider. In our model, each robot can do a fixed number of tasks and obtains a benefit (or incurs a cost) for each task. The tasks are divided into groups and each robot can do only one task from each group. These constraints arise when the robots have to do a set of tasks that have precedence constraints and each task takes the same time to be completed. We extend the auction algorithm to provide an almost optimal solution to the task assignment problem with set precedence constraints (the theoretical guarantees are the same as that of the original auction algorithm for unconstrained tasks). In other words, we guarantee that we will get a solution within a factor of O(n t e) of the optimal solution, where n t is the total number of tasks and ε is a parameter that we choose. We first present our algorithm using a shared memory model and then indicate how consensus algorithms can be used to make the algorithm totally distributed.

AAMAS Conference 2011 Conference Paper

The Evolution of Cooperation in Self-Interested Agent Societies: A Critical Study

Lisa-Maria Hofmann
Nilanjan Chakraborty
Katia Sycara

We study the phenomenon of evolution of cooperation in a society of self-interested agents using repeated games in graphs. A repeated game in a graph is a multiple round game, where, in each round, an agent gains payoff by playing a game with its neighbors and updates its action (state) by using the actions and/or payoffs of its neighbors. The interaction model between the agents is a two-player, two-action (cooperate and defect) Prisoner's Dilemma (PD) game (a prototypical model for interaction between self-interested agents). The conventional wisdom is that the presence of network structure enhances cooperation and current models use multiagent simulation to show evolution of cooperation. However, these results are based on particular combination of interaction game, network model and state update rules (e. g. , PD game on a grid with imitate your best neighbor rule leads to evolution of cooperation). The state-of-the-art lacks a comprehensive picture of the dependence of the emergence of cooperation on model parameters like network topology, interaction game, state update rules and initial fraction of cooperators. We perform a thorough study of the phenomenon of evolution of cooperation using (a) a set of popular categories of networks, namely, grid, random networks, scale-free networks, and small-world networks and (b) a set of cognitively motivated update rules. Our simulation results show that the evolution of cooperation in networked systems is quite nuanced and depends on the combination of network type, update rules and the initial fraction of cooperating agents. We also provide an analysis to support our simulation results.

ICRA Conference 2010 Conference Paper

Reconfiguration algorithms for mobile robotic networks

Nilanjan Chakraborty
Katia P. Sycara

For a deployed mobile robotic network to function usefully, the robots should have the capability to adjust their positions, while maintaining the network connectivity. In this paper, we present algorithms that allows a robot to decide when it is feasible for it to move to a desired point by adjusting its own positions (and the positions of some other robots in the network), while maintaining all the network connectivity constraints. Under the assumption of a disc model of communication, we show that the problem can be formulated as a convex optimization (or feasibility) problem (actually a second order cone program). Thus, the problem can be solved in polynomial time by centralized interior point algorithms. However, this requires the robot to have knowledge of the position of all the nodes in the network. Our main contribution is the development of an incremental algorithm, that solves the feasibility problem (of whether the robot can move to its desired goal) by obtaining the information about the position of the robots and their immediate neighbors only if they are required to move. We present simulation results comparing the performance of the centralized algorithm with the incremental algorithm for randomly generated networks. From simulation results, we observe that the time required by the incremental algorithm to solve the feasibility problem is relatively independent of the size of the network.

IROS Conference 2009 Conference Paper

Complementarity-based dynamic simulation for kinodynamic motion planning

Nilanjan Chakraborty
Srinivas Akella
Jeffrey C. Trinkle

In this paper, we present the use of complementarity-based dynamic simulation algorithms for kinodynamic motion planning. Dynamic simulation algorithms are used as local planning methods in sampling-based motion planning algorithms to find inputs that ensure the resulting trajectory satisfies the dynamics constraints. However, the inputs are not guaranteed to give collision-free path segments. The inputs, chosen either by random sampling or from a discretization of the available inputs, are rejected if the path segment is not collision free. In cluttered environments, finding a feasible input is difficult and sensitive to the duration ¿t of application of the input, and to the discretization resolution of the input set. When the collision constraints (or any inequality constraints on the state of the robot) are modeled as a set of complementarity constraints, the dynamic simulation algorithm gives a path segment that touches the obstacles and a set of contact forces whenever the robot makes contact with the obstacles. The sum of the chosen input forces and the contact forces transformed to the input space gives a control input that guarantees a collision-free path segment (provided it is within the actuator bounds). Thus in cluttered environments, using a complementarity-based dynamic simulation algorithm, we can find a feasible input that is relatively insensitive to the choice of ¿t and the discretization resolution of the input set. We present simple simulation examples showing the advantages of our algorithm in cluttered environments.

ICRA Conference 2008 Conference Paper

Minimum time point assignment for coverage by two constrained robots

Nilanjan Chakraborty
Srinivas Akella
John T. Wen

This paper focuses on the assignment of discrete points to two robots, in the presence of geometric and kinematic constraints between the robots. The individual points have differing processing times, and the goal is to identify an assignment of points to the robots so that the total processing time is minimized. The assignment of points to the robots is the first step in the path generation process for the robots. This work is motivated by an industrial microelectronics manufacturing system with two robots, with square footprints, that are constrained to translate along a common line while satisfying proximity and collision avoidance constraints. The N points lie on a planar base plate that can translate along the plane normal to the direction of motion of the robots. The geometric constraints on the motions of the two robots lead to constraints on points that can be processed simultaneously. We show that the point assignment for processing problem can be converted to a maximum weighted matching problem on a graph and solved optimally in O(N 3 ) time. Since this is too slow for large datasets, we present a O(N 2 ) time greedy algorithm and prove that the greedy solution is within a factor of 3/2 of the optimal solution. Finally, we provide computational results for the greedy algorithm on typical industrial datasets.

ICRA Conference 2006 Conference Paper

Proximity Queries between Convex Objects: an Interior Point Approach for Implicit Surfaces

Nilanjan Chakraborty
Jufeng Peng
Srinivas Akella
Jason E. Mitchell

In this paper, we present an interior point approach to exact distance computation between convex objects represented as intersections of implicit surfaces. The implicit surfaces considered include planes (polyhedra), quadrics, and generalizations of quadrics including superquadrics and hyperquadrics, as well as intersections of these surfaces. Exact distance computation algorithms are particularly important for applications involving objects that make contact, such as in dynamic simulations and in contact point prediction for dextrous manipulation. They can also be used in the narrow phase of hierarchical collision detection. In contrast to geometric approaches developed for polyhedral objects, we formulate the distance computation problem as a convex optimization problem; this optimization formulation has been previously described for polyhedral objects. We demonstrate that for general convex objects represented as implicit surfaces, interior point approaches are reasonably fast and in some cases, owing to their global convergence properties, are the only probably good choice for solving proximity query problems. We use an interior point algorithm that solves the KKT conditions obtained from the convex programming formulation. We present implementation results for example implicit surface objects and demonstrate that distance computation rates of about 1 kHz can be achieved