## 3 Feasible Trajectory Planning Algorithm
### Artificial Intelligence-Based Heuristic  
The \(A^{*}\) algorithm has shown strong performances in solving trajectory problems in systems such as videogames, where the overall state of the machine is not subject to the physical and temporal constraints inherent in nonholonomic systems. While classic A* methods can successfully find optimal trajectories in general cases, these trajectories may be suboptimal or infeasible for applications such as autonomous vehicles. Introducing mechanical constraints requires the penalization or favoring of specific configurations, requiring hybrid \(A^{*}\) systems to compute the cost of individual states differently.  
As demonstrated in [50], the \(A^{*}\) algorithm can achieve significant improvements in efficiency by employing an SVM as a heuristic function rather than relying on the standard Euclidean distance heuristic. In this approach, SVMs are utilized to classify different trajectories, defining a nonlinear separation hyperplane that distinguishes acceptable trajectories from nonacceptable ones.  
A key advantage of using an SVM as a heuristic in a hybrid \(A^{*}\) lies in the significant reduction of search complexity. Traditional heuristics, such as the Euclidean distance, often require the exploration of thousands of nodes in the search space, leading to increased computational time and complexity. Conversely, when an SVM-based heuristic is applied, the search space can be drastically reduced to fewer nodes, particularly when higher values of \(\gamma\) (which controls the complexity of the SVM boundary) are used [50]. This reduction occurs because \(\gamma\) is a hyperparameter that shapes the decision boundary and influences the complexity of the learned model. Specifically, \(\gamma\) determines the influence of individual data points on the decision boundary according to the following kernel formulation:  
\[K(\chi_{i},\chi_{j})=\exp\frac{-||\chi_{i}-\chi_{j}||^{2}}{2\gamma^{2}} \tag{25}\]  
The technical advantage of integrating SVMs into the the \(A^{*}\) algorithm lies, in the proposed algorithm, in bypassing the need to check the feasibility of unfeasible trajectories. Instead, the SVM provides a priori decision making for each state, thereby shortening the exploration process, through a _soft_ pruning of the search space.  
Beyond the search efficiency gains achieved by employing SVMs, the convergence properties of hybrid \(A^{*}\) algorithms are crucial for ensuring their practical applicability. To this end, this work proposes an improved hybrid A* heuristic function designed to leverage insights from a classificator that has been trained to identify the most promising (in terms of kinodynamic feasibility) trajectory segments, as detailed below. The proposed heuristics are the following:  
\[F(c_{SA},T_{AB},\mathcal{G}_{B},\mathcal{G}_{F})=f(c_{SA},T_{AB},\mathcal{G}_{ B},\mathcal{G}_{F})+k_{f}\,p(c_{SA},T_{AB},\mathcal{G}_{B})\,f(c_{SA},T_{AB}, \mathcal{G}_{B},\mathcal{G}_{F}) \tag{26}\]  
with \(k_{f}\in[0,1]\) and the prediction \(p(c_{SA},T_{AB},\mathcal{G}_{B})\in\{0,1\}\). The prediction \(p\) is the binary output of a properly trained classifier, and its value is 0 if the trajectory segment \(T_{AB}\) is classified as nonadmissible, whereas it is 1 if otherwise. The coefficient \(k_{f}\) (whose positiveness ensures the admissibility of the heuristics) is a weight factor that dictates the effect of \(p\): when \(k_{f}=0\), \(p\) does not affect the order in which adjacent nodes are explored, while \(k_{f}=1\) moves nodes with \(p=1\) to the top of the list of nodes to be explored. The following subparagraphs will focus on the way \(p\) is found.