In the Watchman Route Problem (WRP), the task is to find a path for a watchman agent such that all locations in the given map will be visually seen by the watchman at least once during the path traversal. Recently, the problem has been optimally solved on a grid map using heuristic search. In this paper, we extend this work to the case of multiple agents. We call this problem the Multiple Watchman Route Problem (MWRP). In MWRP, the task is to find a path for each watchman such that each location on the map will be seen by at least one watchman. We optimally solve MWRP with heuristic search for two different objective functions with a number of A*-based variants, including an enhanced branching mechanism. We then provide an experimental study on these methods and on other attributes of this problem.

Compliant grasping systems offer a wide range of robot hand designs. Understanding the stability behavior of compliant grasps can enhance the reliability and security of such hands. A classical result in compliant grasp mechanics states that a stable multifinger grasp can suddenly lose its stability when the finger force magnitudes exceed a critical threshold determined by the grasp's geometry. This event is known as coin snapping. This paper provides a full analysis of the coin snapping phenomenon for planar grasps governed by linear compliance laws. The analysis leads to important insights concerning compliant grasp security. For instance, does a grasping system give warning signs before an object snaps out of the fingers' grip? Is this an inevitable phenomenon in linearly compliant grasps? By systematically studying the bifurcation patterns of compliant multifinger grasps, this paper provides analytic characterization of the stability behavior of these systems, as well as answers to the mentioned questions under certain simplifying assumptions. Graphical examples and experimental measurements illustrate and validate the results.

In this paper we propose an energy control based algorithm for performing swing-up regrasping. In such regrasping motion, an object is manipulated using a robotic arm around a point pinched by the arms gripper. The aim is to manipulate the object from an initial angle to regrasp it on a new desired angle relative to the gripper. The pinching point function as a semi-active joint where the gripper is able to apply only dissipative frictional torques on the object to resist its motion. We address the problem by proposing an algorithm based on energy control. Simulations on a three degrees of freedom manipulator regrasping a bar validate the proposed algorithm.

The fabrication of a multiactuator mechanism requires excessive wiring that may become the design's bottleneck. We introduce a novel actuation method for an actuated flexible manifold (AFM). The AFM is a 2-D surface embedded in ℝ2or ℝ3. The AFM shape can theoretically be manipulated into any continuous smooth function. The mechanism possesses dozens of degrees of freedom (DOF). However, an applicable AFM would require thousands or even an infinite number of DOF (for the continuous case). This paper addresses the need to aggressively reduce the number of inputs. To exemplify our optimization, we introduce an algorithm for the forward kinematics and the inverse kinematics for such mechanisms. We then present a periodic actuation method, which enables input reduction to its peripheral inputs alone. We show how a 40-DOF AFM can make the most of its capabilities, while the number of inputs substantially drops. To exemplify our results, we have fabricated an AFM as a grid using shape memory alloy artificial muscle wire. Our input method may simplify the fabrication process, reduce the mechanism's overall weight, and improve the actuation performance.

In this paper, we present the swing-up regrasping problem in which an object is manipulated using a robotic arm around a point pinched by the arm's gripper. The aim of the regrasping is to manipulate the object from an initial angle to regrasp it on a new desired angle relative to the gripper. The pinching point functions as a semiactive joint at which the gripper is able to apply only frictional torques on the object to resist its motion. We address the problem by proposing a novel approach that incorporates an impulse-momentum method with a clipped linear quadratic regulator (cLQR) based controller for stabilization on the desired angle. In particular, a suboptimal cLQR controller is presented to deal with the dissipative semiactive joint. The interaction of these methods with the unique property of the semiactive joint is investigated and analyzed. Simulations on a six degrees of freedom manipulator regrasping a bottle validate the proposed approach. Moreover, a full experiment was conducted on a robotic arm to test the approach and the control of a semiactive joint. The simulations and experiment have proven the feasibility of the method.

Abstract—A novel algorithm is proposed for offline motion planning of a robotic arm to perform a throw task of an object to reach a goal target. The planning algorithm searches for a throw trajectory that could be performed under kinematic and dynamic (i.e., kinodynamic) constraints. We parameterize the throw trajectory by a time-invariant high-dimensional vector. Then, the kinodynamic and target constraints are formulated in terms of time and the parameterization vector. These con-straints form time-varying subspaces in the parameterization space. We present a stochastic method for finding a feasible and optimal solution within the subspace. The method generates a number of random points within the parameterization space and checks their feasibility using an adaptive search. The algorithm is guaranteed under a known probability to find a solution if one exists. We present simulations and experiments on a 3R manipulator to validate the method. I.

The work presented in this paper proposes a new method for time based motion planning of a dynamic system to reach a dynamical goal within a specified time. The method enables trajectory planning based on the dynamics of the system with time constraint. Moreover, this method allows rendezvous planning of two dynamic systems where only one is controlled. To reach this objective, we introduce a new concept termed Time-Based RRT (TB-RRT) which is an extended version of the Rapidly-exploring Random Tree (RRT). The concept of the TB-RRT is to add time parameters to the nodes in the tree such that each node denotes a specific state in a specific time. The algorithm was implemented in two applications to demonstrate the approach and validate its feasibility; The first application is a one degree of freedom bat hitting a ball and the second application is a three degrees of freedom manipulator catching a moving object. Simulation results show the system accurately following the planned trajectory and the robot catching the object in time.

This paper presents an algorithm for planning the foothold positions of quadruped robots on irregular terrain. The input to the algorithm is the robot kinematics, the terrain geometry, a required motion path, as well as initial posture. Our goal is to develop general algorithm that navigate quadruped robots quasi-statically over rough terrain, using an APF (Artificial Potential Field) and graph searching. The algorithm is planning a sequence set of footholds that navigates the robot along the required path with controllable motion characteristics. Simulations results demonstrate the algorithm in a planner environment.

SpiderBot is a cable suspended mobile robot that is designed to climb walls and hang from ceilings by shooting tethered plungers onto the surface. Removing the plungers, it reels in the web, aims, and repeats the process to climb farther. SpiderBots' design was inspired by the fictional character Spider-Man. The robot can be used for carrying equipment and sensors over a disaster area to help rescue forces. It can maneuver and serve as a moving platform inside building such as workshops and hangers without taking floor space. The robot can also move between floating vessels at sea and serve as a moving crane.

We explore the problem where a group of robots with different velocities search for a target in an unbounded unknown environment. The target position is un known, hence, an online search algorithm is developed. The H-MRSTM algorithm (Heterogeneous Multi-Robot Search Time Multiplication), launches a group of n robots from a common starting location to search for the target. The robots are assigned to search inside a series of concentric discs with increasing radii. Each robot is assigned to search inside a disc and when completing the search inside this disc without finding the target, the robot is assigned to search in the next unoccupied disc. We prove that every algorithm that solves this search problem must have at least a quadratic time competitive complexity and prove that the H-MRSTM algorithm's complexity is also quadratic. Hence, we obtain both an upper and lower bound on the time competitive complexity of the search problem. Consequently, H-MRSTM is proved to be optimal. Simulations in various environments show that the average case performance of H-MRSTM is superior to that of homogeneous multi-robot and single robot algorithms. In depth simulation analyses evaluated the effect of several other parameters such as the initial disc search time, the distribution of the velocities, the number of robots and the position of the target.

We investigate the path finding problem to a target whose position is known in an unknown and unbounded environment. We present a novel motion planning algorithm which uses a group of heterogeneous robots to search for the path to the target. The algorithm assigns the robots in pairs, each two robots within a pair have the same velocity, and are cooperating to search for the path to the target. The algorithm artificially bounds each pair's search to an ellipse whose focal points are the start and the target points. Each robot pair has a different velocity, thus each pair is assigned to an ellipse with an area corresponding to the search time according to its velocity. The algorithm's performance is analyzed using time competitiveness definitions, and its upper bound is proved to be quadratic in the optimal off-line solution. The algorithm is complete and robust.

This paper presents a physical model developed to find the directions of forces and moments required to open a plastic bag - which forces will contribute toward opening the knot and which forces will lock it further. The analysis is part of the implementation of aQ(¿)-learning algorithm on a robot system. The learning task is to let a fixed-arm robot observe the position of a plastic bag located on a platform, grasp it, and learn how to shake out its contents in minimum time. The physical model proves that the learned optimal bag shaking policy is consistent with the physical model and shows that there were no subjective influences. Experimental results show that the learned policy actually converged to the best policy.

We explore an on-line problem where a group of robots has to reach a target whose position is known in an unknown planar environment whose geometry is acquired by the robots during task execution. The critical parameter in such a problem is the physical motion time, which, under the assumption of uniform velocity of all the robots, corresponds to length or cost of the path traveled by the robot which reached the target. The Competitiveness of an on-line algorithm measures its performance relative to the optimal off-line solution to the problem. While competitiveness usually means constant relative performance, this paper uses generalized competitiveness, i.e. any functional relationship between online performance and optimal off-line solution. Given an online task, its competitive complexity class is a pair of lower and upper bounds on the competitive performance of all online algorithms for the task, such that the two bounds satisfy the same functional relationship. We prove that in general any on-line navigation algorithm must have at least a quadratic competitive performance. This paper describes a new on-line navigation algorithm, called MRBUG (short for Multi-Robot BUG), which requires constant memory and has a quadratic competitive performance. Thus, the above mentioned problem is classified into a quadratic competitive class. Moreover, since MRBUG achieves the quadratic lower bound, it has optimal competitiveness. The algorithm performance is illustrated in office-like environments

Intelligently utilizing the frictional contact between a robot and its environment can prevent slip, maintain balance, and provide stability during a robot's motion. A contact model is first needed to enable robot control achieving these goals. The model should be both accurate and simple enough to allow further system analysis. In this paper we propose a simple parametric contact model, based on the form of the Hertz-Walton model. We experimentally demonstrate that this contact model can be effectively used to predict contact forces for linear and near-linear loading paths. Finally, we briefly discuss the applicability of the presented contact model for snake robot climbing. The control of the snake robot is based on stabilizing a sequence of set points.

A climbing robot mechanism is introduced, which uses dynamic movements to climb between two parallel vertical walls. This robot relies on its own internal dynamic motions to gain height, unlike previous mechanisms which are quasi- static. One benefit of dynamics is that it allows climbing with only a single actuated degree of freedom. We show with analysis, simulations and experiments that this dynamic robot is capable of climbing vertically between parallel walls. We introduce simplifications that enable us to obtain closed form approximations of the robot motion. Furthermore, this provides us with some design considerations and insights into the mechanism's ability to climb.

We explore an online problem where a group of robots has to find a target whose position is unknown in an unknown planar environment whose geometry is acquired by the robots during task execution. The critical parameter in such a problem is the physical motion time, which, under the assumption of uniform velocity of all the robots, corresponds to length or cost of the path traveled by the robot which finds the target. The competitiveness of an online algorithm measures its performance relative to the optimal offline solution to the problem. While competitiveness usually means constant relative performance, this paper uses generalized competitiveness, i.e. any functional relationship between online performance and optimal offline solution. Given an online task, its competitive complexity class is a pair of lower and upper bounds on the competitive performance of all online algorithms for the task, such that the two bounds satisfy the same functional relationship. We classify a common online motion planning problem into competitive class. In particular, it is shown that group of robots navigation to a target whose position is recognized only upon arrival belongs to a quadratic competitive class. This paper describes a new online navigation algorithm, called MRSAM (short for multi-robot search area multiplication), which requires linear memory and has a quadratic competitive performance. Moreover, it is shown that in general any online navigation algorithm must have at least a quadratic competitive performance. The MRSAM algorithm achieves the quadratic lower bound and thus has optimal competitiveness. The algorithm's performance is illustrated in an office-like environments

The mechanics of friction and compliance in multi-contact arrangements is key to understanding and predicting grasp stability and dynamic response to external loads. This paper introduces a comprehensive model for the nonlinear force-displacement relationship at a frictional contact. The model is given in an analytic lumped parameter form suitable for on-line grasping applications, and is entirely determined by material and geometric properties of the contacting bodies. The force-displacement law predicts a nonlinear tangential stiffening as the normal load increases. As a result, the composite stiffness matrix of a frictional grasp is asymmetric, indicating that such grasps are not governed by any potential energy. The consequences for grasp stability are investigated. We formulate a rule for preloading frictional grasps which guarantees stable response at the individual contacts. Then we obtain a criterion for selecting contact points which guarantees overall grasp stability. The synthesis rule and its effect on grasp stability is illustrated with a simple 2D example.

This paper presents an algorithm, called PCG, for planning the foothold positions of spider-like robots in planar tunnels bounded by piece-wise linear walls. The paper focuses on 3-limb robots, but the algorithm generalizes to robots with a higher number of limbs. The input to the PCG algorithm is a description of a tunnel having an arbitrary piece-wise linear geometry, a lower bound on the amount of friction at the contacts, as well as start and target foothold positions. Using efficient convex programming techniques, the algorithm approximates the possible foothold positions as a collection of cubes in contact c-space. A graph structure induced by the cubes has the property that its edges represent feasible motion between neighboring sets of 3-limb postures. This motion is realized by lifting one limb while the other two limbs brace the robot against the tunnel walls. A shortest-path search along the graph yields a 3-2-3 gait pattern that moves the robot from start to target using a minimum number of foothold exchanges. Simulation results demonstrate the PCG algorithm in a tunnel environment.

Presents an immobilization based control method for spider-like robots that move quasistatically in tunnel environments. The control method is based on an immobilization theory which ensures that when a spider-like mechanism is bracing against the environment at an immobile posture, the naturally occurring compliance at the contacts stabilizes the mechanism as a single body. Based on this result, we present two versions of a position control law for general k-limbed spider robots. We show that if the controller's stiffness (i.e. proportional gain) is above a lower limit determined by the spider and environment parameters, stability of the closed-loop spider system is guaranteed. We present dynamic simulations of a spider robot moving in a tunnel under the influence of the immobilization-based control law. The simulations show excellent convergence properties of the control algorithm. A four-legged spider prototype has been built, and we conclude with a description of initial experiments with this robot.

The classical notion of force closure is formulated for multifingered hands, where the fingers actively apply any desired force consistent with friction constraints at the contacts. This paper considers a simpler notion of passive force closure, where each finger obeys some force-displacement law that depends on the finger's joint parameters. The fingers apply initial preload grasping forces, and the grasped object is stabilized against external disturbances by the automatic response of the grasping fingers. After motivating the usefulness of passive force closure, we characterize the conditions for its existence. Then we introduce the passive stability set, defined as the collection of external wrenches that can be passively resisted by a given grasp. We introduce a class of grasp arrangements where the grasping mechanism is compliant while the grasped object is rigid. Such compliant-rigid systems are common, and for these systems the passive closure set can be computed in closed form. Simulation results demonstrate the computation of the passive closure set for two and three-finger planar grasps.

This paper presents a novel design of a 4-legged "spider" robot capable of moving in a wide range of two-dimensional tunnels. The spider moves in a quasi-static manner, by stably bracing itself against the tunnel walls and moving a free limb to a new position. The design has been strongly influenced by the recent immobilization theory of Rimon and Burdick (1995, 1998). The theory dictates the minimum number of limbs such a spider can have, as well as the shape of the footpads. The class of tunnel geometries dictates other key parameters of the spider, such as limb dimensions and number of degrees of freedom of each limb. We review the relevant components of the immobilization theory, then describe the details of the spider design. The spider will initially move under a worst-case assumption of slippery tunnel walls, and we also describe a locomotion strategy under this assumption. The spider has been built and is currently undergoing locomotion experiments.