# Multi-Objective PSO with Variable Number of Dimensions for Space Robot Path Optimization
## 2 Problem Definition  
The space robot pathfinding problem can be viewed as a search for the set of optimal turning points leading the robot safely from its starting location, \(x_{S}\), to the target location, \(x_{T}\). These TPs have to be located somewhere in the feasible decision space, \(\Omega\subset\mathbb{R}^{2}\). The bounding box surrounding all the obstacles located in the area of interest serves usually as \(\Omega\). The situation is illustrated in Figure 1.  
First, we have to clarify some assumptions that are valid throughout the whole paper:  
**Assumption 1**.: _The obstacles are represented by polygons. The \(n\)-th polygon is then a set of 2D nodes, \(\mathcal{O}_{n}\), ordered in a counter-clockwise order._  
**Assumption 2**.: _The mobile robot has a physical body, which is circumferenced by a circle of radius \(r\). All the obstacles are then enlarged by \(r\) (see shaded borders in Figure 1) so that the robot can be viewed as a single point._  
Figure 1: The illustration of the space robot path problem. Three feasible paths from the starting point, \(r_{S}\), to the target point, \(r_{T}\), form the Pareto front of the multi-objective SRPP.  
**Assumption 3**.: _The obstacles are static and their position is known._  
**Assumption 4**.: _The robot moves with a constant speed within \(\Omega\). The robot can change the direction of the movement at any time omnidirectionally._  
The problem of the robot's path through the space containing several obstacles of different polygonal shapes is then formulated as the VND MOOP as follows:  
\[\begin{split}\min_{\mathbf{u}}& f_{1}(\mathbf{u}),f_{2}(\mathbf{u})\\ \text{s.t.}&\mathbf{u}\in\Gamma\subset\mathbb{R}^{N_{ \text{d}}},\\ & N_{\text{d}}\in\mathcal{N}=\{2,4,6,\ldots,N_{\text{max}}\}.\end{split} \tag{1}\]  
Here, symbol \(\mathbf{u}\) denotes a decision space vector whose feasible space, \(\Gamma\), is a subspace of \(\mathbb{R}^{N_{\text{d}}}\). All possible values, \(N_{\text{d}}\), generate a list of feasible dimensions \((N)\) of the VND problem formulation. The symbol \(N_{\text{max}}\) denotes the largest possible dimension. In this formulation of SPRR, \(\mathbf{u}\) is formed by individual turning points, \(\mathbf{r}_{i}\), on the way from \(\mathbf{r}_{\mathcal{S}}\) to \(\mathbf{r}_{\mathcal{T}}\). The location of the \(i\)-th TP is specified by a 2D vector, \(\mathbf{r}_{i}=x_{i},y_{i}\). Thus, the DSV is a collection of TPs:  
\[\mathbf{u}=\{\mathbf{r}_{1},\mathbf{r}_{2},\ldots,\mathbf{r}_{N_{\text{d}}/2}\}. \tag{2}\]  
The path through a maze can be then constructed as a collection, \(\mathbf{p}=\{\mathbf{r}_{\mathcal{S}},\mathbf{u},\mathbf{r}_{\mathcal{T}}\}\).  
Referring to (1), the symbols \(f_{1}\) and \(f_{2}\) stand for the two considered objective functions. The first objective function minimizes the traveled Euclidean distance of the path:  
\[f_{1}(\mathbf{u})=\sum_{i=1}^{N_{\text{d}}/2+1}d\big{(}\mathbf{p}_{i},\mathbf{p}_{i+1} \big{)}, \tag{3}\]  
where \(\mathbf{p}_{i}\) is the \(i\)-th location from the path and \(d(\cdot,\cdot)\) denotes the Euclidean distance between two locations. The second objective function takes the complexity of the path into consideration:  
\[f_{2}(\mathbf{u})=||\mathbf{u}||/2, \tag{4}\]  
where \(||\cdot||\) denotes the length of the vector. Thus, \(f_{2}\) is a discrete objective function and minimizes the number of TPs. There are three candidate solutions: \(\mathbf{u}_{1}\) (green curve), \(\mathbf{u}_{2}\) (blue), and \(\mathbf{u}_{3}\) (red) in Figure 1. These three candidate solutions have 5, 3, and 1 TPs, respectively, which results in DSV dimensions \(N_{\text{d}}=10\), 6, and 2, respectively. It should be noted that any other objectives could be added to the problem formulation (1), e.g., the maximization of a minimal distance of the considered path towards any of the obstacles. For the sake of clarity of the shown results, we stick to the two-objective formulation in this paper.