We suggest a computationally efficient online local motion planning algorithm for mobile robots in unknown cluttered dynamic environments. The algorithm plans a trajectory incrementally up to the finite horizon in state-time space. We systematize bidirectional trajectory planning with three kinds of trajectories: a forward trajectory from the current robot state, a backward trajectory from the state of current target waypoint, and a connecting trajectory between the forward and backward trajectories. Since it is computationally complex to plan a trajectory minimizing given cost-to-go in state-time space, we adopt two simplifying approaches: First, we decompose a cost-to-go function into several parts and we minimize the more dominant part first. Second, we use approximated reachable timed configuration or state region with uniform input. Moreover, for the computational efficiency, we check future collisions in configuration-time space instead of checking inevitable collision state (ICS) in state-time space in order to predict future collisions in advance. When the incrementally planned trajectory is fallen in ICS, we perform the partial trajectory modification scheme using interim goal (a temporary goal for the robot to pass through at the expected collision time in order to avoid the collision), which enables the robot to cope with cluttered dynamic environments. Additionally, we suggest an online path refinement method which refines the given path into shortest path based on visible space with little effort. Performances of the proposed algorithm are validated through extensive simulations and experiment with two types of mobile robots: a holonomic mobile robot and a differential drive mobile robot.
In this dissertation, online local motion planning for mobile robots in unknown cluttered dynamic environments is configured as three sub-problms.
First, We investigate a timed state or configuration space which is the state or configuration space at a given time of state-time space. In the timed state or configuration space, we define two important concepts, reachable region and safe region. Reachable region is the part of timed state or configuration space bounded by motion constraint. Safe region is the region limited by obstacle constraint as well as motion constraint. And we suggest the way how to determine a timed state in a timed state (or configuration) space which is the state sapce at a certain time in state-time space with given motion and obstacle constraints.
Second, we suggest an approach how to avoid obstacles in dynamic cluttered environments based on state-time space. In spite of the small computaional load, suggested method copes with cluttered dynamic environments avoiding ICS using the partial trajectory modification scheme.
Third, we suggest an approach how to minimize cost-to-go near waypoints and goal. To pass through given waypoints and arrive at the goal effectively, we adopt the bidirectional trajectory planning which plans three trajectories: forward trajectory from the robot state and backward trajectory from the current target waypoint that forward trajectory is heading to pass through, and connection trajectory between forward and backward trajectories.
Fourth, we suggest an approach how to refine the waypoint path online. A local waypoint path from the robot to a local goal on global waypoint path is planned to follow the global waypoint path without falling in local minima or any collision with sensed obstacles.
The last one is included in further work.
복잡한 동적 환경에서 모바일 로봇을 위한 계산 효율적인 온라인 로컬 모션 계획 알고리즘을 제안합니다. 이 알고리즘은 시공간적 공간에서 끝까지 궤도를 점진적으로 계획합니다. 현재 로봇 상태로부터의 순방향 궤적, 현재 목표 웨이 포인트의 상태로부터의 역방향 궤적, 및 순방향 및 역방향 궤적 간의 연결 궤적의 3 가지 궤적을 가진 양방향 궤적 계획을 체계화한다. 국가 - 시간 공간에서 주어진 비용을 최소화하는 궤적을 계획하는 것이 계산 상으로 복잡하기 때문에, 우리는 두 가지 단순화 된 접근법을 채택합니다 : 첫째, 비용 - 이동 함수를 여러 부분으로 분해하고보다 지배적 인 부분을 최소화합니다 . 두 번째로, 우리는 근접한 도달 가능한 시간 설정 또는 상태 입력을 가진 상태 영역을 사용한다. 또한, 계산 효율면에서 미래의 충돌을 사전에 예측하기 위해 상태 - 시간 공간에서 필연적 인 충돌 상태 (ICS)를 확인하는 대신 구성 시간 공간에서 미래의 충돌을 검사한다. 점진적으로 계획된 궤적이 ICS에서 떨어지면 중간 목표 (충돌을 피하기 위해 로봇이 예상되는 충돌 시간에 통과하는 임시 목표)를 사용하여 부분 궤도 수정 방법을 수행하여 로봇이 혼란스러운 동적 환경. 또한, 주어진 경로를 거의 보이는 공간을 기반으로 최단 경로로 재정의하는 온라인 경로 갱신 방법을 제안한다. 제안 된 알고리즘의 성능은 두 가지 유형의 이동 로봇 (holonomic 이동 로봇과 이중 구동 이동 로봇)을 사용하여 광범위한 시뮬레이션과 실험을 통해 검증된다.
본 논문에서는 잘 알려지지 않은 복잡한 동적 환경에서 모바일 로봇을 위한 온라인 로컬 모션 계획을 세 가지 세부 계획으로 구성했다.
첫째, 시간 - 상태 공간의 주어진 시간에 상태 또는 구성 공간 인 시간 지정된 상태 또는 구성 공간을 조사한다. Timed 상태 또는 구성 공간에서, 우리는 도달 가능한 영역과 안전한 영역이라는 두 가지 중요한 개념을 정의합니다. 도달 가능 영역은 동작 제한으로 경계 지어진 시간 영역 또는 구성 공간의 일부입니다. 안전 영역은 장애 제한 및 모션 제약으로 인해 제한되는 영역입니다. 그리고 우리는 주어진 모션과 장애물 제한이있는 상태 - 시간 공간에서 특정 시간에 상태 저장 (state space) 인 시간이 있는 상태 (또는 구성) 공간에서 시간 상태를 결정하는 방법을 제안한다.
둘째, 우리는 국가 시간 공간에 기초한 역동적 인 어수선한 환경에서 장애물을 피하는 방법을 제시한다. 제안 된 방법은 계산량이 적음에도 불구하고 부분 궤적 수정 기법을 사용하여 ICS를 피하면서 복잡한 동적 환경에 대처한다.
셋째, 경유지 근처의 경비를 최소화하는 방법을 제안합니다. 주어진 웨이 포인트를 통과하고 목표에 효과적으로 도달하기 위해 로봇 상태에서의 순방향 궤적과 순방향 궤도가 통과하려는 현재 목표 웨이 포인트에서의 역방향 궤도와 연결 궤적의 3 가지 궤도를 계획하는 양방향 궤도 계획을 채택합니다.
넷째, 웨이 포인트 경로를 온라인으로 재구성하는 방법을 제안합니다. 로봇에서 글로벌 웨이 포인트 경로의 로컬 목표까지의 로컬 웨이 포인트 경로는 로컬 최소 점 또는 감지 된 장애물과의 충돌없이 글로벌 웨이 포인트 경로를 따라 계획됩니다.
