第 8 回 会津大学ロボットシンポジウム

Enhanced Path Planning Methodfor Autonomous Service Robot

Raihan Kabir and Yutaka Watanobe

raihan.kabir.cse@gmail.com, yutaka@u-aizu.ac.jp
The 8th University of Aizu Robot Symposium

1

Table of Contents:• Background study and Objective of this Research• Proposed approach for the enhancement in Robotic Path Planning• ArUco Marker based Service Point Searching• Dynamic path adjustment• Conclusion• Reference

The 8th University of Aizu Robot Symposium2

Background study and Objective of this Research• An autonomous robotic wheelchair is a type of mobile robotthat is designed to help people with disabilities or mobility
impairments to move around independently.
• Features of autonomous robotic wheelchairs:• Navigation• Vision system to avoid obstacles• Control, management and Safety• Accessibility• Independence

RoboticWheelchair▪ Our Research focus is in the area of robot Navigation, Vision, Control, andmanagement system to automate the robotic wheelchair that can moveautonomously with some simple commands.
The 8th University of Aizu Robot Symposium3RoboticWheelchair

Robot Navigation

A* path planning algorithm

Performance enhancement
using proposedRobot motion block

Publications: (Major conference)• Raihan Kabir, Yutaka Watanobe, Keitaro Naruse, Rashedul Islam, (2022), " Effectiveness of Robot Motion Block on A-star
Algorithm for Robotic Path Planning " In: SoMet-2022, pp: 85-96. DOI: 10.3233/FAIA220241
The 8th University of Aizu Robot Symposium

4Proposed Method
To achieve the research goal, the general block diagram of our proposed model is:

The 8th University of Aizu Robot Symposium5

A* path planning algorithm with proposed robot motion block• A* is one of the famous path searching and graph traversal algorithm for its optimality, completeness,and optimal efficiency.
• It is an updated version of best-first search or informed search algorithm.

• The strategy is to search in a weighted graph to find the given goal node by taking a consistentheuristic function h(s) as input that uses Euclidean distance 𝑑 𝑝, 𝑞 = (𝑞1 − 𝑝1 )2 +(𝑞2 − 𝑝2 )2 .
• It calculate the cost for each nodes 𝐶𝑜𝑠𝑡(𝐶) = 𝑚𝑖𝑛 𝑠𝑒𝑎𝑟𝑐ℎ𝑒𝑑 − 𝑙𝑖𝑠𝑡, ℎ 𝑆goal , 𝑠𝑒𝑎𝑟𝑐ℎ𝑒𝑑 − 𝑙𝑖𝑠𝑡

The 8th University of Aizu Robot Symposium

6Proposed robot motion block:• In a grid-based search, a robot needs to search its surrounding
neighbor cells optimally so that it can find the goal node bychecking less amount of grid cells.
• For searching the neighbor nodes, it uses a block of cell nodes
which is called a robot motion block or motion kernel.
• The first, second, and third columns represent the x-axis, y-axis,
and the costs of the particular points in 2D grid space.

𝑛0−𝑛0𝑚𝑜𝑡𝑖𝑜𝑛 = −𝑛0𝑛0−𝑛−𝑛

𝐶 𝑛
𝐶 𝑛
𝐶 𝑛
𝐶 𝑛
𝐶 𝑛∗2−𝑛𝑛𝐶𝑛∗2𝑛−𝑛𝐶𝑛∗2𝑛𝑛𝐶𝑛∗2

Here, 𝑛 = 1, 2, 3, … , 𝑁
𝐶 = movement cost
towards the neighborcells.

▪ In the proposed robot motion block matrix,n represents the distance between therobot and the searching cells.

…

▪ The proposed motion block has eightneighbor cell nodes surrounding the robot.
𝑛=1
The 8th University of Aizu Robot Symposium

𝑛=2

𝑛=37

Grid-map preparation using the dataset: (Dataset)▪ The dataset contains eight types of grid maps which arerepresented as PNG format images. But for the experiment,
we need a matrix of grid maps.
▪ Dataset images have no border, which is essential so thatthe robot cannot escape from the grid map.

(a1)

(b1)

(c1)

(a2)

(b2)

(c2)

▪ Each type of planning map environment contains 1,000

images, and the resolution of the images is 201*201.

bugtrap_forest

forestmaze

Pre-processed dataset
The 8th University of Aizu Robot Symposium

Sample map images of the dataset (a1,a2)
bugtrap_forest, (b1,b2) forest, and (c1,c2)
mazes.
Raw dataset8• The proposed model is experimented with different robot motion blocks (n = 1 to 6) for three types ofmaps.
• When the robot motion block size n increases, the number of searched cells drastically decreases.
• At the same time, the path costs increased a little, but it’s negligible.
Motionblock’s size: 𝑛 = 1

𝑛=2

𝑛=3

𝑛=4

The 8th University of Aizu Robot Symposium

𝑛=5𝑛=69

Experimental Outcomes: (cont.)• Compared to the conventional method the experimental results shows a 92 % to 99 % reduction
for time complexity.

• 63 % to 93 % reduction for the number of searched nodes compared to the conventional method.
• The path costs increased a little 0.2 % to 12 %.
Map type
bugtrap_forest

forestmazes

Robot motion block

n=1

n=2

n=3

n=4

n=5

n=6

Cell searched
Path cost

22011
261

6528
262

4473
264

2596
292

1760
290

1422
294

Time needed (s)

4.640

0.359

0.109

0.046

0.015

0.009

Cell searched

14596

904

639

524

517

448

Path cost

323

326

328

329

334

333

Time needed (s)

3.968

0.047

0.023

0.009

0.008

0.002

Cell searched

20950

7736

5355

3852

3275

2604

Path cost

377378376

384385390

Time needed (s)

2.140

0.234

0.093

0.031

0.030

0.015

The 8th University of Aizu Robot Symposium

10Experimental Outcomes: (cont.)

Number of searched nodes

Time needed for searching the goal

Number of nodes for path cost

The 8th University of Aizu Robot Symposium

11

Robotic
Wheelchair

Robot Navigation

Enhanched A* path planning algorithm

ArUco Marker based Service
Point Searching

dynamicpath
adjustment

Publications: (Major conference)•Kabir, Raihan, Yutaka Watanobe, Md Rashedul Islam, Keitaro Naruse, (2022), "Service Point Searching for Disabled People using Wheelchair based
Robotic Path Planning and ArUco Markers" In: IEEE 8th World Forum on Internet of Things (WF-IoT-2022), Yokohama, Japan.
The 8th University of Aizu Robot Symposium

12Research objective
Robot• Moving towards to the service point movableobstacles rises a problem of a collision.
• Dynamic path adjustment can be a solve of thatproblem.
• There are several object detection methods but
those are highly computational systems.

Obstacle• On the other hand, ArUco marker can bedetected without any computational overhead.
(light, detection in any direction, and axis ofthe marker)

Servicepoint

The 8th University of Aizu Robot Symposium

13

Proposed Method:
To achieve the research goal, the general block diagram of our proposed model is:

The 8th University of Aizu Robot Symposium

14Indoor Grid-map preparation:▪ To test the improved A* algorithm and other partsof the proposed model, a grid map of an indoor
environment is prepared and had a dimension of
792 × 635.
▪ In this map, the number of obstacle cells was130,743 among the total number of cells(502,920).

Sample indoor grid map of an elderly care center.
where black pixels = obstacles, white pixels = free space, greenpixels = start, and blue pixels = goal.
The 8th University of Aizu Robot Symposium

15Service points in an indoor environment:

Service point nameColor

Service point namePush Button
No.

Color

Push ButtonNo.

• Different colored push button for different Service points in an indoor environment to go to desired place.

1

Help_deskG

5

LaundryY

2

Vending_machineO

6CommodeP

3

Cofee_machine

R

7

Post_box

W

4

BedBThe 8th University of Aizu Robot Symposium

16Path planning using improved A* algorithm:• Compared to the conventional method the experimental results show around an 89% reduction intime complexity.
• 55 % to 65 % reduction for the number of searched nodes compared to the conventional method.
• The path costs increased a little around 0.2 %Method

Conventional A*method

Proposed A*method

StartEnd#Searched cellTime complexity (s)Path cost

Bed

Post_box

127,934

42.09

691

Bed

Commode75,121

24.89

520

Bed

Post_box

58,152

5.81

696

Bed

Commode26,2102.76

527

The 8th University of Aizu Robot Symposium

17Path planning using improved A* algorithm: (cont.)• The proposed model has experimented with different start and target positions (service points).

• These are the graphical view of the outcome results.

(a1)

(a2)

(b1)

(b2)

The outcomes of the improved A* algorithm, (a1, b1) conventional A* method, and (a2, b2) proposed
improved A* method.
The 8th University of Aizu Robot Symposium

18

ArUco marker-based service point and obstacle searching:• In a 3D space, detecting service points and obstacles is challenging and requires high computationalpower. Also, it is difficult to accurately detect every obstacle and service point under different lighting
conditions from different angles.
• However, these challenges can be handled easily using ArUco markers because they meet all therequirements in terms of versatility, robustness, and reliability.

• A geometrical square 7 × 7 matrix is used to represent the ArUco marker and up to 1024 different marker
generation is possible.
• Also, it is possible to detect the axis of the marker.

The 8th University of Aizu Robot Symposium

19

ArUco marker-based service point and obstacle searching: (results)• The robotic wheelchair follows the prepared path from one place to the target service points.
• On its path, it also searches for the obstacles and the target service point using the ArUco markers.

(a)

(b)

(c)

Here, (a) = Service point, (b, c) = Obstacle, (c) = Obstacle detection with three axis x, y, and z.
The 8th University of Aizu Robot Symposium

20Dynamic path adjustment to avoid obstacles:• Planning the shortest path is a challenging task, and dynamically adjusting the planned path to avoidobstacles is another challenging task.
• It is very important for a real-time robotic wheelchair to avoid uncertain collisions.
• The proposed approach makes an adjustment in the initially planned path to avoid any collision and makesa new adjusted path dynamically.

The 8th University of Aizu Robot Symposium

21Dynamic path adjustment to avoid obstacles: (results)• Outcome results of dynamic path adjustment method.
Adjusted path

The 8th University of Aizu Robot Symposium

22Conclusion:• An enhanced A* algorithm with different robot motion blocks is proposed to present a fasterrobotic path planning algorithm.
• The proposed ArUco marker-based searching method can quickly search the service point
and obstacles without any computational overhead. Also, it can detect the axis of theobstacle which helps the obstacle avoidance system• The proposed dynamic path adjustment system is helpful for the automated robot forcollusion-free movement.
• Comparison of performances with state-of-the-art methods shows the effectiveness of ourproposed model.
• It is our hope that this proposed path planning method will improve the performance ofautomated wheelchair’s safety operation.
• However, still there are some lickings in our proposed methods which we will investigate in ourfuture works.
The 8th University of Aizu Robot Symposium

23Thank you for your attention

The 8th University of Aizu Robot Symposium24