We address a path planning problem for heterogeneous multi-robot systems under specifications consisting of temporal constraints and routing tasks such as package delivery services. The robots are partitioned into several groups based on their dynamics and specifications. We introduce a concise description of such tasks, called a work, and extend counting LTL to represent such specifications. We convert the problem into an ILP problem. We show that the number of variables in the ILP problem is fewer than that of the existing method using cLTL+. By simulation, we show that the computation time of the proposed method is faster than that of the existing method.

This letter proposes a post-processing method to improve the smoothness and safety of the path for an autonomous vehicle navigating in an urban environment. The proposed method transforms the initial path given by local path planning algorithms using a stochastic approach to improve its smoothness and safety. Using the proposed method, the initial path is efficiently transformed by iteratively updating the position of each waypoint within it. The proposed method also guarantees the feasibility of the transformed path. Experimental results verify that the proposed method can improve the smoothness and safety of the initial path and ensure the feasibility of the transformed path.

We investigate an online problem of a robot exploring the outer boundary of an unknown simple polygon P. The robot starts from a specified vertex s and walks an exploration tour outside P. It has to see all points of the polygon's outer boundary and to return to the start. We provide lower and upper bounds on the ratio of the distance traveled by the robot in comparison to the length of the shortest path. We consider P in two scenarios: convex polygon and concave polygon. For the first scenario, we prove a lower bound of 5 and propose a 23.78-competitive strategy. For the second scenario, we prove a lower bound of 5.03 and propose a 26.5-competitive strategy.

Path planning and motion control are fundamental components to realize safe and reliable autonomous driving. The discrimination of the role of these two components, however, is somewhat obscure because of strong mathematical interaction between these two components. This often results in a redundant computation in the implementation. One of attracting idea to overcome this redundancy is a simultaneous path planning and motion control (SPPMC) based on a model predictive control framework. SPPMC finds the optimal control input considering not only the vehicle dynamics but also the various constraints which reflect the physical limitations, safety constraints and so on to achieve the goal of a given behavior. In driving in the real traffic environment, decision making has also strong interaction with planning and control. This is much more emphasized in the case that several tasks are switched in some context to realize higher-level tasks. This paper presents a basic idea to integrate decision making, path planning and motion control which is able to be executed in realtime. In particular, lane-changing behavior together with the decision of its initiation is selected as the target task. The proposed idea is based on the nonlinear model predictive control and appropriate switching of the cost function and constraints in it. As the result, the decision of the initiation, planning, and control of the lane-changing behavior are achieved by solving a single optimization problem under several constraints such as safety. The validity of the proposed method is tested by using a vehicle simulator.

This article presents efficient strategies for evacuating from an unknown affected area in a plane. Evacuation is the process of movement away from a threat or hazard such as natural disasters. Consider that one or n(n ≥ 3) agents are lost in an unknown convex region P. The agents know neither the boundary information of P nor their positions. We seek competitive strategies that can evacuate the agent from P as quickly as possible. The performance of the strategy is measured by a competitive ratio of the evacuation path over the shortest path. We give a 13.812-competitive spiral strategy for one agent, and prove that it is optimal among all monotone and periodic strategies by showing a matching lower bound. Also, we give a new competitive strategy EES for n(n ≥ 3) agents and adjust it to be more efficient with the analysis of its performance.

This paper proposes a novel practical path planning framework for autonomous parking in cluttered environments with narrow passages. The proposed global path planning method is based on an improved Fast Marching algorithm to generate a path while considering the moving forward and backward maneuver. In addition, the Support Vector Machine is utilized to provide the maximum clearance from obstacles considering the vehicle dynamics to provide a safe and feasible path. The algorithm considers the most critical points in the map and the complexity of the algorithm is not affected by the shape of the obstacles. We also propose an autonomous parking scheme for different parking situation. The method is implemented on autonomous vehicle platform and validated in the real environment with narrow passages.

We propose a practical local and global path-planning algorithm for an autonomous vehicle or a car-like robot in an unknown semi-structured (or unstructured) environment, where obstacles are detected online by the vehicle's sensors. The algorithm utilizes a probabilistic method based on particle filters to estimate the dynamic obstacles' locations, a support vector machine to provide the critical points and Bezier curves to smooth the generated path. The generated path safely travels through various static and moving obstacles and satisfies the vehicle's movement constraints. The algorithm is implemented and verified on simulation software. Simulation results demonstrate the effectiveness of the proposed method in complicated scenarios that posit the existence of multi moving objects.

The wireless robotic sensor network (WRSN) is a combination of a mobile robot and wireless sensor networks. In WRSN, robots perform high-level missions such as human rescue, exploration in dangerous areas, and maintenance and repair of unmanned networks in cooperation with surrounding sensor nodes. In such a network, robots should move to the accident site as soon as possible. This paper proposes a distance-aware robot routing (DAR) algorithm, which focuses on how to pick the shortest path for the mobile robot by considering characteristics different from packet routing. Simulations are performed to demonstrate the benefits of using the proposed algorithm.

High-speed collision detection is important to realize a highly-safe intelligent vehicle. In collision detection, high-computational power is required to perform matching operation between discrete points on surfaces of a vehicle and obstacles in real-world environment. To achieve the highest performance, a hierarchical matching scheme is proposed based on two representations: the coarse representation and the fine representation. A vehicle is represented as a set of rectangular solids in the fine representation (fine rectangular solids), and the coarse representation, which is also a set of rectangular solids, is produced by enlarging the fine representation. If collision occurs between an obstacle discrete point and a rectangular solid in the coarse representation (coarse rectangular solid), then it is sufficient to check the only fine rectangular solids contained in the coarse one. Consequently, checks for the other fine rectangular solids can be omitted. To perform the hierarchical matching operation in parallel, a hierarchically-content-addressable memory (HCAM) is proposed. Since there is no need to perform matching operation in parallel with fine rectangular solids contained in different coarse ones, the fine ones are mapped onto a matching unit. As a result, the number of matching units can be reduced without decreasing the performance. Under the condition of the same execution time, the area of the HCAM is reduced to 46.4% in comparison with that of the conventional CAM in which the hierarchical matching scheme is not used.

This paper proposes genetic algorithms (GAs) for path planning and trajectory planning of an autonomous mobile robot. Our GA-based approach has an advantage of adaptivity such that the GAs work even if an environment is time-varying or unknown. Therefore, it is suitable for both off-line and on-line motion planning. We first presents a GA for path planning in a 2D terrain. Simulation results on the performance and adaptivity of the GA on randomly generated terrains are shown. Then, we discuss an extension of the GA for solving both path planning and trajectory planning simultaneously.