In a graph search algorithm, a given environment is represented as a graph comprising a set of feasible system configurations and their neighboring connections. A path is generated by connecting the initial and goal configurations through graph exploration, whereby the path is often desired to be optimal or suboptimal. The computational performance of the optimal path generation depends on the avoidance of unnecessary explorations. Accordingly, heuristic functions have been widely adopted to guide the exploration efficiently by providing estimated costs to the goal configurations. The exploration is efficient when the heuristic functions estimate the optimal cost closely, which remains challenging because it requires a comprehensive understanding of the environment. However, this challenge presents the scope to improve the computational efficiency over the existing methods. Herein, we propose reinforcement learning heuristic A* (RLHA*), which adopts an artificial neural network as a learning heuristic function to closely estimate the optimal cost, while achieving a bounded suboptimal path. Instead of being trained by precomputed paths, the learning heuristic function keeps improving by using self-generated paths. Numerous simulations were performed to demonstrate the consistent and robust performance of RLHA* by comparing it with the existing methods.

Wheelchairs are among the most important equipment in terms of facilitating the lives of people with walking disabilities. In particular, the use of electric wheelchairs allows people with walking disabilities to move comfortably without excessively straining their bodies. However, in some cases, a person with a walking disability who uses an electric wheelchair may have difficulties in driving the wheelchair or may experience unintended collisions due to obstacles that are not within the line of sight. In order to prevent such negative events, it is necessary to develop a wheelchair with electric wheels that is produced at a minimum cost, can be easily sold to all kinds of people with disabilities, and will not be difficult to use. In addition, this equipment must include a system designed to provide wheelchair control and driving comfort with maximum efficiency for areas outside of the line of sight, which is one of the features required by all people with walking disabilities. This article explains the design of a prototype that can detect blind spots thanks to sensors and provide driving comfort while a wheelchair driver with walking disabilities uses it. In this paper, it is aimed to create a smart electric wheelchair that can be used by anyone with a walking disability while keeping the costs to a minimum.

In this paper, we proposed a novel path replanning algorithm on arbitrary graphs. To avoid computationally heavy preprocessing and to reduce required memory to store the expanded vertices of the previous search, we defined the feature vertices, which are extracted from the previous path by a simple algorithm to compare the costs between adjacent vertices along the path once. Proper additional heuristic functions are designed for these feature vertices to work as local attractors guiding the search toward the previous path’s neighbors. To avoid unnecessary expansions and speed up the search, these additional heuristic functions are properly managed to stop intriguing or guiding search toward the feature vertices. The proposed algorithm of Fast Replanning Multi-Heuristic A* is a variation of Shared Multi-Heuristic A* while removing or deactivating the additional heuristic functions during the search. Fast Replanning Multi-Heuristic A* guarantees the bounded suboptimality while efficiently exploring the graph toward the goal vertex. The performance of the proposed algorithm was compared with weighted A* and D* lite by simulating numerous path replanning problems in maze-like maps.

In this paper, we consider the path planning problem on a graph. To reduce computation load by efficiently exploring the graph, we model the heuristic function as a neural network, which is trained by a training set derived from optimal paths to estimate the optimal cost between a pair of vertices on the graph. As such heuristic function cannot be proved to be an admissible heuristic to guarantee the global optimality of the path, we adapt an admissible heuristic function for the terminating criteria. Thus, proposed Learning Heuristic A* (LHA*) guarantees the bounded suboptimality of the path. The performance of LHA* was demonstrated by simulations in a maze-like map and compared with the performance of weighted A* with the same suboptimality bound.

In this paper, we solve the path planning problem for a tethered mobile robot, which is connected to a fixed base by a cable of length L. The reachable space of the robot is restricted by the length of the cable and obstacles. The reachable space of the tethered robot can be computed by considering the topology class of the cable. However, it is computationally too expensive to compute this space a-priori. Instead, in this paper, we show how we can plan using a recently-developed variant of A* search, called Multi-Heuristic A*. Normally, the Multi-Heuristic A* algorithm takes in a fixed set of heuristic functions. In our problem, however, the heuristics represent length of paths to the goal along different topology classes, and there can be too many of them and not all the topology classes are useful. To deal with this, we adapt Multi-Heuristic A* to work with a dynamically generated set of heuristic functions. It starts out as a normal weighted A*. Whenever the search gets trapped in a local minimum, we find the proper topology class of the path to escape from it and add the corresponding new heuristic function into the set of heuristic functions considered by the search. We present experimental analysis comparing our approach with weighted A* on planning for a tethered robot in simulation.

In this paper we investigate the problem of navigation for a planar mobile robot tethered to a base by a flexible cable of length L. Obstacles present in the environment, coupled with the cable length constraint, makes the problem highly non-trivial. We adopt a topological approach along with graph search-based techniques to solve this problem, wherein we use the notion of a homotopy augmented graph to capture the information about the homotopy class of the cable. This lets us plan traversable optimal trajectories from an initial robot position and cable configuration to a final position of the robot. We demonstrate the algorithm by planning trajectories in several cluttered environments and with different cable lengths. As a demonstration of practical applicability, using a dynamic simulation testbed we simulate a robot-cable system following a planned trajectory.

We present the mathematical framework and algorithms for multi-robot topological exploration of unknown environments in which the main goal is to identify the different topological classes of trajectories and thus efficiently distribute the task of exploration among different groups of robots. We consider two-dimensional configuration spaces. At any point in time, the robots' map consists of known, partially-mapped obstacles. The unknown, yet-to-be-explored area is mapped to a single point, thus giving us a quotient space. The topological classes on the quotient space allows us to define topological classes of trajectories connecting a robot pose to the unknown region in the original configuration space. Robots explore this configuration space choosing different homology classes when confronted by obstacles or walls. We illustrate the basic idea with simulations of small teams of robots. Experiments with a single robot illustrate the applicability of the method to robots that have small sensor footprints and limited computational resources. We also provide comparisons with a standard frontier-based algorithm.

We address the problem of synthesizing planar, bimanual, whole-arm grasps by developing the abstraction of an open chain gripper, an open, planar chain of rigid links and revolute joints contacting a planar, polygonal object, and introducing the concept of a generalized contact. Since two generalized contacts suffice for planar grasps, we leverage previous work on caging and immobilization for two contact grasps to construct an algorithm which synthesizes contact configurations for stable grasping. Simulations show that our methodology can be applied to grasp a wide range of planar objects without relying on special-purpose end-effectors. Representative experiments with the PR2 humanoid robot illustrate that this approach is practical.