Robots are inherently limited by physical constraints on their link lengths, motor torques, battery power and structural rigidity. To thrive in circumstances that push these limits, such as in search and rescue scenarios, intelligent agents can use the available objects in their environment as tools. Reasoning about arbitrary objects and how they can be placed together to create useful structures such as ramps, bridges or simple machines is critical to push beyond one's physical limitations. Unfortunately, the solution space is combinatorial in the number of available objects and the configuration space of the chosen objects and the robot that uses the structure is high dimensional. To address these challenges, we propose using constraint satisfaction as a means to test the feasibility of candidate structures and adopt search algorithms in the classical planning literature to find sufficient designs. The key idea is that the interactions between the components of a structure can be encoded as equality and inequality constraints on the configuration spaces of the respective objects. Furthermore, constraints that are induced by a broadly defined action, such as placing an object on another, can be grouped together using logical representations such as Planning Domain Definition Language (PDDL). Then, a classical planning search algorithm can reason about which set of constraints to impose on the available objects, iteratively creating a structure that satisfies the task goals and the robot constraints. To demonstrate the effectiveness of this framework, we present both simulation and real robot results with static structures such as ramps, bridges and stairs, and quasi-static structures such as lever-fulcrum simple machines.

Robot actuators have physical limitations in how fast they can change their velocity. The more accurately planning algorithms consider these limitations, the better the robot is able to perform. Sampling-based algorithms have been successful in geometric domains, which ignore actuator limitations. They are simple, parameter-free, probabilistically complete and fast. Even though some algorithms like RRTs were specifically designed for kinodynamic problems, which take actuator limitations into account, they are less efficient in these domains or are, as we show, not probabilistically complete. A common approach to this problem is to decompose it, first planning a geometric path and then time-parameterizing it such that actuator constraints are satisfied. We improve the reliability of the latter step. However, the decomposition approach can neither deal with non-zero start or goal velocities nor provides an optimal solution. We demonstrate that sampling-based algorithms can be extended to consider actuator limitations in the form of acceleration limits while retaining the same advantageous properties as in geometric domains. We present an asymptotically optimal planner by combining a steering method with the RRT* algorithm. In addition, we present hierarchical rejection sampling to improve the efficiency of informed kinodynamic planning in high-dimensional spaces.

Kinodynamic motion planning is an important problem in robotics. It consists of planning the dynamic motion of a robotic system taking into account its kinematic and dynamic constraints. For this class of problems, high dimensionality is a major difficulty and finding an exact time optimal robot motion trajectory is proven to be NP-hard. Probabilistic approximate techniques have therefore been proposed in the literature to solve particular problem instances. These methods include Randomized Potential Field Planners (RPP), Probabilistic Roadmaps (PRM) and Rapidly Exploring Random Trees (RRT). When physical obstacles and differential constraints are added to the problem, applying RPPs or PRMs encounter difficulties. In order to handle these difficulties, RRTs have been proposed. In this study, we consider a multiple camera industrial inspection problem where the concurrent motion of these cameras needs to be planned. The cameras are required to capture maximum number of defect locations while globally avoiding collisions with each other and with obstacles. Our approach is to consider a solution to the kinodynamic planning problem of multiple camera inspection by making use of the RRT algorithm. We explore and resolve issues arising when RRTs are applied to this specific problem class. Along these lines, we consider the cases of a single camera without obstacles and then with obstacles. Then, we attempt to extend the study to the case of multiple camera where we also need to avoid collisions between cameras. We present simulation results to show the performance of our RRT based approach to different instrument configurations and compare with existing deterministic approaches.