Optimal robot task scheduling in cluttered environments considering mechanical advantage

Abstract

In various industrial robotic applications, the effective traversal of a manipulator amidst obstacles and its ability to reach specific task-points are imperative for the execution of predefined tasks. In certain scenarios, the sequence in which the manipulator reaches these task-points significantly impacts the overall cycle time required for task completion. Moreover, some tasks necessitate significant force exertion at the end-effector. Therefore, establishing an optimal sequence for the task-points reached by the end-effector’s tip is crucial for enhancing robot performance, ensuring collision-free motion and maintaining high-force application at the end-effector’s tip.

To maximize the manipulator’s manipulability, which serves as a performance index for assessing its force capability, we aim to establish an optimal collision-free task sequence considering higher mechanical advantage. Three optimization criteria are considered: the cycle time, collision avoidance and the manipulability index. Optimization is accomplished using a genetic algorithm coupled with the Bump-Surface concept for collision avoidance. The effectiveness of this approach is confirmed through simulation experiments conducted in 2D and 3D environments with obstacles employing both redundant and non-redundant robots.

1. Introduction

Nowadays, numerous applications in industry use robots and especially redundant manipulators, which are requested to visit successively multiple targets in working cells cluttered with obstacles. The effective utilization of robotic systems yields enhanced productivity, reduced production costs, and improved product quality. The optimization of production costs and the maximization of productivity stand as primary objectives within the realm of industrial automation. Strategic task scheduling emerges as a significant area of focus and concern to thoroughly investigate the complete potential of the robot, ensuring a comprehensive exploration of its capabilities. [1].

Industrial robots employing six degrees of freedom (DOF) can accomplish both translation and rotation of the end-effector in any chosen direction within the workspace. The increasing deployment of robot manipulators across diverse industrial tasks underscores the imperative for researchers in robotics to address challenges associated with achieving heightened precision, enhanced productivity, cost reduction, and superior manufacturing quality. Nevertheless, a noteworthy portion of the workspace is frequently characterized by singular configurations, leading to high joint torques induced by forces at the end-effector. The existence of environmental obstacles further imposes constraints on the robot’s mobility.

The added flexibility of redundant manipulators proves beneficial for circumventing obstacles and reaching locations that are typically inaccessible. In industrial robotic applications, the objective of enhancing productivity in path following involves identifying time-optimal collision-free paths while considering the torque limits of the actuators. Consequently, the development of sophisticated motion planning algorithms becomes crucial to leverage the advantages of redundant manipulators effectively and fully. These algorithms should exploit the inherent capabilities of redundant manipulators to navigate internal singularity configurations and obstacles, thereby achieving enhanced manipulability [2].

Analyzing the performance attributes of a robot, including dexterity, manipulability, and accuracy, holds paramount importance in the design and analysis of a robot manipulator. Within the realm of kinematics, manipulability denotes the capacity of robot manipulators to move in arbitrary directions. As a quantitative metric for this capacity, Yoshikawa [3] proposed one of the earliest mathematical measures for the manipulability of serial robots. This measure centers on assessing the manipulating capabilities of robotic mechanisms concerning the precise positioning and orientation of end-effectors. The force transmission characteristics of a manipulator at any given posture can be geometrically represented as ellipsoids, termed “manipulability ellipsoids.” Numerous indices and measures, documented in the literature ( [4–11]), are available to articulate the kinematic capabilities of a robotic manipulator.

Manipulation tasks can be considered as a sequence of actions in Cartesian task coordinates. Nevertheless, the actual execution of a task necessitates implementing a sequence of actions in actuator coordinates, specifically joint coordinates. Within a given posture of a manipulator, certain “preferred directions” emerge for force exertion in task coordinates. Among these directions, there exist force exertion vectors that impose minimal loading on the actuators [12]. The optimal directions for force are those that require maximum force at the end-effector compared to the joints torques. Configurations that require lower torques (or forces) at the joints are preferable, as they result in a higher mechanical advantage for the robot.

Through the manipulation of a manipulator’s posture, it is possible to modify the shape and orientation of the force ellipsoids, thereby altering the optimal directions for force control. Enhancing the effective capability of a manipulator involves adopting postures that align the optimal direction with the directions relevant to the task.

1.1. Literature review

Significant emphasis has been placed on industrial applications wherein a robot is designated with navigating environments containing obstacles to reach a specified sequence of task-points using its hand tip. The predetermined sequence for the robot to visit multiple task-points and return to the starting point is not predefined. Conversely, it is essential to consider the constraint of ensuring collision-free movements.

This problem constitutes a combination of path planning and task scheduling of robot manipulators. The problem focuses on defining the optimum joint movements so that the end-effector can complete a set of tasks according to the predefined trajectory. In the task scheduling problem, the problem involves determining the optimum sequence for a manipulator’s end-effector to visit various task-points. This problem aligns with the Traveling Salesman Problem (TSP) [13]. When integrating the TSP into robotics, the challenge escalates because the aim is to minimize the cycle time while ensuring the robot’s end-effector reaches specified task-points and avoids obstacles simultaneously. Besides, the choice of multiple solutions to the inverse kinematics problem must also be taken into consideration.

Numerous techniques have been proposed and explored in the literature ( [14–19]) for addressing point-to-point trajectory challenges encountered by robotic manipulators, with a focus on time cost considerations. The authors in ref. [14] present a planning methodology tailored for industrial robots with 6 DOF, operating within the implicit and discretized C-space. The work of ref. [15] addresses a motion planning problem where the end-effector of a robotic arm is tasked with reaching successive goal placements. The objective is to calculate a near-optimal path for the robot, ensuring that the end-effector visits each goal exactly once. This task involves the integration of two challenging subproblems: formulating a collision-free shortest path and resolving the TSP. The work of ref. [16] investigates a scheduling problem that encompasses optimal scheduling of robot tasks while simultaneously considering collision-free motion planning. The study pertains to both redundant and non-redundant robots operating within the 2D space.

The authors in ref. [17] present a novel approach to robot task planning that integrates the consideration of intricate geometric volumes with general-purpose knowledge-level planning techniques. This approach, termed the knowledge volume approach, introduces an intermediary stage between continuous robot motions and symbolic planning. The work in ref. [18] introduces a method that concurrently addresses the planning of collision-free motion and the scheduling of a time-optimal route along a designated set of task-points. The authors employ a modified genetic algorithm (GA) with specialized encoding to handle the intricacies arising from the multiplicity of robot inverse kinematics and the necessary intermediate configurations in searching for the optimal solution. For a more extensive review of the robotic task scheduling problem, interested readers are referred to ref. [19].

Considerable research has been conducted on manipulability measures with a focus on optimizing the placement of the manipulator’s path to enhance efficiency or gain advantages. In ref. [20], the authors investigate the optimal placement of the robot’s base with a focus on velocity efficiency using a velocity measure. The proposed criterion relies on the orientation of the manipulability ellipsoid relative to the path. In ref. [21], the authors introduce a method for optimizing the task placement of a serial manipulator, aiming to minimize the required joint torques utilizing the manipulator’s mechanical advantage (MMA).

In ref. [22], the authors introduce a methodology aimed at extracting optimized trajectories by leveraging the capabilities of kinematic redundancy. Within this framework, particular attention is devoted to the consideration of the force ellipsoid to ensure the stability of drilling operations. In a more recent study detailed in ref. [23], the authors study the motion planning problem for a manipulator in an environment cluttered with obstacles. The authors explore the motion planning problem for a manipulator operating in an environment characterized by obstacles. The study places special emphasis on the robot’s mobility, intricately tied to manipulability and the associated costs of joint limitations. The optimization criteria encompass manipulability and the distance to the joints’ limits. To address these challenges, the authors employ a Rapidly Exploring Random Tree, extending and optimizing it through state costs specifically tailored for manipulability.

Most of the proposed approaches solve the task-scheduling problem and motion planning as separate problems. However, in practical applications, the plan generated by the task-level planner often encounters execution challenges due to path-planning failures. Consider, for instance, a scenario where a robot is tasked with placing a book on a shelf; while the task scheduler suggests placing the book on the shelf due to available space, the motion planner may struggle to formulate a collision-free path for this action. In such instances, the task scheduler must devise a new plan. Hence, it is imperative to address the challenges of motion planning and task scheduling concurrently.

As an extension to our already published work [16], our current research emphasis is directed toward identifying the optimal collision-free path planning while concurrently maximizing the MMA. The goal is to ascertain the optimal sequence of task-points for the robot in the presence of obstacles. Typically, this problem is decomposed into two distinct computationally challenging tasks: Task scheduling, closely aligned with the TSP, and path planning. Scheduling involves establishing the task-point sequence to minimize cycle time, while path planning entails determining an efficient and collision-free path between two successive task-points. In this study, we integrate these two NP-hard problems for simultaneous resolution, taking into account the MMA.

1.2. Motivation and contribution

Minimizing cycle time, avoiding collisions, and maximizing manipulability are the primary considerations for applications in cluttered environments where increased capability for force exertion at the end-effector is critical. The primary focus of this paper is to address the multi-objective optimization problem posed by these challenges. Notably, within the literature, there appears to be a gap in works that specifically investigate this problem within the context of manipulability. A plausible explanation for this gap is the inherent difficulty in simultaneously integrating the two problems, where the planner must consider the manipulability of the manipulator, resulting in a highly challenging NP-hard problem.

This paper proposes a method that is general for redundant and non-redundant robots operating in 2D or 3D environments. The distinction between 2D and 3D environments is that 2D environments offer simplicity and computational efficiency, whereas 3D environments provide a more realistic representation of the physical world. The optimization approach introduced in this work concerns the optimal sequence of the manipulator’s end-effector that minimizes the cycle time and simultaneously maximizes the mechanical efficiency considering the configurations multiplicity. The mechanical efficiency is expressed through MMA to apply force at the end-effector ensuring low joint torques.

The main innovative issues of this paper are summarized below:

• • The proposed approach is capable of handling both obstacle avoidance and task scheduling problems simultaneously, in the condition of the mechanical efficiency considering the configurations multiplicity.

• • The proposed approach is applicable to both redundant and non-redundant manipulators having finite or infinite possible configurations at each task-point.

• • The proposed approach can be applied in either 2D or 3D environments cluttered with obstacles.

The proposed optimization approach for robotic manipulators presents significant practical implications across diverse industrial applications. For instance, in tasks such as grinding and deburring, where force exertion at the end-effector is critical for enhancing mechanical advantage, optimizing cycle time can lead to increased efficiency and productivity on the production line. Additionally, in material handling and sorting operations within warehouses and logistics centers, faster cycle times enable quicker and more accurate picking and placing of items, thereby improving overall throughput. Similarly, in assembly processes, pick-and-place operations, and packaging facilities, minimizing cycle time facilitates faster production rates, reduced manufacturing costs, and meeting tight production deadlines. Moreover, in painting and coating applications such as automotive manufacturing, where precision and speed are paramount, optimizing cycle time enhances throughput and efficiency, ultimately contributing to improved profitability. By addressing these diverse tasks and applications, the proposed optimization approach offers practical solutions to enhance the performance and efficiency of robotic manipulators across a wide range of industrial scenarios.

In practical applications such as assembly, where sequence constraints may dictate the order of task execution, our optimization framework can easily accommodate such constraints while minimizing cycle time and optimizing mechanical advantage across various manipulator configurations (please refer to ref. [24] for more details). This flexibility ensures the adaptability of our approach to a wide range of industrial tasks.

2. Problem statement

Consider a robotic manipulator that is requested to operate in a 2D (or 3D) environment confined by static obstacles characterized by known arbitrary shape, size, and location, as illustrated in Figure 1. The primary objective for the robot’s end-effector is to traverse a specified set of M task-points within this environment, ensuring each task-point is visited exactly once. In this study, our emphasis lies exclusively on the kinematic aspects of the robotic manipulator, disregarding dynamic considerations. This strategic decision aims to simplify the optimization process and alleviate computational complexity, ensuring practical feasibility for real-time implementation in industrial environments.

Figure 1. A robotic manipulator with $n$ joints in a 2D environment cluttered with obstacles assigned to reach M task-points.

Without accounting for the dynamic properties, the robot’s kinematic model determines its motion, while being restricted by both the obstacles within the work cell and the torque limits of the actuators. Additionally, the optimization of the total cycle time does not take into consideration the time spent by the robot at each task-point for performing operations, since this duration depends on the task process and can be regarded as fixed and known.

Under the above analysis and assumptions, the aim is threefold:

1. A. To determine the end-effector’s feasible tour that minimizes the cycle time.

2. B. To determine an end-effector’s path to ensure safe movement of the manipulator.

3. C. To achieve mechanical advantage at the manipulator’s end-effector during the traversal of the task-points.

The first optimization criterion centers on addressing the TSP within robotic applications, aiming to establish the optimal sequence among task-points by minimizing time rather than distance. To adapt TSP to Robotics, consider a robotic manipulator with n rotational joints in a 2D (or 3D) Cartesian space designated to visit M task-points, each defined by known coordinates. The determination of the optimal cycle time involves accounting for the multiplicity of robot configurations corresponding to each task-point, along with the presence of obstacles within the environment. Consequently, selecting the robot’s configuration depends on both the criterion for optimal cycle time and the characteristics of obstacles, including shape and location, which limit the available configuration choices.

The total cycle time $t_{c}$ required for the manipulator to travel between M designated task-points and return to the initial task-point is expressed as:

(1) \begin{align} t_{c}=\sum _{i=2}^{M\left(1+\gamma \right)}t_{i}+ {\max}_{j}\left(\frac{\left| \boldsymbol{\theta }_{j1}-\boldsymbol{\theta }_{j\left[M\left(1+\gamma \right)\right]}\right| }{\dot{\theta }_{j}}\right) \end{align}

in which the first term $(\sum _{i=2}^{M(1+\gamma )}t_{i})$ expresses the time required by the manipulator for its transition between the successive configurations, and the second term $\left(\frac{\left| \boldsymbol{\theta }_{j1}-\boldsymbol{\theta }_{j\left[M\left(1+\gamma \right)\right]}\right| }{\dot{\theta }_{j}}\right)$ expresses the time required for its transition from the last configuration back to the initial one, where,

• • γ is the number of intermediate configurations along a specific end-effector’s path between two successive task-points [15] and

• • $t_{i}$ is the time needed by the manipulator to travel from the point $(i-1)$ to the point $i$ is given by,

(2) \begin{align} t_{i}= {\max}_{j}\left(\frac{\left| \boldsymbol{\theta }_{ji}-\boldsymbol{\theta }_{j\left(i-1\right)}\right| }{\dot{\theta }_{j}}\right) \end{align}

where

• • $\boldsymbol{\theta }_{ji}$ is the $j^{th}$ -joint ( $j=1,2,\ldots, n$ ) displacement for the $i^{th}$ ( $i=1,2,\ldots, M$ ) end-effector location and

• • $\dot{\theta }_{j}$ is the average velocity of the $j^{th}$ joint considered as constant.

The second optimization criterion involves identifying a safe path for the robotic manipulator during its transition from one task-point to another. To account for the manipulator’s shape and ensure an obstacle-free trajectory for the end-effector, we designate a set of random points $l_{v}^{j}, v=1,\ldots, N$ and $j=1,\ldots .,n$ on the surface of each manipulator’s link, where $N$ represents the total number of points on each link and $n$ is the total number of the manipulator’s links.

Following the methodology presented in ref. [25], each point $l_{v}^{j},$ traces a path in robot’s workspace $\mathcal{W}\equiv \mathbb{R}^{2}$ or $\mathbb{R}^{3}$ . A collision-free path $l_{v}^{j},(s)$ should be searched in the “flat” areas of the Bump-Surface. The image $S(l_{v}^{j} (s))$ that lies on the bumps of $S$ yields a path $l_{v}^{j}(s)$ that avoids penetrating the obstacles in $\mathcal{W}$ . Thus, the goal for collision avoidance entails a path $l_{v}^{j}(s)$ on $S$ with minimal flatness H, which is described by,

(3) \begin{align} H=\max _{\boldsymbol{\theta }_{\textit{total}}} \left(S_{w}\left(l_{1}^{1}\left(s\right)\right),\ldots, S_{w}\left(l_{N}^{1}\left(s\right)\right),\ldots, S_{w}\left(l_{N}^{n}\left(s\right)\right)\right) \end{align}

with respect to the joint variables $\boldsymbol{\theta }_{\textit{total}}$ , where,

• • if $\mathcal{W}\equiv \mathbb{R}^{2}$ , then $\boldsymbol{\theta }_{\textit{total}}=(\boldsymbol{\theta }_{0},\ldots, \boldsymbol{\theta }_{m},\ldots, \boldsymbol{\theta }_{M+(M-1)\gamma })$ and $\boldsymbol{\theta }_{m}\boldsymbol{\epsilon }\mathbb{R}^{n}$ for a planar manipulator with $n$ links and,

• • if $\mathcal{W}\equiv \mathbb{R}^{3}$ , then $\boldsymbol{\theta }_{\textit{total}}=(\theta _{0},\theta _{1},\ldots, \theta _{m},\ldots, \theta _{M+(M-1)\gamma })$ and $\theta _{m}\epsilon \mathbb{R}^{6}$ for a Programmable Universal Manipulation Arm (PUMA) manipulator,

The third optimization criterion relates to MMA. MMA encompasses information related to the robot’s ability to exert force at the end-effector in a specific direction, providing a quantification of the robot’s force efficiency along that particular vector. MMA relies on both the configuration and the end-effector force vector. A higher MMA value indicates a relatively high end-effector force in comparison to the joint torques. Conversely, a lower MMA value corresponds to a requirement for relatively high joint torques to achieve high end-effector force. Thus, the minimum MMA represents the most unfavorable force/torque ratio along the path. Consequently, by maximizing the worst force/torque ratio, MMA is consistently maintained at a high level along the path.

The expression for the minimum MMA value can be articulated as follows:

(4) \begin{align} {\textit{min}}(MMA)={\textit{min}} \{(r_{m})_{i}\},\ i=1,\ldots, M \end{align}

and

(5) \begin{align} r_{m}=\sqrt{\frac{ {\boldsymbol{f}} _{m}^{T} {\boldsymbol{f}}_{m}}{\boldsymbol{\tau }_{m}^{T}\boldsymbol{\tau }_{m}}} \end{align}

where,

• • ${\boldsymbol{f}}_{m}$ represents the weighted vectors of end-effector force and

• • $\boldsymbol{\tau }_{m}$ represents joint torque.

The objective of this work is threefold: (a) the minimization of the overall cycle time $t_{c}$ (Eq.(2)), (b) the minimization the flatness $H$ (Eq.(3)), and (c) the maximization of the $min (MMA)$ (Eq.(4)). Given the conflicting nature of these three objectives, it is imperative to appropriately combine the objective functions to address the overall problem.

For non-redundant robots, where the possible configurations at specific points can be determined by the inverse kinematics, the objective function is expressed as a ratio of these three objectives. For redundant robots, where direct kinematics is applied to determine potential (infinite) configurations at the points, an additional parameter to account for the position error $(D)$ at the end-effector should be considered. Therefore, the objective function is formulated as:

(6) \begin{align} \min _{\theta } \left(E \right)=\begin{cases} \min _{\theta }\left(\frac{t_{c}\left(\boldsymbol{\theta }_{\textit{total}}\right)e^{H\left(\boldsymbol{\theta }_{\textit{total}}\right)}}{MMA}\right)\!,\ for\ non-\textit{redundant}\ \textit{manipulators}\\ \min _{\theta }\left(\frac{t_{c}\left(\boldsymbol{\theta }_{\textit{total}}\right)e^{H\left(\boldsymbol{\theta }_{\textit{total}}\right)}e^{D\left({\boldsymbol{\theta }_{\textit{total}}}\right)}}{MMA}\right)\!,\ for\ \textit{redundant}\ \textit{manipulators} \end{cases} \end{align}

where $D=\| {\boldsymbol{p}}_{c}-{\boldsymbol{p}}_{d}\|$ is characterized as the position error between the current position ${\boldsymbol{p}}_{c}$ of the manipulator’s end effector and the desired position ${\boldsymbol{p}}_{d}$ ( ${\boldsymbol{p}}_{c}, {\boldsymbol{p}}_{d}\in [0,1]^{2}$ ). Additionally, $D(\boldsymbol{\theta }_{\textit{total}})$ represents the minimum distance between the manipulator’s links and the obstacles.

3. Preliminaries

3.1. Theoretical background of manipulator mechanical advantage

Dubey and Luh [6] introduced the MMA as a performance measure, representing the robot’s capability to exert force and moment at the end-effector. MMA is visualized through an ellipsoid termed as MMA-ellipsoid (MMAE), serving as an indicator of the robot’s capability to exert forces at various points within its workspace. A higher mechanical advantage, indicative of enhanced performance in applying forces and moments, is achieved in the direction of force and moment. Enhancing MMA in the direction of force and moment exerted by the robot at the end-effector leads to reduced joint force requirements. Enhancing the mechanical advantage is particularly recommended for applications like grinding and deburring, where increased capability for force exertion at the end-effector is crucial.

MMA delineates the relationship between the end-effector’s force and the joint torques contingent upon the robot’s configuration and the direction of the end-effector force vector. A high MMA value implies a relatively high end-effector’s force compared to the joint torques, while a low MMA value necessitates relatively high joint torques to succeed a high end-effector’s force. In other words, the minimum MMA signifies the worst ratio and by maximizing the worst ratio, the MMA is consistently maintained at a high level across all the visited task-points.

According to Dubey and Luh [6], MMA is defined as the ratio of the norm of the end-effector force vector to the norm of joint torque vector, and it is denoted as $r_{m}$ . Thus,

(7) \begin{align} r_{m}=\sqrt{\frac{f_{m}^{T}f_{m}}{\tau _{m}^{T}\tau _{m}}} \end{align}

where $f_{m}$ and $\tau _{m}$ are the weighted vectors of end-effector force and joint torque, respectively.

Let $\tau$ , $f$ , and $\mathrm{J}$ be the end-effector force vector, the joint torque vector and the robot’s Jacobian matrix, respectively, the transformations $J_{m}=W_{f}^{-1/2}JW_{\tau }^{1/2}$ , $f_{m}=W_{f}^{1/2}f$ , and $\tau _{m}=W_{\tau }^{1/2}\tau$ are used, where $W_{f}\in R^{m\times m}$ and $W_{\tau }\in R^{n\times n}$ are symmetric and positive definite weighting matrices. In most instances, these will be taken as diagonal matrices for simplicity.

The joint torque vector is given by

(8) \begin{align} \tau _{m}=J_{m}^{T}f_{m} \end{align}

Substituting (2) into (1), we get

(9) \begin{align} r_{m}=\sqrt{\frac{f_{m}^{T}f_{m}}{\left(f_{m}^{T}J_{m}J_{m}^{T}f_{m}\right)}} \end{align}

If the transformed vector $f_{m}$ belongs to the null space of $J_{m}^{T}$ , the torques generated at the joints reduce to zero and r_m tends to infinity. If $\boldsymbol{u}_{\boldsymbol{m}}$ is defined as a unit vector oriented in the direction of $\boldsymbol{f}_{\boldsymbol{m}}$ , then $\boldsymbol{r}_{\boldsymbol{m}}$ can be reformulated as:

(10) \begin{align} \boldsymbol{r}_{\boldsymbol{m}}=\mathbf{1}/\boldsymbol{u}_{\boldsymbol{m}}^{\boldsymbol{T}} \boldsymbol{J}_{\boldsymbol{m} }\boldsymbol{J}_{\boldsymbol{m}}^{\boldsymbol{T}} \boldsymbol{u}_{\boldsymbol{m}} \end{align}

where

(11) \begin{align} \boldsymbol{u}_{\boldsymbol{m}}=\boldsymbol{f}_{\boldsymbol{m}}/\boldsymbol{f}_{\boldsymbol{m}}^{\boldsymbol{T}} \boldsymbol{f}_{\boldsymbol{m}} \end{align}

The singular value decomposition of $J_{m}$ can be written as:

(12) \begin{align} J_{m}=\boldsymbol{S}\boldsymbol{\Sigma }_{\boldsymbol{m}}\boldsymbol{T}^{\mathrm{T}} \end{align}

where $\boldsymbol{S}\in \mathbb{R}^{\boldsymbol{mxm}}$ and $\boldsymbol{T}\in \mathbb{R}^{\boldsymbol{nxn}}$ are orthogonal matrices, and $\boldsymbol{\Sigma }_{\boldsymbol{m}}\in \mathbb{R}^{\boldsymbol{mxn}}$ , $m\lt n$ , is a diagonal matrix of the following form:

(13) \begin{align} {\unicode[Arial]{x03A3}} _{m}=\left[\begin{array}{lllllll} \xi _{1} & & & & & | & \\ & \xi _{2} & & 0 & & | & \\ & & . & & & | & 0\\ & 0 & & . & & | & \\ & & & & \xi _{m} & | & \end{array}\right] \end{align}

where ξ ₁ ≥ ξ ₂ ≥ ^… ≥ ξ _m ≥ 0. The non-zero elements of Σ _m represent the singular values of J _m and their number is equal to the rank of J _m . The manipulator mechanical advantage r_m can be demonstrated to fall within the following range [26]:

(14) \begin{align} \frac{1}{\xi _{1}}\leq r_{m}\leq \frac{1}{\xi _{m}} \end{align}

The actual value of r _m is influenced not only by the robot configuration and the weighting matrices W _τ και W _f but also by the direction of the force applied by the robot end-effector. The end-points of the vectors ${\boldsymbol{r}}_{\boldsymbol{m}} {\boldsymbol{u}}_{\boldsymbol{m}}$ for a given robot configuration can be depicted as a surface (or curve for m = 2). This surface can be accurately represented by an ellipsoid with principal axes (1/ξ ₁ ) $\boldsymbol{s}_{\mathbf{1}}$ , (1/ξ ₂ ) $\boldsymbol{s}_{\mathbf{2}}$ , _… , (1/ξ _m ) $\boldsymbol{s}_{\boldsymbol{m}}$ , where $\boldsymbol{s}_{\boldsymbol{i}}$ ∈R ^m denotes the i ^th column vector of S in (12). This ellipsoid is denoted as the MMAE and both its shape and volume are contingent upon the robot configuration. In the case that one or more ξ_i are equal to zero, the manipulator mechanical advantage in the direction(s) of $\boldsymbol{s}_{\boldsymbol{i}}$ vector(s) becomes infinite. If the external force vector applied at the end-effector aligns with the direction(s) of vector(s) $\boldsymbol{s}_{\boldsymbol{i}}$ corresponding to zeros ξ_i, then the resulting torques at the joints will be null.

A redundant robot provides the capability to derive diverse MMAEs for the same end-effector position through self-motion. The overall ability of a redundant robot to exert force at the end-effector in a desired direction can be enhanced by reshaping and reorienting MMAE.

As a general remark, the mechanical advantage becomes essential for performance, especially in cluttered environments, where obstacles may impede the motion of robotic manipulators. This performance measure determines the manipulator’s ability to exert force effectively. A higher mechanical advantage enables the manipulator to move in cluttered environments by optimizing motion to avoid obstacles and achieve task objectives. The consideration of the manipulability index is essential for assessing the manipulator’s performance in cluttered environments and optimizing its capabilities to perform tasks efficiently.

3.2. An introduction to the bump-surface concept

The Bump-Surface concept proves to be a powerful tool for representing the robot’s workspace utilizing a unified mathematical entity [27]. As a global method, this concept characterizes the robot’s workspace by employing a B-Spline surface incorporated within a higher dimensional space. The Bump-Surface concept operates under the assumption that the environment of robot is confined within a region denoted as $[0,1]^{K}, K=2,3$ , which represents the normalized space. This space is discretized into evenly spaced subintervals along its $n$ orthogonal directions, thereby creating a grid of points ${\boldsymbol{p}}\epsilon [0,1]^{K+1}, K=2,3$ . The $K+1$ coordinate of each grid point ${\boldsymbol{p}}\epsilon (0,1],$ if ${\boldsymbol{p}}$ lies within an obstacle, and it is equal to 0, otherwise. For example, in a 2D environment $(K=2)$ , a 2D B-Spline surface is depicted within 3D Euclidean space, as illustrated in Figure 2.

Figure 2. (a) A 2D environment with two rectangular obstacles. (b) The corresponding Bump-Surface.

A collision-free path needs to be identified within the “flat” regions. Choosing a path that “ascends” the bumps of the surface leads to a path that traverses the obstacles in the initial robot’s workspace (Figure 3).

Figure 3. (a) An example two paths on the Bump-Surface, the path with red color “climbs” the bump while the curve with yellow color is collision free. (b) Another point of view.

Figure 4. A feasible chromosome for a non-redundant manipulator indicating that the robot first visits the task-point three with a configuration denoted by the alleles (1 0 1), then visits the task-point one with a configuration denoted by the alleles (111) etc. The second segment of the chromosome delineates the manipulator’s configuration at the task-points, where each three-digit allele of (000, 001, 010, …, 111) designates one out of eight configurations of the manipulator.

Figure 5. A feasible chromosome for a redundant manipulator.

Figure 6. (a) Robot’s configurations at the task-points. (b) The manipulator’s end-effector trace while moving in 2D environment.

Figure 7. (a) Minimal distance between the robot’s end-effector and the nearest obstacle during its motion from task-point to task-point. (b) Normalized manipulability index during task.

Figure 8. (a) A representative example of manipulator’s workspace. (b) Another point of view.

Figure 9. (a) The proposed solution. (b)-(f) Some points of view.

Figure 10. (a) Minimal distance between the robot’s end-effector and the nearest obstacle during its motion. (b) Normalized manipulability index during task.

Figure 11. The CPU time versus the number of task-points for the 1st scenario.

Figure 12. The CPU time versus the number of task-points for the 2nd scenario.

4. The optimization search algorithm

Multi-goal motion planning poses a challenge as an NP-complete optimization problem. GAs [28, 29] emerge as a robust optimization tool for addressing problems in high-dimensional search spaces when conventional techniques prove too intricate or time-consuming. The essential components of GAs are elucidated in the subsequent sections.

The representation mechanism: The choice of an encoding mechanism is crucial, with integer encoding proving especially advantageous in cases where binary encoding would require specialized repair algorithms. In this regard, integer encoding aligns well with the TSP. Conversely, binary or floating encoding is more suitable for handling the multiplicity of robot configurations at task-points depending on whether the robot exhibits redundancy or not. As a result, a mixed encoding scheme is preferable. This proposed representation scheme reduces the required number of genes to encompass robot configurations at the task-points. As a result, the proposed chromosome is comprised of three segments:

Segment # 1: utilizes integer encoding to represent the sequence of the robot’s movement between the task-points (integer encoding).

Segment # 2: represents the configurations corresponding to the task-points specified in Segment#1 (binary or floating encoding for non-redundant and redundant robots, respectively).

Segment # 3: expresses the intermediate configurations between successive task-points, as outlined in Segment#1 (floating encoding).

When considering the two distinct cases separately (non-redundant and redundant robots), it becomes apparent that a distinct representation scheme is required to accommodate the different characteristics of each robot type. This distinction is necessary since the possible configurations at each task-point for non-redundant robots are known and finite, whereas for redundant robots, the possible configurations at each task-point are infinite. For the case of non-redundant robots, the binary encoding is employed to express the finite configurations corresponding to the points, while for the case of redundant robots, the floating encoding is used to express the joint angles constituting the configurations at the points. It should also be noted that the manipulator transitions between successive points on a path are determined by linear interpolation between two successive configurations.

For example, let a three-DOF non-redundant manipulator operating in the 3D space that is assigned to visit four task-points through a path defined by $\gamma =2$ intermediate points between successive task-points. Assuming that the manipulator can reach each task-point with eight different configurations, a feasible chromosome can be formulated as follows (Figure 4):

Now, let a redundant manipulator with three rotational joints, that is requested to reach $M=4$ task-points in a 2D workspace through a path defined by γ $=2$ intermediate points. A plausible chromosome can be formulated accordingly (Figure 5):

where TP1, TP2, TP3, and TP4 are the task-points 1,2,3, and 4, respectively, and IC is the intermediate configuration corresponding to the successive task-points.

The evaluation mechanism assesses the quality (i.e. the fitness) of each chromosome within the population and is given by:

(15) \begin{align} \textit{fitness}=\frac{1}{E} \end{align}

Genetic operators play a crucial role in the proposed GA. The reproduction process employs the roulette wheel scheme, where chromosomes are chosen for replication with probabilities proportional to their fitness. Following reproduction, crossover serves as a recombination operator. In this work, the order crossover is employed for the integer encoding, while a one-point crossover is applied to both the binary and floating encoding. Mutation is introduced to infuse new genetic material into the population, preventing premature convergence to local minima. For the integer encoding, the inversion mutation operator is utilized. For the binary encoding, the mutation operator involves altering a randomly selected gene with a digital value of “0” to “1” and vice versa. For the floating encoding, the mutation operator is implemented to change a random gene to another lying within the search space.

5. Simulation results

To evaluate the performance of the proposed approach, two scenarios have been carried out. The first scenario, which considers a redundant robot operating in a 2D environment, and the second scenario, which considers a non-redundant robot operating in a 3D environment, are indicatively presented.

In the first scenario , we consider that a three-dof manipulator is requested to visit a set of task-points in an environment that is cluttered with convex and non-convex polygonal obstacles. In this scenario, a three-dof manipulator with rotational joints is requested to approach 10 task-points. The robot’s environment contains four polygonal obstacles and the task-points are located on vertices and edges of the obstacles. Figure 6(a) presents the robot’s configurations at the task-points and the optimum sequence of the task-points provided from the proposed approach is as follows: 7 – 6 – 5 – 1 – 3 – 4 – 9 – 2 – 8 – 10. Figure 6(b) presents the end-effector’s trace while the robot is moving in the 2D environment between the task-points (the black triangle shows the robot’s base). The minimum distance between the robot’s end-effector and the obstacles while moving in the 2D environment is presented in Figure 7(a). Figure 7(b) presents the performance of the manipulability index, while the manipulator’s end-effector follows the proposed trajectory. It is noticed that the manipulability index takes small values while the manipulator is moving close to the obstacles.

In a second scenario , we assume that a PUMA manipulator is requested to accomplish a similar task. In both simulations, the proposed approach provides a trajectory for the manipulator’s end-effector while simultaneously the manipulability index is high even avoiding an obstacle. In this experiment, the robotic arm (Puma 762) is required to perform its task in a 3D workspace. The manipulator is requested to visit seven task-points in an environment that is cluttered with four convex and non-convex polyhedral obstacles. An illustrative figure of the manipulator’s workspace is shown in Figure 8. Here, the obstacles are represented by red and dark green, and the gray area shows the operation space. The task-points are represented by orange points and are placed on some of the vertices of the obstacles. The proposed solution is presented in Figure 9(a)-(f) shown from different points of view, where the manipulator’s end-effector is requested to visit the task-points in the following order: 1 – 2 – 5 – 3 – 4 – 7 – 6. In Figure 9, the blue dots represent the end-effector’s trace.

To demonstrate the efficacy of the proposed methodology, the calculation of the minimum distance between the robot’s end-effector and obstacles during movement in the 3D environment is conducted and presented in Figure (a). It is noticed from Figure 10(a) that the distance takes the value 0 only on the task-points and takes values other than zero when the robot is moving between the task-points. Figure 10(b) presents the performance of the manipulability index, while the manipulator’s end-effector follows the proposed trajectory. It is observed that the manipulability index exhibits small values when the manipulator is in close proximity to obstacles.

A noteworthy insight into problem complexity arises from the variability in calculation time concerning the number of task-points. Numerous experiments were executed, utilizing a three-DOF manipulator navigating a 2D environment with four obstacles. The task assigned was to reach a specified number of task-points while ensuring the minimum cycle time and avoiding obstacles. To evaluate how the increasing number of task-points affects computational time, a series of experiments were conducted involving a Puma manipulator working in a 3D environment with four obstacles and assigned to reach a specific number of task-points. Figure 11 and Figure 12 illustrate the relationship between computational time and the number of task-points, suggesting that central processing unit (CPU) time experiences an almost linear increase with the growing number of task-points.

6. Conclusions

This paper introduces a novel method for determining the sequence of the task-points visited by the end-effector’s tip assuring collision-free motion amidst obstacles while maximizing force at the end-effector’s tip. To leverage the potentiality of the manipulator manipulability, the MMA serves as the performance index of the force capability. This study incorporates three optimization criteria: cycle time minimization, collision avoidance, and the manipulability index aiming to determine the optimal collision-free task sequence to account for higher mechanical advantage. The optimization is achieved through a GA integrated with the Bump-Surface concept for collision avoidance.

The proposed approach is general and applicable to both redundant or non-redundant robotic manipulators operating in 2D or 3D environments. Especially for redundant robots, the developed optimization approach offers an effective alternative to the solution of the inverse kinematics problem, providing solutions to the direct kinematics problem. Simulation experiments using a three-DOF redundant manipulator in a 2D space and a non-redundant PUMA operating in a 3D space demonstrate the efficiency and effectiveness of the proposed method.

Future work will explore the integration of dynamic analysis to account for factors such as payload variations, external disturbances, and safety considerations, offering a more comprehensive optimization framework. By incorporating dynamic properties into our optimization model, the efficiency and adaptability of robotic manipulators will be further enhanced in various industrial applications. Additionally, future research endeavors could explore the integration of roll and pitch angle constraints, acknowledging their significance in manipulator dynamics and their potential to improve the practical applicability and effectiveness of our optimization approach.