1.Introduction

Most the designed and developed of robots are to work in extreme environments such as ocean bottom, space and hazard prevention. It is not easy for the people living there because of the high atmosphere, the low temperature and the high risks for the life of people. However, the robots are capability of replacing people to reduce the risks. In fact, there are many different types of robots have been produced for many years, but they can be classified into two types according to the mobility on the ground. The first type is Fixed-robot. They don't have the ability of self-relocation and the second type of the robot is Mobile-robots. For Mobile-robots, they can freely travel by using the self-locomotion ability. This paper only focuses on the last type that is Mobile-robots. Therefore, when the word “robot” that is mentioned in this paper, that mean is Mobile-robots. The self-locomotion of the robot can be performed in a lot of ways such as wheels, crawlers and fly. The robots are also separated into two types of Wheeled-robot and Legged-robot that depends on the mobility of the robot that is a wheel or a crawler, respectively.

The structure of a robot is mostly mechanical structure to form a kinematic chain of the robot. In addition, they also include their integration with sensors, actuator and controller system. For Wheeled-robot, it is easy to design a mechanism and a controller, but if the robot must work on the ground which the depression of a surface is greater than the diameter of wheel then the robot cannot pass over. The Legged-robot has a locomotion ability that is better than the Wheeled-robot’s but it is very complex to design mechanical structure and the keep the stable status of Legged-robot in a moving situation. Because the kinematics of the legged robot is nonlinear, it means that the robot’s parameter is varied according to the time (Chen et al., 2001). However, if the robot has to work on unfavorable environment like a rough terrain, then the best choosing in this situation will be the Legged-robot. The controller of the Legged-robot will be simpler by using a designed sequence of footholds (Fig. 1).

The sequences are using as position set-points of the robot controller (Hirose et al., 2002; Hirose, 2001). In this case, the locomotion of the Legged-robot is only defined by two types of the moving. The first moving is called the straight-going gait and the other is called the standstill-turning gait (Chen et al., 2002; Izumi et al, 2001; Hirose, 1984). In the straight-going gait, the robot’s direction is along the y-axis in the frame Σc (the Σc represents a frame which is attached with the robot’s body) (Fig. 1a). In the standstill-turning gait, the robot will turn ϕ angle around the center of the robot’s body, however, the position of the robot along y-axis which is not changed during the turning cycle time (Fig. 1b). The robot’s center after finished a straight-going and standstill-turning gait which are denote by c*.

If the position of the standstill-turning points is known then the robot is able to walk to anywhere by using straight-going and standstill-turning gaits sequence. In Fig. 2, it is shown an example of a method to go to a goal by using straight-going and standstill-turning gaits sequence.

Therefore, an algorithm has to develop to find these turning points for the robot. This issue have been mentioned in many researches (Chen et al., 2000; Pan and Cheng, 1991). Unfortunately, the researchers have not mentioned that how to minimize the robot’s moving distance. In this paper, we proposed a new method to find the shortest way and avoid obstacles on the terrain by using Dijkstra’s algorithm. In the robot’s journey, it will meet not only small obstacles but also large obstacles.

For small obstacles, the robot can easily step over. Obviously, for large obstacles, the robot can’t walk over the obstacles because the height of obstacles may be higher than the height of robot’s footstep. In this situation, it is assumed that the obstacles on the terrain which are enough height to the robot can’t step over or cross over, therefore, the best choice of the robot is walking around the obstacles. The Dijkstra's algorithm and turning point finding method are presented at Section 3. There are seven section in our research paper contain. Section 1 is introduction. Section 2 is the mechanical structure of quadruped robot TITAN-VIII. Section 4 discusses a way to obtain the generation of quadruped robot gait. Section 5 is simple flow chart of the control algorithm. The experimental results are shown in Section 6. Finally, Section 7 shows some of the conclusions drawn from this research.

2.Mechanical structure of TITAN-VIII

This paper is focused on TITAN-VIII that is a kind of the Legged-robot. A photo of quadruped walking robot TITAN-VIII is shown in Fig. 3. The major specification of TITAN-VIII in standard walking posture and is 0.3 [m/s] (craw gait) and 0.9 [m/s] (trot gait). The payload is 5~7 [kg]. Its leg length is 400mm and weight is 40kg. It is fed from battery or AC-DC power supply.

It is used to for general application purpose. The mechanism of the TITAN-VIII is a standard mechanism that composed of rotating joints. The robot’s body is made of aluminum rectangular plate which is attached with four legs by rotating joints. These legs are driven by three actuators for each leg. The actuator consists of a DC motor and a motor driver. This will result in 12 actuators for 4 legs that make a more complex of the robot’s construction, but it is making an ability to climb over a plane’s slope.

The Fig. 4 is showed a block diagram of TITAN-VIII. It is included a Titech Robot Driver, a 16 channel D/A converter, a 16 channel A/D converter and a ARM Cortex-M3 microcontroller as a main controller. The desired joint angle of four legs can be automatically computed by main controller, after that it is transformed to the physical value by the D/A converter and sent to the motor driver. The real angles are on-line measured by means of the potentiometer to be sure that the joint angles reach to desired angles. The specifications of motor driver are U = 30 [V], Imax = 8 [A], Ucontrol = ±10 [V].

The schematic drawing of TITAN-VIII is presented in Fig. 5. In this figure, a, b, d and e are called the length of four link of four legs, respectively. The leg’s mechanisms are composed of a link-wire plane mechanism, a rotating mechanism and a round plate as its foothold.

In Fig. 5, the frame Σc is denoted as a fixed frame at the robot’s Center of Gravity (CoG) and another fixed frame is attached with the ground, is named Σo. It is used to describe the robot’s motion in the global frame. In the Σc, the position vector of A_i and B_i are determined by c ρ A i = [ c x a i , c y a i , c z a i ] and c ρ B i = [ c x b i , c y b i , c z b i ] for i = 1, 2, 3 and 4, respectively. In addition, the correlation between Σc and Σo is expressed by vector o ρ c = [ o x c , o y c , o z c ]. Ai and Bi in Σo are given by:(1)(2)

Where: T is the orientation matrix of Σc with respect to Σo(3)

ϕ is a turning angle around center c, ϕ = 0 means that there is no changing direction.

3.Dijkstra’s algorithm

In most situations, the walking time of the robot to a desired point (a goal point) must be the shortest time for increasing of the robot’s working efficiency. Therefore, the robot controller has to find the shortest way to the goal and avoid obstacles which appear on the terrain. There are a lot of methods to find the shortest way such as Dijkstra's algorithm, Bellman–Ford algorithm, Floyd–Warshall algorithm and Johnson's algorithm. The Dijkstra's algorithm was selected in this research because its operations are less complex than the others. It is very important in real-time control system of autonomous robot. In our experiment, we use a controller which is made by ourselves. Our robot controller has an ARM^®Cortex^®-M3 microcontroller and an AVR microcontroller without using a personal computer like the original robot controller. By using an independent controller, the robot can freely walk on working area without restricted by the connecting wires between the robot and the computer. In our controller, ARM^®Cortex^®-M3 has a higher processing performance than AVR microcontroller’s, therefore, the path-finding algorithm is performed by ARM^®Cortex^®-M3 microcontroller and AVR for controlling peripheral devices such as actual motor drivers and sensors, respectively.

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph (Dijkstra, 1959) The algorithm was commonly used for two purposes. The first, it can be able to find the shortest path between a starting node and another node in a graph. The second, it can also be used for finding the shortest paths from a starting node to all other nodes. In the second purpose, for example, if the nodes are the cities and length between the pair of nodes represent driving distances then Dijkstra's algorithm can be used to find the shortest route way between one city and all other cities. Most situations, the robot only walks from a starting point to goal point, so the first method is a more accordant choice. Dijkstra’s algorithm is discussed more detail at the following part.

The algorithm uses a graph as shown in Fig. 6a. The starting and goal point is called “s” and “d”, respectively. In the graph, it is existed some the pair of vertexes which are called inter-vertexes, they have the ability to connect with other ones. The rest of ones do not have any this ability, they are seen as their distances between them are infinity.

Dijkstra’s algorithm finds the shortest path between “s” and “d” in a graph as Fig. 6a. There are six vertexes in this graph numbering from 1 to 6. The distance is 15, 8 and 5 units from “s” to 2, 3 and 4, respectively. Vector V are defined to mount marked vertexes as “a bag” to contain intermediate vertexes in the operation of algorithm. The starting point is added into V like first element at the initialization stage. And now, the algorithm is starting at vertex 1 with only one element in V, V={1} and vertex 1 is called the current vertex. We can see that the pairs of 1-2, 1-3 and 1-4 are inter-vertexes and the shortest corresponding distance path between “s” and vertex 4 is 5 units. Therefore, vertex 4 will be marked a label as a current vertex and will be also added to vector V, then vector V has one more element and is expressed by V={1, 4}. So, vertex 4 is not connected to vertex 2 and vertex 5, the distance from vertex 4 to them is infinity. Obviously, the vertex 4 is connected to vertex 3 and vertex 6 but vertex 3 is selected as a candidate for adding V because the distance from vertex 3 to vertex 1 through current vertex 4 that is shorter than the distance from vertex 6 to vertex 1 through vertex 4, we have V={1, 4, 3}. The general formula for finding the length from a vertex to s that is presented as following.(4)

Where L_k(s, v) is a length from vertex v to starting vertex s at the cycle k and L_k-1(s, v) is the length at before cycle of cycle kth. L_k(s, u) is the length from current vertex u to s and w(u, v) is the length between vertex u and v. If there is more than one vertex with current vertex to make a pair of inter-vertexes then the vertex with the smallest L_k which will be selected as current vertex at next cycle. Additionally, we have to note that we don’t need to consider vertexes which have been in V. In the Fig. 6, the current vertex is marked by symbol *.

And then, vertex 2 is chosen as a candidate for current vertex because the distance from vertex 2 to vertex s is equal to 10 units (from 2 to “s” through 3) and the distance is shorter than the distance from vertex 6 to vertex s. At this moment, V is added an element, V= {1, 4, 3, 2}. Because it is easy to see that the vertex 2 is only connected to vertex 5 , it becomes a next current vertex, V={1, 4, 3, 2, 5}.

In addition, vertex 5 is connected to the goal vertex as a unique connection. The algorithm will be stopped when the goal vertex is appeared in V vector. After all, we have V= {1, 4, 3, 2, 5, 6}. By finding vector V and saving the vertex tracings of current vertexes, the vertex are as turning-points of the robot which are obtained. Finally, we obtain the desired the robot path by connecting all the selected turning-points successively. The designed path is drawn in a solid line (Fig. 6f) which is generated from the starting point to the goal point. The algorithm is also used to determine a suitable path of the robot in an environment with many obstacles.

In Fig. 7, it is showing an example of the robot journey to destination. We figure out that the robot working environment is a plan with a gird. The meshes are made by vertical and horizontal lines with the same length between them. The lengths are a fixed value and are determined by an experimental equation. If the lengths are too small, the robot will not have enough space to perform self-standstill-turning gait. In addition, the robot path will be longer, if the lengths are more than the necessary value. The suitable length can be expressed by following experimental equation:(5)

Where, 2n is the length of robot body. S_max is the longest footstep of the robot in a gait cycle and Δ is length of meshes. The purpose of making the gird is a technique to find suitable turning-points along the moving direction from the starting-point to the goal-point.

The crossing points between horizontal lines and vertical lines of the grid will be chosen as candidates for turning-point. At the crossing points, there are three ways to go to a next point that is along vertical, horizontal line and diagonal line as shown in Fig. 8.

We assume that the robot is being vertex 1, while the robot is able to select one of three directions. From current turning-point to vertex 2 denotes the direction vector from 1 to the goal, therefore, the vertex 2 is the next current position.

At the vertex 2, the diagonal line from 2 to 6 and 7 is prevented by an obstacle, therefore, the robot can only go straight to 3 along solid line. Obviously, when the robot is on 3, the diagonal line from 3 to 8 is selected such a unique line because others lines are inhibited by some obstacles on the environment. A boundary with the safety distance is imagined surrounding obstacles. The boundary will separate the working space of robot into two parts that are the forbidden and allowed zone. If an obstacle is too near others, the robot won’t make a though way between them. In this situation, these obstacles are considered to be only one obstacle; they are called the combined obstacle. A specified line is generated surrounding the combined obstacles to make a region that prevent approaching robot to be nearer.

The obstacles on terrain will be detected by the robot’s sensors such as the camera, proximity sensors and ultrasonic sensors. The sizes of obstacles are measured by processing the acquired images from a camera to create a terrain map with fully obstacles.

4.Generation of the quadruped robot gait

In the middle of walking or running, a quadruped robot has to have balanced in order to avoid falling or unwanted body motion. Therefore, the controller has to generate a fit gait with the robot motion. There are many methods to generate a gait of Legged-robot as discussing in (Chen et al., 2001; Hirose et al., 2002). The purpose is to keep the projection of CoG onto horizontal plane within the supporting polygon which is created by supporting legs of the robot. In other words, the robot is being in the statically stable (Chen et al., 2001).

In the statically stable gait, the robot is able to remain stable as long as the CoG within the support area. It is shown an example of the quadruped robot in others status (Fig. 9). The black solid rounds are representing the robot foothold contacting ground which role such supporting legs on a working cycle of the robot and the white rounds are lifting-legs. In left part of Fig. 9, three legs provided a support area and the horizontal projection of CoG is located into the support area, therefore, the robot is in the statically stable and vice versa.

The shortest distance from CoG to the different edges of the support polygon is stability margin (Fig. 9). The stability margin provides some indication of the ability to resist disturbances while it is in the walking statically stable. The higher stability margin of the robot is the better because this is demonstrate that the robot is not easy to fall down when the robot is working at varied terrain.

We will define a sequence of the legs of the quadruped robot to keep CoG onto the support area at any time, is shown in (Fig. 10).

For keeping CoG on to support polygon, three legs has to support its body at any time and one leg left that will play a role as the swing leg (lifting up). In a moving cycle, the support leg does a successive performance swing-ahead, although it does not lift up. With respect to the swing leg, it performs a sequence of the moving including three types of the moving that are lift-up moving, swing-ahead moving and put-down moving in a cycle. The robot repeats the sequences of the moving at the other cycles. The generation of quadruped robot gait to form the sequence of swing leg and support leg which is selected in such a way that keeping the vertical projection of CoG onto horizontal plane within the support area.

We define Σo and Σc like above. The quadruped robot is being in initial posture with the stride of legs and the height of the CoG that are denoted L₀ and H₀, respectively. Thus, the position vectors of four footholds in Σc are given by:(6)(7)(8)(9)

And, the relation between Σo and Σc can be expressed by:(10)

Where, h_i ( i= 1, 2, 3 and 4) is height of the i^th foothold. Normally, the value of h_i is equal to zero but there is an exception that is when the robot climbs up and down on the stair. The height of the body is denoted by ^oz_c. The robot body plate is always parallel with vertical plate and locates at a higher position than the ground; therefore, ^oz_c is not equal to zero.

When the robot begins to crawl forward, the third leg A₃ will be lifted up firstly after that it swings ahead a distance S ( S is shorter than S_max ) and put down at last of its duty, and finishes first step of a sequence of steps. The new position of A₃ is denoted by A^*₃. The foothold of other legs is still at the same position during this phase. It’s clearly that the CoG is always settled in a supporting polygon which is made by A₁, A₂ and A₄. Obviously, the new position of the A₃ with respect to Σc can be determined by following equations:

c ρ A 3 = [ − L 0 − m , − n + S , h 3 ]

The robot body is moved ahead a quarter of S after the first phase. The posture of the robot is varied as shown Fig. 9a. The position vector of CoG becomes:

o ρ c = [ o x c , o y c + S / 4 , o z c ]

Similar to first selected swing leg, the others should be the next swing leg after the third leg. It is obvious that the robot body will be moved ahead a distance of S after completely four steps. The sequence of swing leg can be determined as 3→1→4→2 or 4→2 →3→1.

The sequence of legs in standstill-turning gait is presented as Fig. 11.

We assume that the turning angle is ∅. If the robot performs a left turning ∅ then the turning angle will be ∅ > 0; otherwise, ∅ < 0. Similar to the straight-going gait, the initial posture of the robot in standstill-turning gait is presented by solid line as shown in Fig. 11a. The A₄ leg can be selected as the first swing leg as shown in Fig. 11b. The A₂ leg should be the next swing leg. After A₂ and A₄ legs, the A₁ leg should be selected as the swing leg. Finally, the A₃ leg performs a footstep to position A^*₃, then the robot is returned to the initial posture. Therefore, the sequence of swing leg for left turning is 4→2→1→3; otherwise, the sequence is 3→1→2→4 for right standstill-turning gait about the robot center c. The foothold vector can be determined the same way with straight-going gait.

TITAN-VIII has four legs and three activating joints in each leg (Fig. 12), where θ_i1, θ_i2 and θ_i3 are joint angles. Based on the generated desired gaits above, the position of footholds can be known at any time of a moving cycle. Now, the key for implementation of the desired moving is how to know angle joints of the robot. If we can know them, we can completely control the robot to follow a desired trajectory. It’s easy to know that the value of θ_i1, θ_i2 and θ_i3 will be determined in relation of the height of the robot body H_i and the stride L_i, as shown in Fig. 12. When the robot moves, the formulations for determination of value of θ_i are generalized based on an equivalent leg mechanism of TITAN-VIII.

Thus, we obtain equation:

The other side, we can obtain the height of legs and stride from the position of foothold A_i and B_i in Σc. We suppose that the shape of leg is constant from start to end of a moving cycle, and then we obtain:

Where: c ρ A i = [ c x a i , c y a i , c z a i ] and c ρ B i = [ c x b i , c y b i , c z b i ], for i = 1, 2, 3 and 4, respectively. Moreover, the revolute joint of Bi is able to rotate around z axis, we have:

Therefore, we finally obtain (14) from (11), (12) and (13):

We denote some constants as follows:

e i x = c x a i − c x b i ; e i y = c y a i − c y b i ; B t = c z a i − c z b i A t = ( c x a i − c x b i ) 2 + ( c y a i − c y b i ) 2 C t = ( A t 2 + B t 2 − b 2 − d 2 ) ; E t = b C t + d ; F t = b sin D t

Solving equation (14), we can obtain the joint positions θ_i1, θ_i2 and θ_i3 as shown in equation (15).

Because of the limit of the robot’s mechanism and the roughness of the ground profile. When the robot reach the maximum stretch of four legs, it takes a maximum stride. The maximum stretch, denoted by Amax, is defined by equation (16) (Chen et al., 2001).

Where Δν denote the roughness of the ground profile, H0 is the height of the robot center-of-gravity in the initial posture. The leg stretch of the quadruped robot should satisfy:

Equation (17) is boundary condition to solve equation (15).

The maximum stride and the maximum turning angle are denoted by S_max and ∅_max, respectively. The maximum stride is the longest footstep in a gait cycle. ∅_max is a maximum turning angle of the robot’s joints in a gait cycle when the robot takes a left turning or right turning. T, are mentioned (Chen et al., 2001).

5.The control algorithm

The flow chart of control algorithm is shown in Fig. 13. The parameters at initial posture, a robot staring point and a goal point are given as initial inputs for the algorithm. The ground profile of the terrain is determined by the sensor system and the vision system. The collected data from the system is used to create a grid map that consists of the information of obstacles. The grid map play a role Dijkstra’s algorithm input data. Based on the information, the shortest trajectory to the goal point will be completely established by Dijkstra’s algorithm. The robot position vector is known from the trajectory after that the joint angles are determined from equation (15). Finally, the quadruped robot is actuated though ROBOT DRIVER to DC motor. If the robot doesn’t reach the goal point in a moving cycle then the control system will repeat the sequence of leg until the robot is on the goal.

6.Experimental result

The robot in our experiment which is named TITAN-VIII, the size of robot body and robot legs are as follows [mm] m = 101, n = 201, a = 43, b = 200, d = 155 and e = 45. The initial posture is given by the position of legs with θ_i1 = 0, θ_i2 = 0 and θ_i3 = 90⁰, so that the length of legs and the height of body at the robot initial status are L₀= 200 mm and H₀= 243 mm, respectively. The largest stride and maximum turning angle in a gait cycle are S_max = 226 mm and ∅_max = ± 44⁰, (Hirose et al., 1984), respectively. If the desired turning angle is a larger turning angle than the robot maximum turning angle, the robot has to implement the stand still-turning gait for several times to reach the desired angle. The experimental results were conducted on a computer and there is simulation software installed on it. There are a lot of robot simulation software such as Matlab & Simulink, Gazebo, Webots and RoboDK. In our experiment, Matlab & Simulink was selected. The coordinates of a starting point and a goal point were given by user. A coordinate grid map was established on terrain and the robot was in a node of the grid. There is an obstacle on the terrain which the robot could step over; the robot had to find the shortest path to go to the goal. The simulation environment for the robot is presented in Fig. 14.

The bold line was the robot trajectory which was automatically created by using Dijkstra’s algorithm. An obstacle was putted on the simulation environment that was indicated by the gray polygon (Fig. During the walking process on simulation environment, the robot avoided the obstacle by going around the obstacle because we assume that the robot can step over the obstacle. The left bottom corner is the starting point and right top corner is the goal point.

The change of variable joint θ_i1, θ_i2 and θ_i3 in a straight-going gait cycle were shown in Fig. 15.

A gait cycle is every 5s. At the time t = 0 ÷ 1s, when the robot was being in initial status, the variable joints were equal to initial value.

At time t = 1 ÷ 2s, the robot moved its leg 1^st backward in the direction of the motion, when θ₁₁ was increased at the first period and reached a stable angle at the end of period (Fig. 15a). It is easy to see that θ₁₃ also was changed because the length of leg 1^st was already increased a distance at this time.

At time t = 2 ÷ 3s, the leg 1^st was as the swing leg, it was lifted from ground and was swung ahead. According to the sequence of steps in Fig. 10, the θ₁₁ and θ₂₁ were increased continuously to keep the leg’s foothold 1^st at the ground all the time t = 3 ÷ 4s and t = 4 ÷ 5s and were came back the initial angle at the end of cycle (Fig. 15b, c).

The change of the length of four legs in a moving cycle was shown in Fig. 16. The lengths of legs were changed between the initial status is L₀ = 200 mm and 215.7 mm.

Because the robot crawled without changing the height of CoG, the difference between H_i at first and last cycle is equal to zero. The height of four legs was presented in Fig. 17. At the turning point the robot will change its gait from the straight-going to the standstill-turning gait. The changing length of legs in this process were shown in Fig. 18. It is clearly that the robot turning angle is either ± 45⁰ or ± 90⁰, on the other hand, the maximum turning angle of the robot is ∅_max= ± 44⁰. The turning gait will be done two times when desired turning angle was ∅ = ± 45 and will be need four times when desired turning angle is ∅ = ± 90. After the standstill-turning, the robot walked toward in a new moving direction. The robot will repeat the sequence of moving until it reaches the goal.

7.Discussion

This paper has presented a method of generating a straight-going gait and a standstill-turning gait for a quadruped robot TITAN-VIII. The formulations of evaluating position of foothold in fixed frame have been mentioned in this paper to determine the joint positions in moving cycle of the robot. In addition, the path finding algorithm has also been developed to avoid obstacles on the robot terrain. The obstacles avoidance algorithms based on Dijkstra’s algorithm choose the suitable path to a goal. The proposed Dijkstra’s algorithm is characterized by just finding the turning-point rather than the making a curve trajectory that reduces the calculation processing. It means that there is a fewer calculations processing than others, therefore, the sampling time is able to choose a small value to help increasing the robot speed.

The experimental results verified the reliability and effectiveness of the proposed method. It's proven by two things. First, the robot can perform a smooth transition from one gait cycle to a other one, because the robot returns to the initial posture after each gait cycle whenever it is in a straight gait or turning gait. Next, a possible large stride of the robot can be taken in very gait cycle by considering various factors in the robot status such as mechanism constraints, uneven terrain.

It should be also first research that the proposed method can be applied to general crawling with different duty factors. Moreover, the proposed method can be work in real world condition.