Motion Coordination for Construction Vehicles using Swarm Intelligence

1. Introduction

As human civilisation develops, more and more civil structures are being built at an ever increasing pace. The application of robotics in automating the construction process may become an important component in the future development of construction technologies. Tasks assigned to and performed by robots during a construction process include but not limited to floor finishing, tile laying, exterior painting, board installation, material handling and delivery (Warszawski, A. & Navon, R., 1998). Mobile robots or vehicles are also very attractive in these application paradigms. For example, concrete cracks in a tunnel are inspected using a mobile robot with onboard cameras (Yu, S. N. et al., 2007). A robotic system is deployed for road lane painting which alleviates the risks encountered by workers in heavy traffic highways (Woo, S., et al. 2007). In particular, multi-vehicles will outperform single vehicles when operating in the coordinated manner in terms of capability, flexibility and economy.

One of the critical issues in deploying vehicles in construction sites rests on their navigational abilities (Lee, S., et al., 1997), specifically, with severe spatial constraints and this naturally leads to the need for formation controls (Desai, J. P., et al., 2001). With this regard, control theoretic (Jongusuk, J. & Mita, T., 2001 and Fierro, R., et al., 2001), and behaviour-based (Balch, T. & Arkin, R. C., 1998) approaches have been applied. In the former approach, controller designs would be very challenging as precise descriptions or models of the system are required, e.g., in a close-form or differentiable expression, and special consideration may be needed to account for numerical instabilities. On the other hand, the latter approach requires expert design knowledge and behaviours are mostly determined in a problem dependent manner.

Alternative methodologies for path planning or formation control, such as soft-computing and evolutionary computation are free from the above mentioned burdens, have increasingly drawn the attentions of researchers and engineers in recent years. For example, a neural network, applying the self-learning principle, was employed in the floor coverage problem scenario in constructions (Yang, S. X. & Luo, C., 2004). However, the coordination of multi-vehicles was not within the scope of the research work described there. Fuzzy logic based approaches for vehicle path planning was reported in (Soltani, A. R. & Fernando, T., 2004) for cases of navigating a single vehicle in construction sites but multi-vehicle coordination issues were also not addressed. In (Ding, Y. et al., 2003), the Ant system algorithm was employed for its natural representation of vehicles as ants and the major focus of the work therein was on the allocation of job schedules with regard to vehicle coordination. Furthermore, the multi-agent concept implemented with genetic algorithms (GA) was reported in (Chen, H. & Xu, Z., 2005, Cao, Z. et al. 2002), where the problem domain addressed was on roadside following for vehicle navigation. In essence, vehicles were treated as living species evolving by adaptation to natural selections imposed by the constraints from the kerb boundaries. However, one of the hurdles in applying the GA is the determination of the many control parameters during the algorithmic design stage, e.g., selection schemes and crossover/mutation probabilities.

From an alternative point of view, the collective motion of vehicles can be treated as an aggregation of microscopic particles evolving through the solid and liquid phases (Gregorie, G. et al., 2003) with a balance between diffusion and cohesion. This analogy further inspires another form of swarm intelligence, namely, the particle swarm optimisation (PSO) algorithm (Clerc, M. & Kennedy, J., 2002) for its simplicity and promising performance in wide application areas. The principle of PSO is based on the exchange of social knowledge and personal experiences among the individuals (particles) in the swarm. Specifically, the algorithm operates by coding potential solutions as individual particles and simulates bird flocks or fish schools moving across the problem space. A solution is produced from the best particle in the swarm. The PSO algorithm has been used in robot path planning (Qin, Y. et al., 2004), navigation (Doctor, S. & Venayagamoorthy, G. K., 2004) and many other design optimisation problems. In (Pugh, J. & Martinoli, A. 2006), the PSO was examined into its algorithmic characteristics. In particular, multiple mobile robots were used as the venue to study the effects of particle group size and neighbourhood topologies in the context of robust learning. Furthermore, performances were made against those obtained from genetic algorithms (GA) and PSO was found out-performing. Here, the use of PSO as an optimizer for the control design purpose is pursued, following the framework given in (Ha, Q. P. & Kwok, N. M., 2007) with the focus on construction automation applications of cooperative multiple vehicles.

In this work, relaxing the constraints encountered in control saturations (Jiang, Z. P. et al., 2001), the PSO algorithm is employed in the multi-vehicle formation control paradigm. This method will be applied for the coordination of the motions of vehicles in a construction site, assuming the information of the locations of the vehicles is available. Speed and steering commands for the vehicles are derived from the PSO algorithm in order to establish the required formation. In this context, waypoint guidance (Whang, I. H. & Hwang, T. W. 2002) are implemented for smooth vehicle manoeuvres. Moreover, to avoid inter-vehicle collisions during the early formation phase, behaviour-based reactions together with dynamic vehicle-target indexing schemes are applied for its implementation ease and satisfactory performances.

The rest of the paper is structured as follows. In Section 2, a description of the problem is presented and the particle swarm optimisation algorithm is introduced in Section 3. In Section 4, the proposed approach is developed and simulation results are given in Section 5. Finally, a conclusion is drawn in Section 6.

2. Problem Description

The problem scenario considered is that construction vehicles are deployed for material delivery, site clearing or excavation, navigating through constrained spaces and in task dependent formations such as lines, columns or wedges and others. Furthermore, the formation parameters may be time-varying as the task requires. Let the motion of the M vehicles under coordination control be described by the following motion model,

$$\begin{gathered} x k + 1 i = f ( x k i , u k i ) \\ [ x k + 1 i y k + 1 i ϕ k + 1 i ] = [ x k i + v k i T cos ⁡ ( ϕ k i + γ k i T ) y k i + v k i T sin ⁡ ( ϕ k i + γ k i T ) ϕ k i + γ k i T ] \end{gathered}$$

(1)

where x k i is the state of the ith (i = 1,···,M) vehicle at time k consisting of its xy-coordinate and orientation ϕ k i with respect to the x-axis, u k i is the drive commands (control) containing the velocity v k i , steering rate γ k i and T is the sampling time.

The goal of vehicle coordination is to derive a sequence of controls for each vehicle, i.e.,

u i = { u 0 i , ⋯ , u k i }

(2)

such that the trajectories

x i = { x 0 i , ⋯ , x k i }

(3)

followed by the vehicles are attracted to the desired ones of a formation determined by a high-level path planner. These controls can be obtained by applying control theoretic or behavioural-based approaches. However, computational considerations such as numerical stability and storage requirements have to be catered for. To this end, an evolutionary computation technique, the particle swarm optimization algorithm for its efficiency and effectiveness, is adopted to tackle the multi-vehicle coordination problem addressed in this paper.

The particle swarm optimization (PSO) algorithm can be viewed as a swarm intelligentce-based multi-agent heuristic search method where potential solutions are coded as particles. The algorithm contains a recursive iteration loop (generations) and can be described by the following pseudo code.

Initialize particles randomly across the solution space

While not terminate

o

Evaluate the particle fitness

o

Find the best particle

o

Find the best instances of particles against generations

o

Calculate particle velocities

o

Update particle locations

o

Increase generation count

Terminate if generation count expires.

In the context of vehicle coordination, the vehicle speeds and steering commands are coded as particles,

u p , k i = { v p , k i , γ p , k i } T , p = 1 , ⋯ P

(4)

where p is the particle index and i is the index for a vehicle.

The particles in the solution space are allowed to move with arbitrary velocities (which is distinguished from the vehicle speeds). The initial particle velocities may be all set to zero or random numbers. In subsequent generations, the velocities are determined as

v p , g + 1 i = w v p , g i + c 1 i ( u ^ g i − u p , g i ) + c 2 i ( u ~ p , g i − u p , g i )

(5)

where w is a weighting factor representing the momentum of the particle, g is the generation count, (C₁, c₂) ∈ [c_min, c_max] are uniform random numbers denoting as the gain factors, u ^ g i (group-best) is the particle that gives the best performance within the swarm at the g-th generation, u ~ p , g i (personal-best) is the best performing instance of the p-th particle over the past generations. The momentum weighting factor determines the randomness in the search for solutions, while the gain factors are responsible for the rate of convergence to the optimum solution.

Assuming a unity sampling time step, the particle locations in the solution space are updated in the next generation as

u p , g + 1 i = u p , g i + v p , g + 1 i

(6)

The algorithm then iterates through a pre-determined number of generations and the best particle u ^ g ̄ i at the terminating generation g → is used in controlling the ith vehicle to move to its next location from time k to k+1 by letting u k i ← u ^ g → i .

4. Proposed Approach

In this paper, the coordination of multi-vehicles into formations is achieved by combining the PSO algorithm and the behaviour-based motion strategy in deriving the motion commands as well as avoiding inter-vehicle collisions.

4.1 Particle structure

For the M vehicles to be coordinated, there are M sequences of control commands to be determined by the PSO. The approach adopted assumes that a high-level path planner is available to design the required formation and each vehicle knows it current location. This gives a set of formation locations or targets as

$$\begin{gathered} X t = { x 1 , ⋯ , x M } \\ x t = { x t , y t , ϕ t } , t = 1 , ⋯ , M \end{gathered}$$

(7)

where each formation location contains its corresponding xy-coordinates and the orientations are referred to the x-axis. On the other hand, the initial locations of the vehicles are not specified (i.e., not in a formation) but their locations are known to the PSO algorithm.

The control commands are represented by a set of control particles. Note that for the M vehicles each one contains a set of P location particles describing the possible locations of virtual vehicles. In each generation, the particles are used to move the virtual vehicles according to the motion model in equation (1). The predicted vehicle locations are shown in Fig. 1.

OPEN IN VIEWER

Fig. 1.

Predicted vehicle locations by the drive commands given by the particles

4.2 Waypoint based formation

The formation of vehicles into platoons is furthered treated as a tracking problem. Due to the non-holonomic constraints of the vehicles they cannot turn abruptly. First, the distances between the vehicle particles and the virtual vehicles as targets are calculated, giving the translational and angular tracking errors between the predicted vehicles and their corresponding targets, that is

e d = ( x t − x v ) 2 + ( y t − y v ) 2 e θ = tan − 1 ⁡ ( ( y t − y v ) / ( x t − x v ) )

(8)

where subscript t denotes target and v stands for the vehicle, and particle indices are dropped for clarity. Furthermore, because of the non-holonomic constraints, waypoints are constructed such that the vehicle approaches its target location with the angle of arrival aligned in relation to the target orientation. Without the use of waypoints, rapid turns may result when the target is approached. Specifically, the waypoint is formulated as a secondary target given by x_wy_w in the following as

d w = α ( x t − x v ) 2 + ( y t − y v ) 2 , θ w = ( θ t + θ v ) / 2 x w = x t − d w cos ⁡ θ w , y w = y t − d w sin ⁡ θ w

(9)

and is depicted in Fig. 2. Here α = 0.35 is a weighting factor determined experimentally.

OPEN IN VIEWER

Fig. 2.

Waypoint configuration

When the vehicle approaches the waypoint, the distances x_t –x_v, y_t – y_v diminish and gives a decreasingd_w. Eventually, the waypoint coincides with the target. Moreover, as orientation tracking error reduces, the waypoint angle θ _w also approaches the target orientation θ _t as required. The net effect is that the vehicle moves towards its target with a prescribed angle as the target, minimizing the limitations of a non-holonomic vehicle.

4.3 Particle fitness

The goal of formation is to steer the vehicles to their targets by minimizing the translation and angular errors. To this end, the problem posed for the PSO becomes that of a multi-objective optimization process while deriving the speed and steering commands. Consequently, the fitness of the particles is defined as follows.

For each particle, calculate the waypoint errors

$$\begin{gathered} e d w i = ( x w − x v ) 2 + ( y w − y v ) 2 \\ e θ w i = tan − 1 ⁡ ( ( y w − y v ) / ( x w − x v ) ) − θ v \end{gathered}$$

(10)

The fitness is then assigned as

f i = e d w i + | e θ w i |

(11)

Based on this definition of fitness, a dynamical importance weighting is implicitly imposed on the two objectives. It is noted that the maximum value of absolute angular error is π. When the vehicle is located away from its target, the translational error dominates. Alternatively, the angular error dominates when the translational error decreases when the vehicle is close to its target.

Finally, the fitness for the particles is used through the PSO iterations to obtain the drive commands issued to the vehicles as described in the previous section.

4.4 Collision avoidance

When the vehicles started to move towards their required locations, there is a high possibility that they may collide with each other and competing for passages to the targets. In this work, the behavioural-based reactive scheme is adopted and is complemented by a dynamical vehicle-target indexing procedure.

At every time step, the distances between the vehicles and their angular separations are calculated. We have

$$\begin{gathered} d j k = ( x j − x k ) 2 + ( y j − y k ) 2 \\ θ j k = tan − 1 ⁡ ( ( y j − y k ) / ( x j − x k ) ) − θ k \\ j , k = 1 , ⋯ , M \end{gathered}$$

(12)

forming two tables with reference from the j-th to the k-th vehicle.

For each vehicle, the minimum distance to other vehicles is checked against a pre-defined safety radius, determined by the vehicle size. If any vehicle falls within this circular region and coincides with the vehicle's path, a potential collision (with the vehicle as an obstacle) is declared and the following behavioural-based avoidance routine is invoked, see Fig. 3.

OPEN IN VIEWER

Fig. 3.

Behavioural-based collision avoidance scheme

In the figure, the concerned vehicle is labelled 0, while the potential colliding vehicles are labelled from 1 to 8 according to their relative locations to the 0-th vehicle. The following rules are applied.

If a collision is declared then stop moving for some time steps.

In addition to the reactive scheme in avoiding collisions, the dynamical indexing procedure is implemented. Initially, the indices are assigned in a one-to-one basis. For example, the j-th vehicle is assigned with the j-th target. Here the distance between a vehicle and all targets are calculated as

$$\begin{gathered} d j t = ( x t − x j ) 2 + ( y t − y j ) 2 \\ j , t = 1 , ⋯ , M \end{gathered}$$

(13)

A new pair of index relating the jth vehicle, say, to the tth target, is re-defined if the distance is smallest, i.e.

d j t ∗ = min t { d j t }

(14)

By implementing the proposed dynamical indexing schedule, occurrence of dead-lock case are reduced. Note that this approach is limited to homogeneous vehicles.

Simulations are conducted to verify the effectiveness of the proposed methods. Benchmark formations tested are line, column, wedge and diamond. The simulations have involved 5 vehicles, one designated as the leader of the formation pattern. There are also two trajectories that are followed by the leader, say as the task requires, in a 120-by-120m environment. Test scenarios mimic tasks frequently found in a construction process such as material handling, trench excavation, pipe laying or site clearing.

5.1 Trajectory 1

Resultant motion traces of the vehicles are shown in Fig. 4. The trajectory followed by the leader firstly follows a circle in anti-clockwise rotation in the north-east region. It then moves in a straight line to the south-west region where it finally makes a clockwise turn to the west region.

OPEN IN VIEWER

Fig. 4.

Traces of vehicle motions for trajectory 1

In Fig. 4a, the vehicles (illustrated as small triangles) show a close following of the line pattern despite irregular paths observed during the initial periods. This is, unavoidable, mostly due to the need to avoid collision among them. After the formation is established, collisions do not occur.

Results for the column formation are depicted in Fig. 4b. Here, column formations are clearly illustrated. Particularly, it is clear that columns are formed when travelling from south to north, from north to south-west regions and the final periods. It is note that, due to non-holonomic constraints that the vehicles cannot turn rapidly, larger circular arcs are traced. Nonetheless, the vehicles are able to establish the column formation when the leader is moving in a straight path.

The wedge formation result, as given in Fig. 4c, illustrates an averaging phenomenon between the line and column formations. Geometrically speaking, the wedge formation is a combination or inclined patterns of line and column. It is shown that the wedge formation is satisfactorily established.

In Fig. 4d, results from a diamond pattern are depicted. Promising performances are also noticed as the vehicles are able to follow the leader at their corresponding displacements. On the other hand, the diamond is viewed as an end-to-end combination of wedges and the size is compressed. In this regard, non-holonomic constraints are not as severe as in the previous cases. Therefore, circular arcs are traced while the turning diminishes in magnitude and the formation is more tightly established.

5.2 Trajectory 2

Resultant motion traces of the vehicles are shown in Fig. 5. The trajectory followed by the leader firstly follows a semi-circle in anti-clockwise rotation in the north-east region. It then moves in a straight line to the north region and turns towards south-west where it finally makes a clockwise turn to the west region.

OPEN IN VIEWER

Fig. 5.

Traces of vehicle motions for trajectory 2

For this trajectory, results for the line formation are shown in Fig. 5a. Despite the difference in the initial vehicle locations, the line formation is well established and maintained.

Results of column, wedge and diamond formations, shown in Fig. 5b through 5d, all indicate satisfactory establishment of the desired pattern. Due to the difference in the leader trajectory to be followed, collisions between the vehicles are noticeable for the line pattern. Notwithstanding this difficulty, collisions have been successfully mitigated in the other formation patterns.

In summary, the proposed method is robust against the change of formation patterns. The approach is also immune to different leader trajectories as well as initial vehicle locations.

6. Conclusion

This paper has presented an approach for the coordinated motion of vehicles to establish a formation with possible application in construction automation where the deployment of cooperative vehicles is required. The minimization of formation tracking error is posed as an optimization problem. Drive commands issued to the vehicles are derived from the particle swarm optimization algorithm. The behavioural-based and dynamical re-indexing schemes are also implemented in order to alleviate possible collisions between the vehicles. Simulation results have shown the effectiveness of the suggested methods for benchmark formation patterns.