Master Thesis, Tanja Baumann, CVG Prof. Dr. Marc Pollefeys

Chapter 2 Related Work

2.1 Global Obstacle Avoidance

have access to a map of the environment of build a map from the acquired sensor data.

then searched for the optimal path to the goal using a path finding algorithm.

Global obstacle avoidance algorithms

[5] L. Heng, L. Meier, P. Tanskanen, F. Fraundorfer, and M. Pollefeys, “Autonomous obstacle avoidance and maneuvering on a vision-guided MAV using on-board processing," IEEE International Conference on Robotics and Automation (ICRA), pp. 2472{2477, 2011.

• stereo 카메라로 pointcloud 정보를 얻고, 이를 Octomap에 저장함.
• Octomap은 UAV 기체의 미리 결정되어 있는 동작 방식(predefined motion primitives)의 search tree를 계산하는데 활용됨.
• 그 후, An Anytime Dynamic A*(ADA*) 알고리즘을 통해 최적 경로를 찾아냄.

[7] M. Hwangbo, J. Kuner, and T. Kanade, “Ecient Two-phase 3D Motion Planning for Small Fixed-Wing UAVs," IEEE International Conference on Robotics and Automation (ICRA), no. April, pp. 10{14, 2007.

• 주어진 3D 지도에 A* algorithm을 사용하여 고정익 UAV의 첫 탐색 경로를 계산.
• 그 후 local area에서 경로를 개선 시킨 후 미리 계산된 동작 방식으로부터 search tree를 생성.

[8] F. Fraundorfer, L. Heng, D. Honegger, G. H. Lee, P. Tanskanen, and M. Pollefeys, “Vision-Based Autonomous Mapping and Exploration Using a Quadrotor MAV," Intelligent Robots and Systems (IROS), pp. 4557{4564, 2012.

• UAV 기체에 stereo 카메라를 장착.
• loop-closure와 re-localization을 통한 SLAM 기법을 사용.
• 카메라로 부터 얻은 정보와 SLAM을 통해 grond station에서 occupancy map을 생성함.
• Frontier algorithm이 UAV의 새 목표점을 결정하고, 장애물을 탐색하기 위해 Enhanced Vector Field Histogram(VFH+) 알고리즘을 사용함.

[9] A. Mohammadi, “A New Path Planning and Obstacle Avoidance Algorithm in Dynamic Environment," Electrical Engineering (ICEE), vol. 22nd Irani, pp. 1301{1306, 2014.

• 2D 환경에서 수술 바늘의 경로를 찾기 위해 [8]과 유사한 방법 사용.
• hexagonal cells(square보다 부드러운 경로를 만들어줌)로 덮여진 space를 A* 알고리즘을 통해 최적 경로를 찾아냄.

[10] C. Stachniss and W. Burgard, “An integrated approach to goal-directed obstacle avoidance under dynamic constraints for dynamic environments,” IEEE International Conference on Intelligent Robots and Systems (IROS), vol. 1, pp. 508–513, 2002.

• 2D 공간의 지상 로봇의 경로 탐색을 위해 A* 알고리즘을 사용.
• 하위 목표점을 위해 5차원 congiruation space에서 또다른 A* 알고리즘을 사용
• 이는 DWA와 비교되어옴.

[11] O. Brock and O. Khatib, “High-speed navigation using the global dynamic window approach,” IEEE International Conference on Robotics and Automation (ICRA), vol. 1, pp. 341–346, 1999.

Extended Kalman Filters(EKF)

역동적인 scenes에서 떨어져있는 장애물들을 추적하기 위해 사용됨.

[12] A. Ess, B. Leibe, K. Schindler, and L. Van Gool, “Moving obstacle detection in highly dynamic scenes,” IEEE International Conference on Robotics and Automation (ICRA), pp. 56–63, 2009.

• Dynamic programming을 통해 최종 경로를 계산함.

[13] Y. Watanabe, A. Calise, and E. Johnson, “Vision-Based Obstacle Avoidance for UAVs,” AIAA Guidance, Navigation and Control Conference, pp. 1–11, 2007.

• Collision cone을 장애물 주위에 그리고 이를 통해 velocity space의 vectors들을 제한함.

[14] J. Z. Sasiadek and I. Duleba, “3D local trajectory planner for UAV,” Journal of Intelligent and Robotic Systems, vol. 29, no. 2, pp. 191–210, 2000.

• 두 가지 접근법을 사용, 탐색 경로를 계획 한 후 각각의 장애물들을 안전한 거리에서 추적함.

[15] S. Hrabar, “3D path planning and stereo-based obstacle avoidance for rotorcraft UAVs,” IEEE International Conference on Intelligent Robots and Systems (IROS), pp. 807–814, 2008.

• 확률적 기법을 이용하여 search tree를 생성.
• occupancy grid에 확률적 로드맵을 그려, 무작위로 생성된 점 사이에 경로가 존재하면 점을 이음.
• 그리고 이 tree는 D* Lite 알고리즘을 통해 탐색되어, 매 time-step마다 다시 계산하지 않고, 새로운 정보가 들어올 때만 업데이트함.

[16] J. Kuffner and S. LaValle, “RRT-connect: An efficient approach to single-query path planning,” IEEE International Conference on Robotics and Automation (ICRA), vol. 2, pp. 995–1001, 2000.

• 두 개의 random tree를 시작점과 목표점에서 사용함.
• 두 tree가 연결될 때까지 교차하며 확장되어, position과 orientation space를 생성해냄.

2.2 Local Obstacle Avoidance

VFH algorithms

[1] J. Borenstein and Y. Koren, “The Vector Field Histogram - Fast Obstacle Avoidance for Mobile Robots,” IEEE Transactions on Robotics and Automation, vol. 7, no. 3, pp. 278–288, 1991.

• 가장 널리 쓰이는 지역 장애물 회피
• 음파 탐지기로 2D occupancy grid를 생성하고 이를 1D polar 히스토그램으로 바꿈.

[2] I. Ulrich and J. Borenstein, “VFH+: Reliable Obstacle Avoidance for Fast Mobile Robots,” IEEE International Conference on Robotics and Automation (ICRA), pp. 1572 – 1577, 1998.

• VFH를 개선하여 로봇의 최대 회전각과 안전 마진을 고려하는 VFH+를 고안함.
• 이를 바탕으로 여러 적용과 변화를 준 연구들이 진행됨.

[20] K. Song and J. Huang, “Fast optical flow estimation and its application to real-time obstacle avoidance,” IEEE International Conference on Robotics and Automation (ICRA), vol. 3, pp. 2891–2896, 2001.

• 이 논문에서는 optical flow 알고리즘을 polar 히스토그램을 생성하는데 사용하고, 장애물 주변의 약간의 거리를 두는 방식으로 적용함.

[22] B. You, J. Qiu, and D. Li, “A novel obstacle avoidance method for low-cost household mobile robot,” IEEE International Conference on Automation and Logistics, ICAL, pp. 111–116, 2008.

• 이 논문에서 제안한 The Mobile and Static Vector Field Method(MSV)는 연속적인 히스토그램을 바탕으로 동적 장애물의 속도를 추정하여 대응할 수 있도록 함.

이 외에도 여러 연구들이 진행되었으나, 지상 로봇의 2D 환경에서 VFH 알고리즘을 사용하였음.

[26] S. Vanneste, B. Bellekens, and M. Weyn, “3DVFH+: Real-Time ThreeDimensional Obstacle Avoidance Using an Octomap,” MORSE 1st International Workshop on Model-Driven Robot Software Engineering, 2014.

• 이 연구에서는 3D 환경에서의 VFH+알고리즘을 적용함.
• 그러나 주변 환경에 대한 지도를 Octomap을 통해 만들기 때문에, 완전한 local algorithm이라고 하기에 어려움.

이 외에도 머신러닝을 활용한 연구들도 진행됨.

The potential field method

VFH외에도 널리 쓰인 local obstacle avoidance는 포텐셜 필드 기법.

[32] O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,” Autonomous robot vehicles, pp. 500–505, 1985.

• 처음으로 local obstacle avoidance에 포텐셜 필드 기법을 사용한 연구

[33] S. Waydo, “Vehicle motion planning using stream functions,” IEEE International Conference on Robotics and Automation (ICRA), vol. 2, pp. 2484–2491, 2003.

• stream function과 장애물의 속도를 고려하여 2D에서의 포텐셜 필드를 생성함.

[34] T. T. Mac, C. Copot, A. Hernandez, and R. De Keyser, “Improved potential field method for unknown obstacle avoidance using UAV in indoor environment,” IEEE International Symposium on Applied Machine Intelligence and Informatics, pp. 345–350, 2016.

• 실내 환경의 UAV navigation에 포텐셜 필드 기법을 사용함.

이 외에도 여러 방식의 local obstacle avoidance 연구들이 진행됨.

2.3 Impact on this Thesis

장애물 회피에 대해 발표된 모든 연구 중에서 실제 UAV를 대상으로 한 성공적인 테스트는 거의 없음.

성공적이었던 비행 테스트는 MPC 사용한 방법

[18] D. Shim, H. Chung, H. J. Kim, and S. Sastry, “Autonomous Exploration In Unknown Urban Environments For Unmanned Aerial Vehicles,” AIAA Guidance, Navigation, and Control Conference and Exhibit, no. August, pp. 1–8, 2005.

[19] D. H. Shim, H. Chung, and S. S. Sastry, “Conflict-free navigation in unknown urban environments,” IEEE robotics & automation magazine, pp. 27–33, 2006.

Octomap 및 A 알고리즘을 사용한 global approach*

[5] L. Heng, L. Meier, P. Tanskanen, F. Fraundorfer, and M. Pollefeys, “Autonomous obstacle avoidance and maneuvering on a vision-guided MAV using on-board processing,” IEEE International Conference on Robotics and Automation (ICRA), pp. 2472–2477, 2011.

머신 러닝

[30] S. Ross, N. Melik-Barkhudarov, K. S. Shankar, A. Wendel, D. Dey, J. A. Bagnell, and M. Hebert, “Learning monocular reactive UAV control in cluttered natural environments,” IEEE International Conference on Robotics and Automation (ICRA), pp. 1765–1772, 2013.

[31] D. Dey, K. S. Shankar, S. Zeng, R. Mehta, M. T. Agcayazi, C. Eriksen, S. Daftry, M. Hebert, and J. A. Bagnell, “Vision and learning for deliberative monocular cluttered flight,” Field and Service Robotics, vol. 113, pp. 391–409, 2016.

Potential field methods

[34] T. T. Mac, C. Copot, A. Hernandez, and R. De Keyser, “Improved potential field method for unknown obstacle avoidance using UAV in indoor environment,” IEEE International Symposium on Applied Machine Intelligence and Informatics, pp. 345–350, 2016.

에서 수행되었으나, 대부분의 local approaches들은 2D 환경에서만 적용하도록 설계됨.

히스토그램 방식에 대한 연구는 상당히 많이 진행되어 왔지만, 아직 3차원의 UAV에 적용되지는 못했고, 3DVFH+ 알고리즘은 시뮬레이션으로만 테스트됨.

이 논문의 목표는 VFH* 알고리즘을 3DVFH 알고리즘과 결합하고 추가 기능으로 확장하여 신뢰할 수 있는 장애물 회피 동작으로 원활한 UAV 비행을 달성하는 것.

Chapter 3 Approach

3.1 The 3DVFH Algorithm

3DVFH는 global map을 Octomap을 이용하여 생성하고, 이를 통한 bounding box가 히스토그램 기반 장애물 회피에 사용됨.

따라서 이러한 방식은 global과 local approaches의 중간 지점에 있는 방식이라고 할 수 있으며, 기체의 FOV에 벗어나도 이전 장애물들을 기억하고 있다는 큰 장점이 있으면서도, 큰 computational overhead가 소요됨.

이 논문에서는 3DVFH 방법을 global map을 생성하지 않고 순수하게 local algorithm으로 사용함. 이 global map은 stereo 카메라에서 들어오는 3D pointcloud로 대체되며, 훨씬 비용적으로 적은 memory 전략을 통해 local approach의 한계를 해결하고자 함.

The Histogram and Cost function

전처리된 pointcloud에서 얻은 모든 3D point들은 UAV 위치에서의 방위각과 고도각으로 계산되고, 이 점들을 해당하는 히스토그램에 위치시킴.

각 cell들은 각각의 구역에 해당하는 3D point들의 갯수를 가지게 됨. 또한, 드론 기체가 회전 가능하고 천천히 비행하는 것을 가정하여, 최소 회전반경은 고려되지 않음.

그 후, 각 cell에 있는 점들을 계산하고 임계값을 통해 binary polar histogram으로 변환시킴. UAV 기체의 크기와 장애물의 최소 거리를 고려하기 위해, occupied cells 주변에 안전 마진을 두어 막힌 cell로 처리함.

이 histogram의 모든 free cell을 가지고 cost function이 계산됨. 이 cost function은 goal orientation term과 smoothing term으로 구성됨. goal orientation은 목표 방향과 계산된 방향을 비교하고, smoothing term은 이전 time-step의 방향과 계산된 방향을 비교함. Cost function을 통해 가장 낮은 cost를 가지는 경로가 선정되어 움직임.

histogram에 아무 장애물도 없는 경우에는 UAV 기체가 빠르게 이동할 수 있으며, 바로 목표점으로 향하도록 하여 computational time을 줄이도록 함.

3.3 Adaptions for Safety and Corner Cases

to be conitnued

3.2 Building a Memory for 3DVFH

위와 같은 3DVFH 알고리즘은 현재 time-step이며, 드론 기체와 가까운 정보만 접근가능하다. 그렇기에, 이전의 정보나 action은 고려하지 않아 불안정한 행동이나 local minima에 빠질 수 있다.

특히 벽과 같은 큰 장애물을 비행할 때는 이러한 local VFH 방식을 사용하는 것은 불가능하다.

그래서 큰 dataset없이 이전 장애물들을 기억할 수 있는 memory를 포함하도록 하여 알고리즘을 개선시켰다.

1. 이전 히스토그램의 정보를 3D point로 투사시킨다. (Re-projection of Histogram into 3D Points)
2. re-projected된 점들을 0.5배의 resolution으로 memory 히스토그램을 만들고, 이후 up-samped된다. (Building a Histogram from 3D Points)
3. 새 depth 정보로 현재 시점의 히스토그램을 계산한다.
4. 새로운 히스토그램과 memory 히스토그램을 혼합하여 현재 시점의 히스토그램을 만든다. (Combining Memory Histogram and New Histogram)

Memory 히스토그램과 새 히스토그램을 합쳐 만든 히스토그램을 가지고 navigation을 하며, 다음 계산을 위해 다시 저장한다. 새 히스토그램의 binary layer(bin)은 적어도 하나의 3D point만 cell 안에 있어도 occupied cell로 계산된다. Distance layer(dist)는 cell 안에 있는 점들의 평균 거리값으로 채워진다. 새 히스토그램은 새로운 정보로 생성되었으므로 Age layer의 값은 항상 0이다.

Memory 히스토그램은 절반의 resolution으로 줄여진 후 다시 up-sampled되는데, 이 때 binary layer를 형성하기 위한 임계값은 매우 중요하다.(이 논문은 6개를 제시함.) 이 임계값이 너무 작은 경우, 원래의 old 히스토그램보다 memory 히스토그램의 occupied cell이 더 많아질 수 있으며, 임계값이 너무 큰 경우에는 memory 히스토그램의 occupied 셀로 이전 old 히스토그램보다 적은 occupied cell을 가지게 된다. 이렇게 되면 memory 효과가 거의 사라지고 장애물 주변부(point가 비교적 적을 것이므로)가 고려되지 않게 된다.

2개의 히스토그램을 합치기 위해서는 현재의 FOV 안에 있는 cell들과 바깥 쪽에 있는 cell들을 구분해야 한다. 예를 들어, Realsense 카메라는 수직 FOV가 46$\degree$이고, 수평 FOV가 59$\degree$이기 때문에 새 히스토그램은 FOV 바깥 쪽에 있는 occupied cell을 가지게 될 수도 있다.

그림 3.5처럼 FOV 안쪽의 cell은 새 히스토그램을 복제하고, FOV 바깥쪽은 OR 연산으로 binary layer을 계산한다. 이 binary layer를 바탕으로 occupied cell에 해당하는 distance와 age 값을 가져온다.

Chapter 4 Results

4.1 Experimental Setup

ROS와 PX4 프레임워크를 이용하여 테스트함. 노드들은 아래와 같이 구성

• Camera Node
• Stereo Processing Node(in simulation oly)
• UAV Node(=Mavros)
• Local Planner Node

시뮬레이션은 Gazebo를 이용하여 3DR Iris 쿼드콥터로 기체를 사용. stereo 이미지를 depth 맵으로 바꿔주는 별도의 노드를 사용함.

실외 테스트는 Intel Aero Ready to Fly 드론을 사용하고, Intel Realsense R200 카메라를 사용함.

로컬 플래너 노드는 다음과 같이 구성됨.

Mavros노드와 3D pointcloud로 기체의 상태정보를 받음. 플래너 알고리즘으로 다음 setpoints를 계산하고 이를 mavros노드를 통해 PX4 Autopilot으로 보냄.

setpoints는 최소 2Hz 주기로 publish되어 off-board 모드를 유지하도록 함. search tree의 사이즈에 따라 알고리즘 계산시간이 통신 주기를 맞추기에 충분하지 않은 경우가 발생하고, 카메라가 pointcloud를 빠르게 publish하는데 실패하기도 함. 이런 경우에 Autopilot은 드론을 다시 position mode로 전환함.