\section{Conclusion}

We presented a self-supervised traversability prediction system for autonomous navigation of wheeled robots in unstructured outdoor environments. Our approach uses a modular architecture that combines traversability prediction using a convolutional neural network that fuses RGB and depth inputs and known kinodynamic model to autonomously navigate in a variety of outdoor environments. We validated our method in different terrains and show better navigation performance than other state-of-the-art approaches. In addition, we demonstrate that our method can overcome limitations present in classical approaches due to the lack of semantic understanding, such as in the avoiding snow. We hope our work leads to further research in this area thereby enabling field robots to navigate without predefined waypoints in unstructured outdoor environments.
\section{Experimental Results}

In this section we present the experimental results from different environments. We perform experiments in environments that are similar to the training dataset (forests) but far from the location where we collected the training dataset. We also show generalization experiments in environments that are distinct from the ones present in the training data. We compare our method against baselines to show the effectiveness of our presented method in a variety of scenarios.

\begin{figure}[htpb]
    \centering
    \includegraphics[trim={0cm 3cm 0cm 3cm}, clip, width=0.98\linewidth]{figures/dataset_images.pdf}
    \caption{Sample traversability estimations projected onto input images. Darker areas represent lower estimated traversability, while brighter areas show higher estimated traversability.}
    \label{fig:dataset}
\end{figure}

\subsection{Traversability Predictions}

Using RGB and depth modalities as input, we found that TravNet is successful in predicting traversability for a variety of obstacles. Figure \ref{fig:net-outputs} shows a variety of terrain examples in which TravNet was used to predict the traversability coefficients.

\begin{figure}[thpb]
    \begin{subfigure}{.48\linewidth}
        \includegraphics[width=\linewidth]{figures/net_output1.jpg}
        \caption{}
        \label{fig:net-outputs-a}
    \end{subfigure}
    \hfill
    \begin{subfigure}{.48\linewidth}
        \includegraphics[width=\linewidth]{figures/net_output2.jpg}
        \caption{}
        \label{fig:net-outputs-b}
    \end{subfigure}

    \begin{subfigure}{.48\linewidth}
        \includegraphics[width=\linewidth]{figures/net_output3.jpg}
        \caption{}
        \label{fig:net-outputs-c}
    \end{subfigure}
    \hfill
    \begin{subfigure}{.48\linewidth}
        \includegraphics[width=\linewidth]{figures/net_output4.jpg}
        \caption{}
        \label{fig:net-outputs-d}
    \end{subfigure}
    \caption{Examples of TravNet inputs in the left images and outputs in the right images. High pixel intensity indicates high traversability value. The examples show \subref{fig:net-outputs-a} a tree trunk, \subref{fig:net-outputs-b} a concrete block, \subref{fig:net-outputs-c} a bicycle rack with a concrete path at the front, and \subref{fig:net-outputs-d} flat grass terrain.}
    \label{fig:net-outputs}
\end{figure}

In addition, we show that TravNet is able to predict semantic information that would not be possible with only geometric information. Fig. \ref{fig:snow-terrain} shows an example of snow traversability prediction. Such prediction would be problematic for a sensor that can only capture geometric measurements, since the height and texture are similar to regular terrain. However, our model is able to predict that snow is less traversable than grass, and we show that such semantic understanding is conserved with the addition of a geometric modality (depth camera).

Although the use of TravNet without the depth modality is possible, we noticed the depth measurement helps with generalization to unseen environments. This improvement is noticeable on environments with higher numbers of geometrical obstacles, such as a wall with different textures and colors from the ones seen in the training dataset.

\begin{figure}[thpb]
    \centering
    \includegraphics[trim={0cm 5cm 0cm 6cm}, clip, width=0.98\linewidth]{figures/snow_terrain.pdf}
    \caption{The left image shows snow terrain that would not be identified using only geometric methods. The center image shows predicted traversability using only RGB input. The right image shows the prediction using RGB and depth images as input.}
    \label{fig:snow-terrain}
\end{figure}

\subsection{Comparison with Baseline Approaches}

We compare our approach (WayFAST) with BADGR, a state-of-the-art learning based approach presented in \cite{kahn2021badgr}. In addition, we also compare against 2 other baselines - 1. a naive method that blindly follows the goal (Blind Pursuit) using the same kinodynamic model and MPPI used in WayFAST but disregarding the traversability map, 2. a LiDAR-based algorithm that generates a traversability map according to geometric obstacles. Both Blind Pursuit and the LiDAR-based method use our same control framework, with the only modification being the perception system. We specify a point goal location and initially position the robot to face the opposite direction for all experiments.

\begin{figure}[htp]
    \centering
    \includegraphics[width=0.98\linewidth]{{figures/baselines.pdf}}
    \caption{Comparison between WayFAST (ours) and baselines. The left image shows the environment and a path the robot would need to traverse to reach the goal. Baselines include BADGR \cite{kahn2021badgr}, a LiDAR-based method, and Blind Pursuit without any use of traversability.}
    \label{fig:comparison-badgr}
\end{figure}

Table \ref{table:forest} shows our results in a forest-like environment, where WayFAST was able to reach the goal as many times as the LiDAR baseline. It is important to note that LiDAR has a 270 degree field-of-view, while WayFAST only uses a camera with a 69 degree field-of-view, allowing the LiDAR baseline to provide a larger set of path solutions. We can also conclude, since the LiDAR baseline uses all of the components from WayFAST (i.e., the kynodynamic model, model predictive controller, and state estimator), similar performance could be obtained for WayFAST with a wider field-of-view. The blind pursuit baseline always crashed into an obstacle or getting stuck in untraversable areas. BADGR was able to navigate for a long period but never reached the goal. It could be because BADGR learns not only the traversability representation but also the robot's dynamic model and our dataset was not rich enough for the neural network to properly learn the necessary dynamics. In addition, WayFAST uses depth and skip connections, which can help in the learning process for small datasets.

\begin{table}[th]
\centering
\begin{tabular}{|c|c|c|c|}
\hline
\multicolumn{1}{|l|}{} & \textbf{Total tries} & \textbf{Successful runs} & \textbf{Success rate} \\ \hline
\textbf{WayFAST}       & 5                    & 4                        & 80\%                  \\ \hline
\textbf{BADGR}         & 5                    & 0                        & 0\%                   \\ \hline
\textbf{LiDAR-based}   & 5                    & 4                        & 80\%                  \\ \hline
\textbf{Blind Pursuit} & 5                    & 0                        & 0\%                   \\ \hline
\end{tabular}
\caption{Summary of experiments in a forest-like environment, where our approach (WayFAST) is comparable to a LiDAR baseline while outperforming the other two baselines.}
\label{table:forest}
\end{table}

\subsection{Comparison with Classical Geometric Navigation}

In order to show that geometric information is not enough for unstructured outdoor environments, we performed additional experiments comparing our proposed approach to LiDAR-based navigation. We tested both methods in areas with snow, and as shown in Fig. \ref{fig:comparison-lidar}, LiDAR was never able to reach the goal since it always got stuck in snow. This experiment shows that WayFAST was able to perceive the snow as an untraversable area and therefore safely avoid it to reach the goal. As shown in Fig. \ref{fig:comparison-lidar}, in four of the five experiments, WayFAST safely reached the goal. In the other experiment, WayFAST reached a location close to the goal but got stuck along the way. The LiDAR-based geometric method was not able to perceive the snow and therefore failed to navigate early in its trajectories.

\begin{figure}[htp]
    \centering
    \includegraphics[trim={1.2cm 0cm 1.2cm 0cm}, clip, width=1.0\linewidth]{figures/snow_experiment.pdf}
    \caption{Comparison between WayFAST and LiDAR navigation on snow terrain (snow not captured by the overhead satellite image). The left image shows how navigation fails on snow when using the LiDAR-based method.}
    \label{fig:comparison-lidar}
\end{figure}

\subsection{Generalization for Unseen Environments}

We tested our method for generalization on a very different environment from the one in the dataset. We chose an urban environment with brick walls and narrow spaces, which can be mostly represented as simple geometric obstacles. Figure \ref{fig:generalization} shows that our method can generalize well to such environments, despite being trained on a dataset that does not include representative images. Our hypothesis is that depth as an additional input modality assists in generalization to avoid geometric obstacles in new environments different from the training set.

\begin{figure}[htp]
    \centering
    \includegraphics[trim={0cm 1.2cm 0cm 2cm}, clip, width=1.0\linewidth]{figures/bell_tower.pdf}
    \caption{Left image shows WayFAST starting from eight different points with same goal. The longest path presented in the left image is due to a snow patch between the starting point and the building (not captured in satellite image). Center image presents BADGR \cite{kahn2021badgr} and the  right image shows LiDAR-based navigation starting from five different locations with same goal.}
    \label{fig:generalization}
\end{figure}

\subsection{Navigation with Only RGB Data}

We tested our method with only RGB data as input for TravNet removing the branch responsible for encoding depth information. This test was performed in Puerto Rico in a different scenario from the training dataset. Figure \ref{fig:coconut-experiment} shows that WayFAST was able to successfully navigate on a challenging outdoor environment even with only RGB input. We performed five runs starting from the same location and with the same goal. The robot was able to complete all five runs without getting stuck or colliding into obstacles.

\begin{figure}[htp]
    \centering
    \includegraphics[trim={1.4cm 0cm 1.4cm 0cm}, clip, width=1.0\linewidth]{figures/beach_experiments.pdf}
    \caption{Experimental results in coconut plantation without depth information. Left image shows the terrain.}
    \label{fig:coconut-experiment}
\end{figure}

Figure \ref{fig:snow-terrain} shows a test in uneven terrain where only RGB was used as input. Also the environment was different from the one present in the dataset. We started the robot at different locations and evaluated if the robot could avoid depressions and obstacles. Out of four runs, the robot arrived close to the goal three times and got stuck in the soil in one run.

\begin{figure}[htp]
    \centering
    \includegraphics[trim={3cm 0cm 3cm 0cm}, clip, width=0.99\linewidth]{figures/puerto_rico_uneven_terrain.pdf}
    \caption{Experimental result on uneven terrain. The left image shows example depressions and unevenness in the terrain. The right image shows paths for the four runs.}
    \label{fig:uneven-terrain}
\end{figure}

\subsection{Limitations and Failure Modes}

From our experiments, we found that a major limitation was the camera's field-of-view. Since the camera used in the experiments has a narrow field-of-view, and the RealSense depth measurements have only a short 5 meter range, the navigation algorithm was not able to plan for long horizons and explore a large variety of paths. The model predictive controller is constrained to find paths in the camera's field-of-view, and therefore, find a minimal cost for that space. With a reduced space for minimization, the robot was not able to avoid large objects or plan around large untraversable areas.

In addition, snow is an example of a situation that may be traversable or untraversable, depending on the softness and depth, which can change with weather. However, in both cases, the snow often has the same visual appearance. We found that even after adding snow data to the dataset, the traversability for snow could vary depending on location, and other sensor modalities may therefore be necessary to safely detect when snow is traversable or untraversable.
\section{Introduction}

Waypoint-based path programming methods for field robots are slow, ineffective, and cumbersome in outdoor and unstructured environments. This has become a major barrier for deployment of field robots in wooded, obstacle prone, or poorly mapped areas, such as remote outposts, contested areas, forests, and agricultural fields. The user has to plan the path around all possible obstacles, including rocks, trees, holes, etc. which is impractical.

As such, algorithms for traversability determination have remained an active area of research (see Section II Related Work). The main challenge here is that heuristics-based methods are difficult to design and often lead to false positives in outdoor environments where geometric traversability is not always equivalent to actual traversability. For example, tall grass could be detected by LiDAR or tactile sensors as geometric obstacles, when in fact, these are obstacles that the robot could  traverse through. Moreover, in addition to predicting obstacle free paths, the traversability system should also predict expected traction coefficient to ensure successful autonomous navigation \cite{ding20222,kayacan2018embedded}.

\begin{figure}[t]
    \centering
    \includegraphics[trim={0cm 3cm 0 7cm}, clip, width=1.0\linewidth]{figures/WayFAST2.jpg}
    \caption{We present WayFAST, a \textbf{Way}point \textbf{F}ree \textbf{A}utonomous \textbf{S}ystem for \textbf{T}raversability prediction that learns to predict obstacle free paths of good traction outdoors.}
    \label{fig:wayfast}
\end{figure}

Learning-based methods to determine traversability based on navigation experiences could lead to more robust navigation by avoiding heuristics \cite{howard2006towards,kahn2021badgr,kim2006traversability,wellhausen2020safe,miki2022learning}. However, learning traversability and robot kinodynamic models together, as done in \cite{kahn2021badgr,loquercio2018dronet,chiang2019learning}, may lead to oscillatory paths. Furthermore, coupling the problem of learning traversability and robot model is unnecessary because kinodynamic models for wheeled robots are well known, as is evident by success of Model Predictive Control (MPC) \cite{kayacan2018embedded,lindqvist2020nonlinear,sun2019tracking} or Model Predictive Path Integral (MPPI) control \cite{williams2017model,williams2016aggressive,gandhi2021robust}. Existing methods have also used heuristics such as collisions, robot attitude, or bumpiness to determine traversability labels. However this approach is limiting, for example, many untraversable terrains, such as snow, sand, or mud are not bumpy. Finally, current methods only provide a binary mask on traversable or non-traversable regions; however, reality is far more complicated. For example, some regions may be \textit{seem} traversable and even lead to a shorter path, but not be preferred due to potential lack of traction, such as a sandy patch or an icy path.

\subsection{Contributions}

In this paper, we present a new modular approach to speed-up field robot path programming that learns to drive the robot on paths of optimal traction. We term our method \textbf{WayFAST}: \textbf{Way}point \textbf{F}ree \textbf{A}utonomous \textbf{S}ystems for \textbf{T}raversability, and demonstrate that it significantly reduces field robot path programming time and effort by letting the user simply pick the target point where the robot needs to travel. Our method is completely self-supervised and heuristic free; that is, it does not need any manual labels or heuristics to be defined for learning traversable regions. Our method is modular, being able to plug into proven state estimators, such as Extended Kalman Filters or Moving Horizon Estimators \cite{thrun2002probabilistic,liu2016moving}, and model predictive controllers, such as traction adaptive Nonlinear Model Predictive Control or MPPI control \cite{kayacan2018embedded,williams2017model,williams2016aggressive,gandhi2021robust}. We show through extensive experimentation in various challenging outdoor environments in two entirely different geographies (US Midwest and Puerto Rico) that our method outperforms existing methods and leads to oscillation free autonomous navigation.

\iffalse
Our main contribution are: 1. Defining the traversability coefficient using obstacle experience and traction estimates from simple robot kinodynamic models, and using a Nonlinear Mohinv Horizon Estimator to estimate it to collect training labels in a self-supervised manner, 2. Creating a modular architecture that provides a data-efficient alternative to end-end methods \cite{kahn2021badgr,loquercio2018dronet,chiang2019learning},
3. We present a multi-modal deep convolution neural network (termed TravNET) that uses image and depth observations from off-the-shelf RGB-D sensors, and provide ways to train it.
Indeed we demonstrate that WayFAST attains a good middle ground as it uses a neural network to learn traversability representations while also leveraging a well known kinodynamic models to improve learning and navigation performance.
\fi
\section{Related Work}

\textbf{Classical navigation.} Global Navigation Satellite Systems (GNSS) based waypoints are the standard method for robot path programming, but this is cumbersome in unstructured outdoor environments. Classical approaches either do reactive obstacle avoidance through heuristics based on sensor data or simultaneously build a map of the environment and determine the robot's position in the map (SLAM) to navigate \cite{thrun2002probabilistic,siegwart2011introduction}. Both approaches only perceive the environment geometrically and assume all geometric obstacles are untraversable but ignore valuable semantic information (e.g., tall grass is geometrically untraversable but a robot can likely go through it). In addition, SLAM methods are computationally expensive, require the environments to have textural variations to reliably track features, and are sensitive to visual aliasing in loop-closure. This limits their performance in challenging unstructured outdoor environments (like forests). In addition, it is not necessary to construct a global map if a navigation system can perceive both geometry and semantics in its local environment.

\textbf{Learned navigation in indoor environments.} Learning-based approaches have been used in indoor robotics to tackle some of the above challenges but they do not generalize to outdoor environments. \cite{bowman2017probabilistic, mccormac2017semanticfusion} fused semantic information to classical sparse and dense SLAM systems but the other limitations in outdoor environments still exist. \cite{gupta2017cognitive,bansal2020combining} use privileged information during training to learn navigational affordances in a modular manner but assume access to perfect odometry. \cite{wijmans2019dd,zhu2017target} use end-to-end learning to output control commands from input images by training a reinforcement learning (RL) agent. However, RL methods are generally sample inefficient and hence these methods require simulations from photorealistic scans for training.

\textbf{Learned navigation in structured outdoor environments.}
Autonomous driving is a common example of a structured outdoor environment. Different modular approaches that use the structure of lanes to learn affordances have been proposed \cite{chang2018deepvp,chen2015deepdriving}.
In agricultural settings, \cite{sivakumar2021learned} uses crop rows as a reference to train a relative state estimation network to autonomously drive a robot in the lane between two crop rows. However, wooded areas, remote outposts, or other rural landscape does not always have reliable repeating structure.

\textbf{Supervised and self-supervised learning in unstructured outdoor environments.} Learning traversability is an emerging area of research.
\cite{valada2017adapnet} takes a supervised learning approach, where a network model is trained for semantic segmentation and shown to be effective for autonomous navigation. However, this requires manual labeling, which is tedious.
For quadrupeds, \cite{wellhausen2019should} presents a method to generate semantic segmentation and dense image predictions based on force sensors. The semantic segmentation is created with weak supervision and the authors show it is possible to use the neural network predictions to choose paths that require less force for quadruped robots locomotion. These tactile force sensors are not common for wheeled robots, add cost and complexity, and although they can be used for ground preference, they are not useful for obstacles. \cite{wellhausen2020safe} uses anomaly detection with normalizing flow to detect out of distribution situations from a navigation training dataset. This produces a binary map of potentially safe areas for navigation. However, binary estimation oversimplifies the perception, making partially traversable paths equally important to fully traversable ones. BADGR \cite{kahn2021badgr} trains an end-to-end model-based RL policy with labels automatically created from embedded sensors. Using different sensors and a set of rules to define collisions, BADGR can predict collision probability and uses a sampling based algorithm to avoid collision and bumpy terrains. BADGR's self created dataset avoids explicit human labeling, but still requires heuristics to generate collision labels. We instead leverage known kinodynamic models to create a traversability predictor that can avoid obstacles and predict paths of good traction.

\section{System Design}

WayFAST is a modular navigation system based on traversability estimation for unstructured outdoor environments. RGB and depth images from on-board camera on the robot are processed through a convolutional neural network to predict traversability. The generated traversability map along with a defined kinodynamic model is then used for model predictive control. Given a goal, the system is able to minimize a cost function that safely guides the robot to the target location. In this section, we describe the robotic platform and various modules of WayFAST in detail.

\begin{figure*}[htp]
    \centering
    \includegraphics[trim={0cm 3.5cm 0 6cm}, clip, width=0.9\linewidth]{figures/estimator_schematic.pdf}
    \caption{Our state estimation scheme, where the green box shows the Nonlinear Moving Horizon Estimator that estimates two-dimensional robot's states and unknown model parameters. The yellow box shows the Extended Kalman Filter used to augment estimates to three-dimensional and integrate the moving horizon estimations with a prediction model.}
    \label{fig:estimator}
\end{figure*}

\subsection{Robot platform description}

TerraSentia (by Earthsense Inc.) is a skid-steer robot, which is a type of robot commonly used in many applications due to its mechanical simplicity, such as agricultural fields, industrial automation, mining, and planetary exploration \cite{higuti2019under,liao2018model,huh2011development,reid2015artemis}. We used an Intel RealSense D435i camera on top and this provides color and depth images (with usable range of 5 meters, which is sufficient as the sensor is pointed towards the terrain). We used a Nvidia Jetson Xavier NX computer in the robot to run our algorithms.

Affine kinodynamic model, given by \eqref{eq:kino-model}, describes skid-steer robots, like
TerraSentia. We use this model to formulate the estimator that provides self-supervised labels for training and also in the model based controller.

\begin{equation}
    \dot{x}(t)
    =
    \begin{bmatrix}
        p_x(t) \\
        p_y(t) \\
        \theta(t)
    \end{bmatrix}
    =
    \begin{bmatrix}
        \mu \cdot cos(\theta(t)) & 0 \\
        \mu \cdot sin(\theta(t)) & 0  \\
        0 & \nu
    \end{bmatrix}
    \begin{bmatrix}
        v(t) \\
        \omega(t)
    \end{bmatrix}
    \label{eq:kino-model}
\end{equation}

$x(t)$ is the state vector composed of  $p_x(t)$, $p_y(t)$ and $\theta(t)$ representing position in x and y axis and heading angle respectively. $\mu$ and $\nu$ are unknown parameters and can be related to a skid coefficient caused by the interaction between the wheels and terrain. $v(t)$ and $\omega(t)$ are the commanded linear and angular velocities, which are the control inputs.

\subsection{Generating Traversability Labels with NMHE} \label{subsection:mhe}

We use a nonlinear moving horizon estimator (NMHE) to generate traversability labels to train our prediction network. The NMHE uses the system model shown in \eqref{eq:kino-model} and synchronously runs with GNSS on the robot. We define $\mu$ and $\nu$ shown in \ref{eq:kino-model} as the traversability coefficient. To estimate this coefficient, we use the commanded action as system input. This allows us to estimate how the robot behaves when action command is applied. Traversibility coefficients should be one when the robot perfectly moves according to the commanded action and zero when the robot is stuck at a place such as when it encounters an obstacle or untraversable terrain.

NMHE is ideal for instantaneous traversability estimation since it deals with constrained states and parameters. We assume the measurements model $h(\cdot)$ is subject to an additive measurement noise $w(t)$ such that the measurements $y(t)$ may be defined as
\begin{equation}
    y(t)=h(x(t),z(t),\Delta\theta)+w(t).
\end{equation}

We solve the following finite horizon optimization formulation to obtain the system states and unknown  parameters
\begin{align} \label{eq:mhe-optimization}
    \begin{gathered}
        \min_{x_{k:k+N}, \mu, \nu, \Delta\theta} ||x_k-\Tilde{x}_k||^2_{P_x} + ||p-\Tilde{p}||^2_{P_p} + \\
        \sum_{i=k}^{k+N} ||y_i-h(x_i,z_i,\Delta\theta)||^2_{P_w}
    \end{gathered}
\end{align}
subject to the constraints
\begin{align} \label{eq:mhe-constraints}
    \begin{gathered}
        x_{k+1} = f(x_k,u_k) \\
        \mu, \nu \in [0,1] \\
        \Delta\theta \in [-\pi,\pi)
    \end{gathered}
\end{align}

$\Tilde{x}_k$ is the initial estimated state vector, $\Delta\theta$ is the offset between true North and compass estimated North, $p=[\mu, \nu, \Delta\theta]^\top$ is the vector of parameters, $\Tilde{p}$ is the estimated vector of parameters, and $N \in \mathbb{N}$ is the length of the horizon. The measurement equation model, subject to additive noise, is defined as
    \begin{equation*}
        w_k = y_k-h(x_k,z_k,\Delta\theta) =
        \begin{bmatrix}
            p_{x_k} - z_{x_k} \\
            p_{y_k} - z_{y_k} \\
            \theta_k - (z_{\theta_k} + \Delta\theta)
        \end{bmatrix}
    \end{equation*}
where $z_k = [z_{x_k}, z_{y_k}, z_{\theta_k}]^\top$, $z_{x_k}$ and $z_{y_k}$ are the pair of measured position coordinates from GNSS, and $z_{\theta_k}$ is the measured heading angle from the embedded inertial sensor. For estimation purposes, we assume the parameters are constant in a short horizon $N$.

The estimator is followed by an Extended Kalman Filter (EKF) \cite{thrun2002probabilistic, farrell2008aided} which uses a prediction and a measurement model to estimate robot's states in a three-dimensional space. Our prediction model is synchronized with the embedded inertial sensor which fills the predictions in a higher frequency while NMHE deals with constraints. Figure \ref{fig:estimator} shows how the NMHE data is used in the EKF where NMHE outputs are used as measurements to correct the EKF predictions. The gyroscope outputs the angular velocities $\omega_x$, $\omega_y$, $\omega_z$, and the accelerometer sensor outputs the linear accelerations $a_x$, $a_y$, $a_z$,  while $\hat{u}_k$ is the composition of these six measurements. Similarly, the vector $\hat{z}_k$ is composed by the NMHE outputs $p_{x_{k+1}}$, $p_{y_{k+1}}$, $\theta_{k+1}$ and the pitch and roll angle measurements $\alpha_{k+1}$ and $\beta_{k+1}$ from the compass.

\subsection{Self-Supervised Learned Perception for Traversability

\begin{figure*}[htp]
    \centering
    \includegraphics[trim={2cm 8cm 6cm 11cm}, clip, width=0.7\linewidth]{figures/trav_net_resnet.pdf}
    \caption{Our TravNet architecture, which fuses RGB and depth information to predict traversability in the input image.}
    \label{fig:net-architecture}
\end{figure*}

We present a convolutional neural network named TravNet to estimate traversability coefficient values in the image space. Traversability coefficient represents how much control effort is needed to reach a defined location. Traversability prediction in image space provides traversability coefficient for trajectories within robot's field-of-view which is then used to plan the locally optimal path to the goal. TravNet takes in RGB and depth images of size 424×240 and outputs a single channel traversability prediction image of same size as input. TravNet uses a ResNet-18 backbone \cite{he2016deep} pretrained on ImageNet \cite{deng2009imagenet}. We truncate the ResNet-18 network before the average-pooling layer, and add a bottleneck block with two convolutional layers followed by a decoder with four blocks of convolutional layers. A second branch encodes the depth information and fuses it with the Resnet18-based RGB encoder after each convolutional block \cite{jiang2018rednet, sun2020real}. Figure \ref{fig:net-architecture} shows TravNet's architecture and how depth information is fused with RGB to predict traversability.

\begin{figure}[htp]
    \centering
    \includegraphics[trim={0cm 0cm 0 0cm}, clip, width=1.0\linewidth]{figures/projection.jpg}
    \caption{An example of labeled data created by projecting traversability estimations onto an image.}
    \label{fig:label-image}
    \vspace{-0.1in}
\end{figure}

To acquire data for training TravNet, we manually drove the robot on forest-like and semi-urban outdoor environments. We collected camera observations and state estimations using our estimator for a period of about 2 hours, which is equivalent to a dataset of 15000 images. Figure \ref{fig:dataset} shows examples of untraversable areas encountered in the dataset. The projected path shows the robot's future trajectory for that given time instant, and the color intensity shows the traversability coefficient estimation.

To train TravNet, we follow a similar approach to \cite{wellhausen2019should}, except that we use our online state estimation with NMHE + EKF to generate training labels. During data collection, the estimator is used to record the robot's position and traversability coefficients. To prepare the training and validation data, recorded image stream is downsampled to 2 fps and the traversed path is projected onto the image space using known transformation matrices to create the label image for each corresponding RGB image. An example is shown in Fig. \ref{fig:label-image}. The loss is calculated sparsely only where the robot traversed using an L1 norm.

The collected data is highly imbalanced with more examples of successful navigation of the robot (traversability coefficient close to one) compared to failures when the robot gets stuck(traversability coefficient close to zero). To address this issue, we use label distribution smoothing technique to more heavily weigh data from failures \cite{yang2021delving}.

\subsection{Traversability-based Model Predictive Controller}

To drive the robot on a safe path to reach the goal location, we formulated a nonlinear model predictive controller (NMPC) that leverages TravNet's traversability prediction. As described in section \ref{subsection:mhe}, we use the kinodynamic model in \eqref{eq:kino-model} to predict the robot's states. In this case, $\mu$ is predicted as a function of the robot's position, while the parameter $\nu$ is held constant. We predict $\mu$ using TravNet and set $\nu$ as the average value from estimations in the dataset. The TravNet output is used as lookup table, and bilinear interpolation is used to interpolate pixel values into a continuous function. We define this continuous function as $\mu(x,y)$, parameterized as a function of the system states $p_x$ and $p_y$. We use a proper transformation $T(\cdot)$ (according to the camera position relative to the center of the robot) to project the robot's position to the image space, such that $(p_{1_k}, p_{2_k}) = T(p_{x_k}, p_{y_k})$, as shown in \eqref{eq:mu-function}, where $I_T(p_{1_k},p_{2_k})$ is the interpolated pixel value from the output traversability image at pixel location $(p_{1_k},p_{2_k})$.

\begin{equation}
    \mu(x_k,y_k)
    =
    \begin{cases}
      0 & \text{if $(x_k,y_k) \not\in \mathcal{F}$} \\
      I_T(p_{1_k},p_{2_k}) & \text{otherwise}
    \end{cases}
    \label{eq:mu-function}
\end{equation}

By defining traversability to be zero when the position states $p_x$ and $p_y$ are not part of the field-of-view set $\mathcal{F}$, the model predictive control solution is constrained within the camera's field-of-view, since the kinodynamic model is uncontrollable when the traversability coefficient is zero. The resulting kinodynamic model used by the controller is shown in \eqref{eq:mpc-model}.

\begin{equation}
    \dot{x}(t)
    =
    \begin{bmatrix}
        p_x(t) \\
        p_y(t) \\
        \theta(t)
    \end{bmatrix}
    =
    \begin{bmatrix}
        \mu(p_x(t), p_y(t)) \cdot cos(\theta(t)) & 0 \\
        \mu(p_x(t), p_y(t)) \cdot sin(\theta(t)) & 0  \\
        0 & \nu
    \end{bmatrix}
    \begin{bmatrix}
        v(t) \\
        \omega(t)
    \end{bmatrix}
    \label{eq:mpc-model}
\end{equation}

To design the online reference tracking NMPC, we choose an optimization horizon $N \in \mathbb{N}$ and positive definite matrices $Q$, $R$, and $Q_N$. The following finite horizon optimization formulation is solved to obtain a sequence of control actions that minimizes the cost function
\begin{align} \label{eq:optimization}
    \begin{gathered}
        \min_{x_k, u_k} \sum_{i=k}^{k+N-1} \left\{ ||x_i-x_i^r||^2_Q + ||u_i||^2_R \right\} \\
        + ||x_{k+N}-x_{k+N}^r||^2_{Q_N} + W \cdot F_{\mu}(x_{k:k+N})
    \end{gathered}
\end{align}
The first term minimizes the error between predicted states $x_i$ and the reference state $x^r_i$. The second term minimizes the control action $u_i$ to introduce some damping effect to the control. The third term minimizes the terminal state error. And finally, the fourth term maximizes the clearance based on the traversability around each predicted state. To maximize the clearance around predicted states, we sample points in a uniform distribution around the states and calculate the average for each state. Then we minimize $1-\mu_{avg}$, where $\mu_{avg}$ is the average of traversability for these random points. This is possible because the traversability prediction is in the image space, which enables the sampling of points. $W$ is a weighing cost to fine-tune this term.

Let $(u_{i}^\ast)_{i=k}^{k+N-1}$ be the solution for the optimization described in \eqref{eq:optimization}. Then, the first control $u_{k}^\ast$ is applied to the system at time $k$ to drive the robot. Figure \ref{fig:mpc-diagram} shows how TravNet is used in the model predictive control formulation to safely drive the robot in an unstructured environment. To speed up the optimization process on a GPU, we utilize a sampling based MPC approach called MPPI as described in \cite{williams2017model,williams2017information}, where action trajectories are sampled and evaluated to find the minimum cost path within the camera field of view. The controller is parallelized on the GPU and can sample more than 4000 trajectories at a frequency of about 10Hz in real-time.

\begin{figure}[htp]
    \centering
    \includegraphics[trim={7cm 2cm 7cm 2cm},clip,width=1.0\linewidth]{figures/mpc_schematic.pdf}
    \caption{WayFAST modular architecture. Images are used to predict a local traversability map, which is used to generate a cost function for the model predictive control (MPC) block. MPC generates locally optimal goal-oriented trajectories of good traction that avoid obstacles.}
    \label{fig:mpc-diagram}
    \vspace{-0.2in}
\end{figure}


\section{Introduction}
\label{sec1}
The aim of single container packing problem is to find the densest possible packing patterns for the given items in a single container. The container can be square, circular, semi-circular, polygonal, cube-shaped or rectangular, and the items can be rectangles, circles or irregularly shaped. As an important class of optimization problems, packing problems have numerous applications in industry and academia, such as applied mathematics, material manufacturing, material cutting, logistics, wireless communication, the fashion industry, architecture layout, and the motor cycle industry. As an NP-hard problem, however, there is no exact algorithm to obtain optimality in polynomial time unless N = NP, and researchers have resorted to heuristics or approximation methods.

We consider a two-dimensional Circle Packing Problem (CPP) in which items are circles. The CPP has been well studied in a wide range of papers. Hifi and M'Hallah \cite{9} reviewed the most relevant literature on efficient models and methods for packing circular items in different types of containers. The CPP is classified into two categories based on whether the circle items are equal \cite{21,29,32} or unequal  \cite{1,2,12}. Other variants exist that consider additional constraints, such as the CPP with equilibrium constraints \cite{8,18}.

For the equal-circle packing problem, the most common approaches are based on the quasi-physical method. Lubachevsky and Graham \cite{24} evaluated each item as a rigid billiard, viewed its movement under a collision force, and proposed a billiards simulation algorithm based on the collision forces between the objects.
They also proved that their algorithm could obtain an optimal solution if \textit{n}, the number of circles, equals $3{k}({k}+1)+1$ for any positive integer \textit{k}. Huang and Ye \cite{13,14} proposed a quasi-physical global optimization method that considered each circle item an elastic object and considered two types of movement, a smooth movement driven by elastic forces and a violent movement driven by strong repulsive and attractive forces. Liu et al. \cite{19} proposed another quasi-physical algorithm incorporating a new pattern update mechanism with an improved Energy-Landscape-Paving method. Other researchers applied meta-heuristics to solve the CPP. For example, Grosso et al. \cite{4} proposed a genetic algorithm for packing equal circles in a circular container based on the Monotonic Basin-Hopping approach and a population-based variant basin-hopping strategy.

For the unequal-circle packing problem, there are two main categories: construction methods and global optimization methods. The construction methods start by constructing a pattern by placing circles one by one according to specific rules. Some researchers fix the container size and rearrange the positions of the circles through each constructive procedure, whereas others adjust the container radius and container centre through the constructive procedure. Huang et al. \cite{15} proposed two greedy algorithms, B1.0 and B1.5. B1.0 placed the circles one by one according to the maximum-hole degree of the current placement, and B1.5 improved B1.0 with a self-look-ahead search strategy. L\"{u} and Huang \cite{25} incorporated a Pruned Enriched Rosenbluth Method (PERM) using the maximum-hole degree strategy, in which the PERM strategy was to efficiently prune and enrich branches and the maximum-hole degree was defined to evaluate the benefit of a partial pattern. Hifi and M'Hallah \cite{10} proposed a three-phase algorithm: a dynamic search phase that successively packed the ordered set of circles, an adaptive phase that used intensification and diversification to find a smaller container, and a restarting phase based on the hill climbing approach. Kubach, Bortfeldt and Gehring \cite{17} formulated several greedy algorithms and parallelized these algorithms by using a master-slave approach followed by a subtree distribution model.

Global optimization methods for solving the unequal-circle packing problem concentrate on improving the pattern iteratively rather than constructing a good initial pattern. Hi et al. \cite{11} presented a Simulated Annealing (SA) approach that defined an energy function for local optimization by using certain pattern transformation methods. Stoyan and Yaskov \cite{28} utilized a combination of tree search and reduced gradient methods for local optimization and translated from one local minimum to another local minimum based on the concept of active inequalities and the Newton method. Fu et al. proposed an Iterated Tabu Search approach (ITS) \cite{3} starting from randomly generated solutions, and a perturbation operator was subsequently employed to reconstruct the incumbent solution. Zeng et al. \cite{31} presented a Tabu Search and Variable Neighbourhood Descent (TS-VND), which is an adaptation of the tabu search procedure of ITS algorithms \cite{3}. Lopez and Beasley \cite{22} viewed this problem as scaling the radii of the unequal circles so that all of them could be packed into a fixed-size container; they improved the pattern quality by using a perturbation strategy of swapping two circles. Additionally, in 2016, they used a new and merged metaheuristic for packing unequal circles in a fixed-size container \cite{23}. Specht \cite{26} proposed a novel algorithm to analyse the unoccupied areas in a packing pattern by graph theoretical methods. It used the object-jumping strategy to achieve densification. This strategy is efficient when the smallest jammer is smaller than the largest unoccupied space.

In this paper, we address an important version of the Circle Packing Problem that attempts to find a non-overlapping dense Packing pattern for \textit{n} Unequal Circle items in a two-dimensional Square Container (PUC-SC) such that the size of the container is minimized. We propose a Partitioning Narrow Action Space and Circle Items (PAS-PCI) algorithm for solving the PUC-SC. The proposed method is inspired by our previous work. In 2011 and 2012, He et al. defined the concept of an action space for the rectangular packing problem \cite{6,7}, and each maximal unoccupied rectangular space is called an action space in a packing pattern. In 2015, He et al.\cite{5} proposed an Action Space based Global Optimization (ASGO) algorithm for the problem that packs unequal circles into a square container. For some given patterns, ASGO utilized the Limited-memory Broyden-Fletcher-Goldfarb-Shanno (LBFGS) algorithm \cite{20} for continuous optimization to reach the local minimums. Then, each circular item is approximated as a square item, and an action-space-based basin-hopping strategy is adapted to find the larger unoccupied spaces as candidate places to replace some of the most overlapping items to jump from a local minimum.

Specifically, PAS-PCI uses a new basin-hopping strategy based on our observation that the small circles and the large unoccupied circle are robustly complementary to each other. We initially partition the circles into several groups according to their sizes. When reaching a packing pattern with the local minimal potential energy, we select items with the maximal deformation from each group and move them to the best-matching or randomly chosen unoccupied action spaces. For the narrow action spaces, we place two items selected from one or two adjacent groups, indicating that they are similar sizes, in the centre of the two partitioned action spaces, which we call neighbour spaces. The new basin-hopping strategy helps reduce local cycling and pushes the search to a promising area.

PAS-PCI also applies a perturbation operator to escape from the local minimum, which is obtained using LBFGS continuous optimization and the basin-hopping strategy. The perturbation operator swaps two similar-size circles or two randomly selected circles. Finally, a post-processing procedure is applied to reduce the container size further when a feasible packing pattern is reached. We perform computational experiments on two sets of benchmark instances and demonstrate the effectiveness of the proposed method by comparing it with ASGO \cite{5}, the current best algorithm published in the literature, and the best-known results downloaded from the Packomania website \cite{27}.

\section{Problem formulation and the general quasi-physical approach}
\label{sec2}
For the PUC-SC problem, we are given $n ({n} \in {N^+})$ circles $C_1, C_2,\dots , C_n$, with integer radii $r_1, r_2, r_3, \dots, r_n$, and asked to find the smallest square container of size \textit{L} such that all circle items are packed feasibly, i.e., without any overlapping between any pair-wise circles $(C_i \bigcap C_j =\phi )$ and with all circles fitting completely inside the container.

Specifically, let the centre of the square container be located at the origin of a two-dimensional Cartesian coordinate system. Denote the centre coordinate of circle $C_i (1 \leq i \leq n)$ as $(x_i, y_i)$, as shown in Fig. \ref{fig:key1}a. We define a packing pattern as $X = (x_1, y_1, \dots, x_i, y_i, \dots, x_n, y_n)$. Let $ \sqrt{(x_i-x_j )^2+(y_i-y_j )^2}$ indicate the Euclidean distance between the centres of circle $C_i$ and $C_j$ (Fig. \ref{fig:key1}b). The PUC-SC problem can be formulated as follows.

        min  \textit{L}\\
s.t.    (1)  $ max(|x_i |,|y_i | )\leq(L/2-r_i),    1 \leq i \leq n.$

\indent~(2)  $ \sqrt{((x_i-x_j )^2+( y_i-y_j)^2 )}  \geq (r_i+r_j),     1 \leq i < j \leq n.$

Here, (1) imposes the condition that any circle should not be extended outside the container, and (2) imposes no overlap between any pair-wise circles.

 \begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.4]{1.jpg}
  \caption {Denotations for the PUC-SC problem.}
 \label{fig:key1}
 \end{figure}

The quality of a feasible solution is measured by the size of the square container \textit{L}. We start from the current known best container size $L_{best-current-result}$ published by ASGO, and in the case when a feasible solution is found, we will try to reduce the container size and seek a better solution.

For a fixed container size \textit{L}, we adopt the quasi-physical approach \cite{30}, considering all \textit{n} circles smooth elastic solids and the square container \textit{L} a hollow rigid solid. Initially, the circles are randomly placed; then, they will move according to the forces generated by the deformation. For a pattern (\textit{X}, \textit{L}), the overlapping between any pair-wise solids will cause elastic deformation and generate potential energy. The overlapping depth between circle $C_i$ and the vertical border is as follows:
  \begin{equation}
  \label{eq1}
  D_{iv}=max(r_i+|x_i |- (L/2),0 ).
  \end{equation}
However, the overlapping depth between circle $C_i$ and the horizontal border is as follows:
  \begin{equation}
  \label{eq2}
  D_{ih}=max(r_i+|y_i |-(L/2),0 ).
  \end{equation}
The embedding depth of two circles $C_i$ and $C_j$ is as follows:
   \begin{equation}
   \label{eq3}
   D_{ij}= max ((r_i  + r_j)- \sqrt{(x_i-x_j )^2+(y_i-y_j )^2},0 )
   \end{equation}
Then, we compute the total elastic potential energy for pattern (\textit{X}, \textit{L}) as the penalty function \cite{5}:
   \begin{equation}
   \label{eq4}
   U_e (X) = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(D_{ij}^2)+\sum_{i=1}^{n}(D_{iv}^2 + D_{ih}^2).
   \end{equation}

$U_e$(\textit{X}) measures the extent of overlap and is clearly nonnegative. If $U_e$(\textit{X}) = 0, then we reach a feasible solution. If $U_e({X}) > 0$, then overlap exists.

When the circles movement reaches a local minimum of the penalty function, the circles can no longer move even when some overlap exists. We define the pain degree \cite{5}for a circle \textit{i} in Eq. \ref{eq5}, where $D_{iv}$ and $D_{ih}$ indicate the overlapping depth to the container borders vertically and horizontally, and $D_{ij}$ indicates the overlapping depth to circle item \textit{j}.
   \begin{equation}
   \label{eq5}
P_i  =(D_{iv}^2+D_{ih}^2+\sum_{j=1 j\neq i}^{n}D{ij}^2)/r_i^2
   \end{equation}

We then pick a circle $C_i$ with the largest pain degree, i.e., the most squeezed circle, and move it to an unoccupied place. This approach is the basin-hopping strategy that drives the search to a promising area. Then, the physical movement can continue; we run the above process iteratively until we find a feasible solution or the iterative process reaches a predefined limit.

\section{PAS-PCI approach}
\label{sec3}
The Limited-memory BFGS (LBFGS) is in the family of the Quasi-Newton method and is usually used to solve large nonlinear optimization problems. For a fixed container size $L_0$, initialized by the current best record for each instance, we randomly place the circle items inside the container to generate multiple patterns. For each pattern, we apply the LBFGS algorithm for continuous optimization until a local minimum is reached. For example, Fig. \ref{fig:key2}a shows a random pattern, and Fig. \ref{fig:key2}b shows the new pattern in the local minimum after applying LBFGS, in which overlaps remain. We then use a basin-hopping strategy based on the Partitioned Action Space and Partitioned Circle to jump out of the stuck pattern.

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{2.jpg}
\caption {Fig. 2. Applying LBFGS to a pattern.}
\label{fig:key2}
\end{figure}
\subsection{Basin-hopping strategy}
\label{sec3:1}
Researchers have proposed many basin-hopping methods to help the stagnated pattern escape from the local optimum by learning the advantages from the search history. An intuitive strategy is to transfer the most squeezed circle to a random place inside the container; however, this method is not effective when the search is located in a large space. Another popular strategy is to swap two circles by various rules, such as swapping pair-wise circles of similar sizes. Although the second strategy is not efficacious for packing equal circles, it is very useful for packing unequal circles. In this paper, we propose a new basin-hopping strategy by partitioning the narrow action spaces and partitioning circle items according to their sizes.

\begin{definition}[Partitioned Circle Items, PCI]
\label{def1}
For a pattern (\textit{X}, \textit{L}) with \textit{n} circle items, we partition the items into four sets, $S_1$ to $S_4$, based on their radii. Without loss of generality and assuming the circles are numbered from 1 to \textit{n} from small to large, we then obtain [1, int (\textit{n}/4)], [int (\textit{n}/4) +1, int (\textit{n}/2)], [int (\textit{n}/2) +1, int (3\textit{n})/4], and [int (3\textit{n}/4) +1, \textit{n}].
\end{definition}

Fig. \ref{fig:key3} shows an example for \textit{n} = 12. $S_1$ contains the smallest items, and $S_4$ contains the largest.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.45]{3.jpg}
\caption {An example of the partitioned sets for \textit{n} = 12. }
\label{fig:key3}
\end{figure}

The locations of large circles in the container are fixed to some extent, whereas the small circles are relatively flexible. Therefore, we give circles in $S_1$ and $S_2$ more priority to move to the Best Matching Spaces (BMS) or other suitable unoccupied spaces and drive the search to a promising area.

\begin{definition}[Best Matching Space, BMS]
\label{def2}
The best matching action space of an item is an action space in which the length of the short side is closest to the diameter of the circle.
\end{definition}

For a stuck pattern (\textit{X}, \textit{L}), we must discover and measure the unoccupied spaces to move a squeezed circle to the right place, but it is difficult to perform accurate calculations because the unoccupied spaces are irregularly shaped. Some researchers pseudo-place a number of additional check disks randomly in the container \cite{16} and calculate the elastic energy of the check disks to evaluate the size of the unoccupied spaces, which is effective for packing equal circles. However, this strategy might not find all of the useful occupied space due to the random placement of the check disks, and some check disks may be placed inside some circle items.

The key issue for the basin-hopping strategy is how to find all of the large unoccupied spaces effectively. We borrow the action space concept from the rectangular packing problem to find the unoccupied spaces. For the rectangular packing problem, an action space is an unoccupied rectangular space into which a dummy rectangle could be feasibly placed, and each edge of the dummy rectangle touches at least one item or the container \cite{6,7}. By approximating the circles to square items, He et al. proposed a novel approach to find all unoccupied spaces as action spaces \cite{5}. The action spaces could approximately measure the sizes of the corresponding unoccupied spaces, and the action spaces could be calculated quickly. We adopt the action space method to find unoccupied spaces, and we consider additional characteristics of the action spaces to fully utilize the unoccupied spaces.

\begin{definition}[Square container $O_0$ and square item $O_i$]
\label{def3}
The square container $O_0$ is only the container for the circle-packing problem. We then approximate each circular item $C_i (i \in [1, n])$ as a square item $O_i$ by setting its width as $(1+(1/\sqrt{2})) r_i$, as shown in Fig. \ref{fig:key4}.
\end{definition}

For a stuck pattern, we approximate each circular item as a square item and adapt the idea of the action space to find all large unoccupied spaces. In the beginning, there is only one action space, the container $O_0$. After placing all of the square items into the action spaces, the action space list is updated. If a square item coincides completely with an action space, then no more action space can be created. If a square item intersects and coincides with an action space in three dimensions, then one new action space is created. If the item coincides with an action space in two dimensions, then two new action spaces are created.

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.45]{4.jpg}
\caption {Approximate each circular item as a square item.}
\label{fig:key4}
\end{figure}

For an action space \textit{i}, denote its width and height as $w_i$ and $h_i$, and denote the coordinates of its left-bottom vertex and right-top vertex as $(x_{i1}, y_{i1})$ and $(x_{i2}, y_{i2})$, respectively. We measure the size of an action space in two ways, the length of the short side and the perimeter, and sort all action spaces in non-ascending order based on the two metrics to create two lists. Let $l_1$ and $l_2$ are two lists, and each list contains the top 10 action spaces, respectively.
 (i) Lexicographic order (list $l_1$): $\min(h_i, w_i) \geq \min(h_j, w_j)$ for \textit{i} in front of \textit{j}.
 (ii) Traditional order (list $l_2$): $h_i + w_i \geq h_j + w_j$ for \textit{i} in front of \textit{j}.

There are more narrow action spaces in list $l_2$, and the narrow action spaces are sorted towards the front compared with their positions in list $l_1$. Thus, we can find more suitable action spaces for moving squeezed circles, particularly for small circles. Fig. \ref{fig:key5}a shows the action spaces in list $l_1$, and Fig. \ref{fig:key5}b shows the action spaces in list $l_2$.

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{5.jpg}
\caption { List of action spaces obtained by two methods.}
\label{fig:key5}
\end{figure}

\begin{definition}[Narrow Action Space, NAAS]
\label{def4}
An action space \textit{i} is called narrow if the long side is at least double the short side, i.e., either $h_i \leq 0.5 w_i$, or $w_i \leq 0.5 h_i$.
\end{definition}

\begin{definition}[Neighbour Action Spaces, NEAS]
\label{def5}
We partition all narrow action spaces in lists $l_1$ and $l_2$ by dividing each Narrow Action Space at the centre of the long side to obtain two equal-size action spaces, which we call Neighbour Action Spaces, as shown in Fig. \ref{fig:key6}.\\
\end{definition}

\begin{definition}[Neighbour Space Occupying, NSO]
\label{def6}
Neighbour Space Occupying (NSO) is the placement of two items in the centres of the Neighbour Action Spaces.
\end{definition}

For a narrow action space, we select two items with the greatest pain degree from $S_1$, or one from $S_1$ and the other from $S_2$, and perform NSO. Fig. \ref{fig:key7} shows an example.

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.45]{6.jpg}
\caption {Partition the narrow action spaces. }
\label{fig:key6}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{7.jpg}
\caption { Move two small items to the centres of the Neighbour Action Space.}
\label{fig:key7}
\end{figure}

\subsection{Algorithm description}
\label{sec3:2}
The PAS-PCI algorithm includes three phases: the initial continuous optimization phase, iterative processing phase and post-processing phase. In the initial continuous optimization phase, we randomly generate a number of packing patterns and use LBFGS for continuous optimization to reach patterns with the local minimum potential energy. Then, in the iterative processing phase, we use basin hopping and perturbation operators together with LBFGS to find a feasible pattern. We initially run the basin hopping and LBFGS iteratively for at most 20 iterations. The basin-hopping algorithm uses intelligent strategies to jump out of the local minimum trap, whereas LBFGS is applied to reach new local minimum patterns. Then, the perturbation operator strategy is used to perturb the patterns to some extent before we run 20 iterations of the basin hopping plus LBFGS once again. The outer iterations for perturbation will run for 5 loops. The entire iterative processing phase will stop once a feasible pattern is found. Finally, we use the post-processing algorithm to reduce further the container size for a feasible pattern. For the parameters, we refer to the ASGO algorithm and make some tiny changes. Fig. \ref{fig:key8} illustrates the framework of the PAS-PCI algorithm.

In the following subsections, we will initially discuss the entire framework and then the details for the basin hopping and post-processing strategies.

\subsubsection{PAS-PCI framework}
\label{sec3:2:1}

The first phase, the initial continuous optimization phase, corresponds to the first level in Fig. \ref{fig:key8}. Its objective is to generate patterns with local minimum potentials and to select good patterns for the iterative processing phase. Parameter \textit{L} represents the container size and is initialized by the current best record $L_{best-current-result}$ published by ASGO. We randomly generate \textit{G} patterns (\textit{G} = 32) to increase the diversification; then, we use LBFGS on each of the patterns for continuous optimization to reach their local minima. We will switch to the post-processing phase if a feasible solution is found.

The iterative processing phase corresponds to the second level in Fig. \ref{fig:key8}. The main strategy is to call the basin-hopping algorithm to jump out of the local minimum trap. We select \textit{m} patterns (\textit{m} = 3) with the lowest total elastic potential energy from the set of patterns ${G_i | 1 \leq i \leq 32}$ and apply the basin-hopping algorithm to the selected patterns to obtain a total of 39\textit{m} =117 new patterns to increase the diversification. And we apply $k_p$ successive iterations ($k_p$ = 20) of basin hopping. At each iteration, we run the basin-hopping algorithm to generate new patterns that inherit some good properties of the old patterns. We then apply LBFGS to reach their local minima. We will check the feasibility at the end of each iteration and switch to the post-processing phase if there exists a feasible pattern. If we execute the basin-hopping algorithm for $k_p = 20$ times and cannot obtain a feasible solution, we then believe that the current patterns cannot be improved using the basin-hopping strategy alone. For the above parameters, we still refer to the ASGO algorithm and make some tiny changes. We therefore modify the perturbation operator proposed by Fu et al. \cite{3}to perturb each of the \textit{m} = 3 selected patterns to jump out of the local minimum trap. The details are shown in the following:
\begin{enumerate}
\item[$Step 1$:]{ Compute the pain degree $P_i$ for each circle $C_i (1 \leq i \leq n)$.}
\item[$Step 2$:]{ Remove all circles in sets $S_1$ and $S_2$ that contain smaller circles.}
\item[$Step 3$:]{ Sort all circles in $S_3$ and $S_4$ by their pain degrees in non-ascending order to obtain a list {B}.}
\item[$Step 4$:]{ Swap pair-wise circles of B[\textit{i}] and B[\textit{i}+1], where $i = 1, 3, 5, 7, \dots$}
\item[$Step 5$:]{ For all circles in $S_1$ and $S_2$, start from the most painful circle in the old pattern and place each circle in the best-matched action space.}
\item[$Step 6$:]{ Apply the LBFGS algorithm for continuous optimization.}
 \end{enumerate}

The perturbation operator strategy will guide the patterns to some promising areas by constructing an updated pattern instead of destroying the pattern. Then, we run the 20 iterations of basin hopping plus continuous optimization again. The outer iteration with the perturbation will run for at most $k_b = 5$ times. If we still cannot find a feasible solution in $k_b$ attempts, we consider that the initial patterns make it difficult to reach a feasible solution and restart the whole process.

The post-processing phase, or the final phase, corresponds to the third level in Fig. \ref{fig:key8}. If we obtain a feasible solution from the above two phases, we then use the post-processing strategy to further reduce the container size while maintaining the feasibility to improve the solution. The details are shown in Algorithm \ref{alg1}.

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.5]{8.jpg}
\caption { The framework of PAC-PNC.}
\label{fig:key8}
\end{figure}
 \begin{algorithm}[htbp]
 \SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
 \Input{Container size, item sizes $r_1, \dots, r_n$, number of patterns \textit{G}, selection number \textit{m};}
 \Output{Feasible pattern ($X, L$) or unfeasible pattern Null}
 \BlankLine
 \Repeat{reach the limitation of time}{
 \emph {Randomly generate \textit{G} patterns and store in array A}\;
 \For{ each pattern A[\textit{i}]}
 {
      \If{ $U_e$(A[\textit{i}]) $ < 10^{-20}$}{
         (A[\textit{i}],\textit{L})$\gets$post-processing algorithm (A[\textit{i}],\textit{L})\;
         return (A[\textit{i}],\textit{L})\;}
 }

 \em{ $k_b\gets0$}\;
 \Repeat {$k_b > 5 $}{
    \For{$k_p=1$ \KwTo $20$}{
       \emph { Select \textit{m} patterns with the lowest $U_e$, for each selected pattern, generate 39 new patterns using the basin-hopping algorithm} \;
        \For{each of the new 39*{\textit{m}} patterns}{
              \emph{$(X',L)\gets$ LBFGS$(X,L)$} \;
              \If{ $U_e(X')  < 10^{-20}$}{
               $(X',L)\gets $ post-processing algorithm $(X',L)$\;
              return $(X',L)$\;
               }
         }
     }
      \emph{Select \textit{m} patterns with the lowest $U_e$, do perturbation operator, $k_b\gets k_{b+1}$}\;
 }}
  return Null
  \label{alg1}
 \caption{PAS-PCI algorithm.}
 \end{algorithm}
\subsubsection{Basin-hopping algorithm}
\label{sec3:2:2}
The basin-hopping strategy attempts to relocate some circular items in the unoccupied spaces to generate new and better patterns. Based on the partitioned action space and partitioned circle items, we adopt several strategies to jump out of the local minimum trap for the stuck pattern. Our idea is based on the robust complementary relationship between the small circles and the large unoccupied spaces.

Our main basin-hopping strategy consists of the Neighbour Action Space and the Partitioned Circle Items (PCI). In particular, we select \textit{m} patterns (\textit{m} = 3) with the lowest $U_e$ to generate diverse patterns and partition the \textit{n} circles into four sets $(S_1, S_2, S_3, S_4)$ according to their radii. For each set, we choose a circle item with the highest pain degree $P_i$ and place that item in the largest action space, a matching action space, or a random action space from the two action space lists $(l_1, l_2)$ such that its centre coincides with the centre of the action space. For a narrow action space, we partition the long side to obtain two equally sized action spaces and select two items with the highest pain degree from $S_1$ or one from $S_1$ and the other from $S_2$. We then perform Neighbour Space Occupying in the largest narrow action space, a matching narrow action space or a random narrow action space. This strategy develops a pattern to patterns of a wide extent while simultaneously maintaining the merits of previous patterns. It also helps prevent local cycling because we choose the most painful circles from each group instead of the most painful circles overall, thus increasing the diversity. We also tabu the jammer of each group for one step to prevent further cycling.

Furthermore, to enhance the diversification, we combine several other basin-hopping strategies to generate new patterns, such as randomly swapping pair-wise similar circle items in each set of $(S_1, S_2, S_3, S_4)$. By "similar", we mean that when circles of each set $(S_1, S_2, S_3, S_4)$ are stored according to their radii, two adjacent circles are of similar radii. All of these strategies drive the search process to explore new areas in the solution space. The details of the basin-hopping algorithm are shown in Algorithm \ref{alg2}.
\begin{algorithm}[htbp]
 \SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
 \Input{\textit{m} selected pattern;}
 \Output{For each of the \textit{m} patterns, a list of new patterns is generated as follows:}
 \BlankLine
 {Generate 24 new patterns by choosing one not tabued circle item from each set $(S_1, S_2, S_3, S_4)$ with the highest pain degree and remove it from the square container. For each of the four selected items,
\begin{enumerate}
\item[(1)]{ Place it into the largest action space in list $l_1$, and obtain four new patterns. }
\item[(2)]{Place it into the largest action space in list $l_2$, and obtain four new patterns.}
\item[(3)]{ Place it into the best matching action space in list $l_1$ or $l_2$, and obtain eight new patterns.}
\item[(4)]{ Place it into a randomly selected action space in list $l_1$ or $l_2$, and obtain eight new patterns.}
\end{enumerate}}
{ Generate three new patterns by choosing two not tabued circle items from set $S_1$ with the highest pain degree, and then
\begin{enumerate}
\item[(1)]{ Perform Neighbour Space Occupying (NSO) on the largest Narrow Action Space (NAAS) to obtain a new pattern.}
\item[(2)]{ Select the best matching NAAS for the most painful circle item in $S_1$ and perform NSO to obtain a new pattern.}
\item[(3)]{ Perform NSO on a random NAAS to obtain a new pattern.}
 \end{enumerate} }
{ Generate three new patterns by choosing two not tabued circle items with the greatest pain degree, one from $S_1$ and another from $S_2$, and then
\begin{enumerate}
\item[(1)]{ Perform NSO on the largest NAAS to obtain a new pattern.}
\item[(2)]{ Choose the best matching NAAS for the selected item from $S_1$ and perform NSO.}
\item[(3)]{ Choose the best matching NAAS for the selected item from $S_2$ and perform NSO.}
\end{enumerate}     }
{ Generate five new patterns as follows:
\begin{enumerate}
\item[(1)]{ Randomly swap pair-wise similar circles of $S_1$ with $S_2$.}
\item[(2)]{ Randomly swap pair-wise similar circles of $S_2$ with $S_3$.}
\item[(3)]{ Randomly swap pair-wise similar circles of $S_3$ with $S_4$.}
\item[(4)]{ Randomly swap pair-wise similar circles of $S_1$ with $S_3$.}
\item[(5)]{ Randomly swap pair-wise similar circles of $S_2$ with $S_4$.}
\item[]{For random swap of ${C_i, C_i+1}$ of a set and ${C_j, C_{j+1}}$ of another set, we mean swap $C_i$ and $C_j$ and swap $C_{i+1}$ and $C_{j+1}$.}
\end{enumerate}}
For each set of $(S_1, S_2, S_3, S_4)$, select a circle item $C_i$ with the greatest pain degree $P_i$ and swap $C_i$ with $C_{i+1}$. Thus, obtain four new patterns.
\BlankLine
For each set of $(S_1, S_2, S_3, S_4)$, randomly swap two circle items. Thus, obtain four new patterns.
\caption{Basin-hopping algorithm.}
\label{alg2}
\end{algorithm}
\subsubsection{Post-processing algorithm}
\label{sec3:2:3}
Finally, the PAS-PCI algorithm calls for post-processing of a feasible pattern to find a better feasible solution with a smaller container size. The post-processing algorithm repeatedly shrinks the container size by a constant factor of $\propto = 0.999$ until a feasible pattern can no longer be obtained. Then, a dichotomy method is applied to find the best feasible solution. Algorithm \ref{alg3} shows the details of the post-processing algorithm.

\begin{algorithm}[htbp]
    \SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
   \Input{A feasible solution ($X, L$), shrinking factor $\propto$;}
   \Output{A feasible solution, in which $L' \leq L$;}
\Repeat{$ U_e(X') > 10^{-20}$}{
	 $ L = \propto L$\;
	 $ X'\gets$ LBFGS ($X,L$)\;
}
    $L_{upper}\gets L/\propto,$ $L_{lower}\gets L$ \;
\Repeat{$L_{upper}- L_{lower} <〖10^ {-7}$}{
        $ L'\gets(L_upper + L_lower)/2$\;
	    $ X'\gets$ LBFGS $(X,L')$\;
        \eIf{$U_e(X') < 10^{-20}$}{
     	     $ L_{upper}\gets L'$\;
     	}{
             $ L_{ower}\gets L'$\;}
}
   \caption{Post-processing algorithm.}
   \label{alg3}
\end{algorithm}

\section{Computational results }
\label{sec4}
To assess the efficiency of the proposed approach, we implemented PAS-PCI in the Visual C++ programming language. We ran PAS-PCI on a personal computer with 3.0 GHz and 4.0 GB memory.

We tested PAS-PCI on two groups of benchmark instances: $r_i=i$ and $r_i=
\sqrt{i}$ ($r_i$ is the radius of circle i, $1 \leq i \leq n$). The instances for $r_i=i$ are large-variation instances, and the second group $r_i=\sqrt{i}$)  contains small-variation instances. On the Packomania website, the range of \textit{n} is from 1 to 72. We executed each instance 10 times to reduce the effects of randomness and find the best results compared with the ASGO algorithm. For each instance, the search process will terminate if PAS-PCI yields a feasible solution no worse than the current best results or if it reaches the time limit. We compared PAS-PCI with both our previous Action Space based Global Optimization (ASGO) algorithm \cite{5} and the best results downloaded from the Packomania website, which were obtained by different authors \cite{27}. The new records obtained in these experiments are published on www.packomania.com by Eckard Specht \cite{27}. He also has further optimized our originally obtained results using some exchange heuristics and relocations \cite{26}. In general, PAS-PCI generates more-satisfying solutions.

\subsection{Parameter setup}
\label{sec4:1}
All of the parameters used in the PAS-PCI algorithm are shown in Table \ref{tab:1}, selected based on a small number of trials or referred to parameters of the previous algorithm ASGO. In Table \ref{tab:2}, we give two examples to show the impact of parameter \textit{m}, the number of selected patterns with the lowest elastic potential energy for basin hopping. Here we only show the evaluations on sampled instances of \textit{n} = 27, and \textit{n} = 64 for the $r = i$ benchmark set. We run PAS-PCI on each instance for 5 times (\textit{m} = 1, 2, 3, 4, 5) and record the results. For each selected value of \textit{m}, we show the number of hit times for 5 trials, and the average running times for successful trails. We also list the best, worst and average solutions. We could see that \textit{m} = 3 yield the best performance. For other key parameters, we also fix other parameters and do small number of trials to select the appropriate value.
Table \ref{tab:1} provides a brief summary of the parameters used in the algorithm. In the basin hopping process, the circles are sorted based on their sizes, and they are evenly partitioned into four groups $S_1$ to $S_4$ based on their radii. $S_1$ and $S_2$ contain smaller circles and they have higher priority for the movement, and we tabu the jammer of each group for one step to prevent the cycling. The container size \textit{L} is initialized by the current best record $L_{best-current-result}$, and the quality of a feasible solution is measured by the final \textit{L} for each instance. $l_1$ and $l_2$ are two lists, each list contains the top 10 action spaces depending on the evaluation metric.
Fig. \ref{fig:key9} illustrates the comparison of the parameters for PAS-PCI and ASGO \cite{5} in the framework. In previous work, He et al. \cite{5} generated 16 initial patterns and choose 2 patterns at the end of each LBFGS iteration. To increase the diversity, we double the initial number of random patterns to \textit{G} = 32, and select \textit{m} = 3 patterns with the lowest elastic potential energy at the end of each LBFGS iteration. Then in the following basin hopping process, we will reach a total of 39\textit{m} = 117 new patterns. For every $k_p$ = 20 iterations of basin hopping, He et al. \cite{5} use a perturbation operator to perturb the patterns to some extent, and their outer iterations for a perturbation run for $k_b$ = 10 loops. In the following experiments that $n\in[14,72]$, as we generate considerably more new patterns in the inner iteration, we set $k_b$ = 5 to save the total running time. Finally we use the same time limit of 48 hours to compare with ASGO \cite{5}.

\begin{table}[htbp]
\caption{Parameter regulation.}
\label{tab:1}
\centering
\begin{tabular}{l l l}
\hline
Parameter  &	Description	& Value\\ [0.5ex]
\hline
\textit{n}  &	Number of circle items  &	14-72\\
$C_i$       &	The $i^th$ circle item	\\
\textit{L}	& Size of the square container & Initialized by the current-best-result\\
\textit{X}	& Coordinates for all centres of the circles & $(x_1, y_1, \dots, x_n, y_n)$\\
$S_1$   & Set of circles            &	Circles index in $[1, int (n/4)])] $ \\
$S_2$       & Set of circles &	Circles index in [int (\textit{n}/4) +1, int (\textit{n}/2)]\\
$S_3$ &	Set of circles & Circles index in [int (\textit{n}/2)+1, int(3\textit{n})/4]\\
$S_4$ & Set of circles & Circles index in [int (3\textit{n}/4) +1, \textit{n}]\\
\textit{N}	 & Tabu tenure & 	1 \\
$l_1, l_2$ &	Lists of largest action spaces &	$|l_1 |=|l_2 |=10$ \\
\textit{G} &	Number of random patterns &	32\\
\textit{m} &	Number of initial patterns for basin hopping &	3 \\
$k_p$ &	Number of successive iteration &	20 \\
$k_b$ &	Perturbations &	5 \\
B[\textit{i}] &	The circle in the $i^th$ position of list B	\\
\textit{T} &	Allowed running time &	48 h \\
\hline
\end{tabular}
\end{table}

\begin{table}[htbp]
\caption{Evaluations on parameter m for PAS-PCI (sampled on n = 27, 64 and m = 1, 2, 3, 4, 5).}
\label{tab:2}
\centering
\begin{tabular}{c }
\textit{n}=27
\end{tabular}
\begin{tabular}{l c c c c c }
\hline\noalign{\smallskip}
\textit{n} & Hits &	Average running & Best solution & Worst solution &	Average solution \\
& & time \\
\noalign{\smallskip}\hline\noalign{\smallskip}
1 &	2/5	& 16,751 &	159.39844572 &	159.40009811 &	159.399271915 \\
2 &	3/5 & 13,634 &	159.25909220 &	159.39642779 &	159.316007847 \\
3 &	5/5	& 3,215	 &  159.10320551 &	159.26084334 &	159.206795856 \\
4 &	5/5	& 6,908	 &  159.18019927 &	159.30947629 &	159.246277900 \\
5 &	5/5	& 8,216	 &  159.16913324 &	159.27609935 &	159.238197052 \\
\noalign{\smallskip}\hline
\end{tabular}
\begin{tabular}{c }
\textit{n}=64
\end{tabular}
\begin{tabular}{l c c c c c }
\hline\noalign{\smallskip}
\textit{n} & Hits &	Average running & Best solution & Worst solution &	Average solution \\
& & time \\
\noalign{\smallskip}\hline\noalign{\smallskip}
1 &	1/5 & 90,454 &	568.46130293 &  568.46130293 &	568.46130293 \\
2 &	2/5 & 76,479 &	568.40597817 &	568.45627099 &	568.43112458 \\
3 &	3/5 & 61,537 &	568.37716941 &	568.41008273 &	568.38910549 \\
4 &	3/5 & 69,862 &	568.37716941 &	568.43158391 &	568.40303589 \\
5 &	3/5 & 73,058 &	568.38011068 &	568.42011171 &	568.39874129 \\
\noalign{\smallskip}\hline
\end{tabular}
\end{table}

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.5]{9.jpg}
\caption { The parameter setup in the flow of PAS-PCI and ASGO. }
\label{fig:key9}
\end{figure}

\subsection{Comparison on $r_i=i$}
\label{sec4:2}
We compared our results on the benchmark instances of $r_i=i$ with two works: ASGO \cite{5} and the results on the Packomania website \cite{27}. The number of circle items per instance that ASGO executed ranges from 15 to 45, in addition to instances 50, 55 and 60. We compared all 34 benchmark instances that ASGO executed with the proposed PAS-PCI algorithm. PAS-PCI returned feasible patterns with smaller container sizes in 33 instances and matched one other instance; PAS-PCI also ran faster in most instances.

We then compared the record results for \textit{i} = 14 to 72 on the Packomania website obtained by several researchers. PAS-PCI returned smaller container sizes in 50 instances and matched the other 9 instances. Note that we updated 19 records for the set of $r_i=i$ (47-48, 51-54, 57, 61-72) that had been kept unchanged since May 21, 2013.
\subsection{Comparison on $r_i=\sqrt{i}$}
 \label{sec4:3}
We also compared our results to the instances for $r_i=\sqrt{i}$. For ASGO, the range of ASGO instances started from 15 to 45, in addition to the instances 50, 55 and 60. We compared all of the 34 benchmark instances that ASGO executed with the proposed PAS-PCI algorithm. PAS-PCI returned feasible patterns with smaller container sizes in 31 instances and matched the other three; PAS-PCI also ran faster in most instances. Comparison of 35 instances (from 14 to 45, in addition to instances 50, 55 and 60 for larger instances) from the Packomania website with the PAS-PCI results shows that PAS-PCI returned feasible patterns with smaller container sizes in 32 instances and matches for the other 3 instances.

Tables \ref{tab:3} and \ref{tab:4} show the computational results for PAS-PCI, ASGO and the Packomania website for $r_i=i$ and $r_i=\sqrt{i}$, respectively. The first column includes the lists of the number of circles, the second column includes the lists of the best-known results obtained by the ASGO algorithm, and the third column includes the lists of the record results we downloaded from the Packomania website. Column 4 includes the best solutions of PAS-PCI, columns 5-8 show the best running time and average running time for ASGO and PAS-PCI, and columns 9 and 10 include the number of hit times for 10 tests on ASGO and PAS-PCI, respectively. With the new results of the instances, several of the new forms can be seen in Fig. \ref{fig:key10} and \ref{fig:key11}.

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.32]{10.png}
\caption { Packing layouts for $r_i=i$ }
\label{fig:key10}
\end{figure}

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.31]{11.png}
\caption { Some better packing layouts for $r_i=\sqrt{i} $ }
\label{fig:key11}
\end{figure}
\begin{table}[htbp]
\caption{Computational results for PAS-PCI, ASGO and the Packomania website when $r_i=i.$}
\label{tab:3}
\centering
\begin{tabular}{l l l l l l l l c c}
\hline\noalign{\smallskip}
 &	Best-known  & Best-known  & Best-solution  & Best-time & Best-time & Average time & Average time & Hits  &	Hits \\
 \textit{n}       & ASGO        & Packomania  & PAS-PCI        & ASGO (s)      & PAS-PCI(s) & ASGO (s) &  PAS-PCI (s) & ASGO  & PAS-PCI \\
\noalign{\smallskip}\hline\noalign{\smallskip}
14 & -----------  & 61.84992131  & 61.84992131  & -----   & 39      & -----   &	73      & ----- & 10/10\\
15 & 68.52756391  & 68.52756391  & 68.52756391  & 101     & 29      & 106     &	86      & 10/10 & 10/10 \\
16 & 75.04786163  & 75.00934256  & 75.00934256  & 37	  & 35      & 582     & 275     & 10/10 & 10/10 \\
17 & 81.50268767  & 81.50268767  & 81.50229942  & 111     &	49      & 956     & 543     & 10/10 & 10/10 \\
18 & 88.70023386  & 88.40408812  & 88.40408757  & 290     &	93      & 1,844   & 712     & 10/10 & 10/10 \\
19 & 95.78524607  & 95.96921334  & 95.77583449  & 36	  & 121     & 3,133   & 1,563   & 10/10 & 10/10 \\
20 & 104.92138708 & 103.11765325 & 103.11765325 & 3       & 105     & 96	  & 248     & 10/10 & 10/10 \\
21 & 110.56074443 &	110.56029719 & 110.56029719 & 1,039	  & 194     & 3,885   & 2,477   & 10/10 & 10/10 \\
22 & 118.61665487 &	118.65797248 & 118.60607058 & 491     & 261     & 2,707   & 1,591   & 10/10 & 10/10 \\
23 & 126.34478973 &	126.49109690 & 126.19548212 & 73      & 47      & 1,793   & 2,963   & 10/10 & 10/10 \\
24 & 134.37268240 &	134.36183861 & 134.28692283 & 610     & 129     & 5,531   & 2,148   & 10/10 & 10/10 \\
25 & 142.62630934 &	142.67641929 & 142.53983356 & 372     & 186     & 2,874   & 907     & 10/10 & 10/10 \\
26 & 151.15018638 &	151.05511016 & 150.99258664 & 759     & 274     & 2,546   & 1,862   & 10/10 & 10/10 \\
27 & 159.40352999 &	159.43924161 & 159.10320551 & 1,800	  & 465	    & 14,979  & 3,314   & 10/10 & 10/10 \\
28 & 168.35062099 &	168.38155796 & 168.09364893 & 599	  & 301	    & 3,627	  & 2,394	& 10/10 & 10/10 \\
29 & 177.09268466 &	177.15283242 & 176.99373443 & 3,358	  & 826	    & 9,883	  & 5,468	& 10/10 & 10/10 \\
30 & 186.12550501 &	186.10273226 & 185.97476319 & 457	  & 719	    & 20,236  & 10,531  & 10/10 & 10/10 \\
31 & 195.30022174 &	195.36206001 & 195.21263867 & 1,272	  & 1,028   & 9,335	  & 7,818	& 10/10 & 10/10 \\
32 & 204.45658766 &	204.53949877 & 204.16829349 & 3,337	  & 485	    & 21,536  & 8,604	& 10/10 & 10/10 \\
33 & 214.22777540 &	214.38380598 & 214.19767547 & 581	  & 1,553   & 7,960	  & 11,317  & 10/10 & 10/10 \\
34 & 224.10619117 &	223.84825302 & 223.77519778 & 429	  & 291	    & 2,696	  & 1,928	& 10/10 & 10/10 \\
35 & 233.51807964 &	233.37623193 & 233.10099573 & 2,737	  & 946     & 13,183  & 10,396  & 10/10 & 10/10 \\
36 & 242.99143037 &	242.96247182 & 242.71634934 & 3,701	  & 2,764   & 17,636  & 8,414	& 10/10 & 10/10 \\
37 & 253.62316424 &	253.61341154 & 253.19632297 & 1,215	  & 1,129   & 3,951	  & 12,937  & 10/10 & 10/10 \\
38 & 263.53652205 &	263.58677860 & 262.89961522 & 931	  & 576     & 12,798  & 7,328	& 10/10 & 8/10 \\
39 & 273.75141478 &	273.71426330 & 273.31495736 & 502	  & 1,832   & 9,137	  & 6,485	& 10/10 & 9/10 \\
40 & 284.30264444 &	284.21598927 & 283.79885749 & 1,877	  & 941	    & 9,339	  & 8,952   & 10/10 & 8/10 \\
41 & 293.89806626 &	293.78879283 & 293.78100971 & 1,555	  & 3,092   & 5,850	  & 15,329  & 4/10  & 7/10 \\
42 & 304.80698321 &	304.78182216 & 304.72298974 & 3,433	  & 2,463   & 10,126  & 8,594	& 6/10  & 5/10 \\
43 & 315.61313564 &	315.59938719 & 315.51991431 & 7,843	  & 6,097   & 33,285  & 21,319  & 5/10  & 8/10 \\
44 & 327.24688870 &	326.95644304 & 326.51876564 & 926	  & 10,043  & 6,842	  & 25,377  & 10/10 & 9/10 \\
45 & 338.08419513 &	337.93815812 & 337.63639881 & 2,859	  & 1,993   & 9,743	  & 9,301   & 10/10 & 6/10 \\
46 & ------------ &	349.05075115 & 349.01221399 & -----	  & 7,309   & -----	  & 21,865  & ----- & 8/10 \\
47 & ------------ &	360.33649558 & 360.28848158 & -----	  & 2,942   & -----	  & 23,459  & ----- & 8/10 \\
48 & ------------ &	371.24394236 & 371.14228033 & -----	  & 11,916  & -----	  & 19,141  & ----- & 6/10 \\
49 & ------------ &	382.35123818 & 382.35123818 & -----	  & 43,604  & -----	  & 96,244  & ----- & 7/10 \\
50 & 394.15415832 &	394.11379133 & 393.99311849 & 20,397  & 5,637   & 121,061 & 31,493  & 4/10  & 5/10 \\
51 & ------------ &	405.98821870 & 405.95674675 & -----	  & 14,394  & -----	  & 48,151  & ----- & 4/10 \\
52 & ------------ &	418.76983792 & 418.76983293 & -----	  & 18,557  & -----	  & 64,878  & ----- & 7/10 \\
53 & ------------ &	429.56613726 & 429.48485256 & -----	  & 1,693   & -----	  & 6,565   & ----- & 10/10 \\
54 & ------------ &	441.70943495 & 441.63484419 & -----	  & 18,031  & -----	  & 65,028  & ----- & 9/10 \\
55 & 453.27302397 &	453.23743150 & 452.98196941 & 134,338 &	20,197  & 142,763 & 73,761  & 2/10  & 6/10 \\
56 & ------------ &	466.65243154 & 466.65243154 & -----	  & 26,946  & -----	  & 61,915  & ----- & 2/10 \\
57 & ------------ &	479.14731853 & 479.14003521 & -----	  & 22,364  & -----	  & 34,921  & ----- & 5/10 \\
58 & ------------ &	490.74893276 & 490.74893276 & -----	  & 32,108  & -----	  & 59,991  & ----- & 4/10 \\
59 & ------------ &	502.95832470 & 502.95832470 & -----	  & 29,398  & -----	  & 68,242  & ----- & 7/10 \\
60 & 516.47881793 &	516.61305890 & 516.39141391 & 21,227  & 19,628  & 88,476  & 42,238  & 10/10 & 5/10 \\
61 & ------------ &	529.99890873 & 529.91176839 & -----	  & 15,608  & -----	  & 42,739  & ----- & 10/10 \\
62 & ------------ &	543.31155400 & 542.94950697 & -----	  & 9,993   & -----	  & 63,716  & ----- & 10/10 \\
63 & ------------ &	555.09335338 & 555.09322952 & -----	  & 3,492   & -----	  & 31,836  & ----- & 3/10 \\
64 & ------------ &	568.40130293 & 568.37716941 & -----	  & 18,011  & -----	  & 56,352  & ----- & 6/10 \\
65 & ------------ &	581.17833643 & 580.71949298 & -----	  & 4269    & -----	  & 32,981  & ----- & 8/10 \\
66 & ------------ &	595.94350942 & 595.93622413 & -----	  & 3719    & -----	  & 17,698  & ----- & 10/10 \\
67 & ------------ &	609.15441946 & 609.15441108 & -----	  & 13,464  & -----	  & 50,492  & ----- & 4/10 \\
68 & ------------ &	622.42276086 & 622.42125971 & -----	  & 12,293  & -----	  & 37,963  & ----- & 8/10 \\
69 & ------------ &	634.31384012 & 634.30215215 & -----	  & 27,068  & -----	  & 108,762 & ----- & 8/10 \\
70 & ------------ &	648.03770190 & 647.87846558 & -----	  & 39,457  & -----	  & 126,511 & ----- & 8/10 \\
71 & ------------ &	662.83805941 & 662.83401285 & -----	  & 52,603  & -----	  & 148,681 & ----- & 2/10 \\
72 & ------------ &	677.34672378 & 677.33531058 & -----	  & 19,837  & -----   & 88,927  & ----- & 5/10 \\
\noalign{\smallskip}\hline
\end{tabular}
\end{table}

\begin{table}[htbp]
\caption{Computational results for PAS-PCI, ASGO and the Packomania website when $r_i=\sqrt{i}.$}
\label{tab:4}
\centering
\begin{tabular}{l l l l l l l l c c}
\hline\noalign{\smallskip}
 &	Best-known  & Best-known  & Best-solution  & Best-time & Best-time & Average time & Average time & Hits  &	Hits \\
 \textit{n}       & ASGO        & Packomania  & PAS-PCI        & ASGO (s)      & PAS-PCI(s) & ASGO (s) &  PAS-PCI (s) & ASGO  & PAS-PCI \\
\noalign{\smallskip}\hline\noalign{\smallskip}

14 &	----------- &	20.03404652  &	20.03384653 &	-----  &	34     & -----   &	49     &	----  &	10/10 \\
15 &	21.29813169 &	21.29813169  &	21.29813169 &	101    &	37     & 275     &	139    &	10/10 &	10/10 \\
16 &	22.56309981 &	22.56309981  &	22.56309981 &	48     &	46     & 2,657   &	186    &	10/10 &	10/10 \\
17 &	23.87238984 &	23.87238984  &	23.87238984 &	1,201  &	193	   & 4,392   &	549    &	10/10 &	10/10 \\
18 &	25.29143658 &	25.30990723  &	25.27915927 &	215    &	135	   & 1,092   &	809    &	10/10 &	10/10 \\
19 &	26.64511657 &	26.66753375  &	26.62601755 &	424    &	183	   & 1,734   &	725    &	10/10 &	10/10 \\
20 &	27.99580859 &	27.99556516  &	27.97923319 &	126    &	154	   & 2,044   &	1,312  &	10/10 &	10/10 \\
21 &	29.33636969 &	29.37295726  &	29.30269792 &	219    &	186	   & 1,528   & 	1,286  &	10/10 &	10/10 \\
22 &	30.73679088 & 	30.74179521  &	30.09246437 &	382    &	182	   & 1,244   &	604    &	10/10 &	10/10 \\
23 &	32.02058355 &	32.03166165  &	32.00872179 &	2,200  &	1,019  & 6,229   &	2,964  &	10/10 &	10/10 \\
24 &	33.38242107 &	33.41437096  &	33.36991643 &	303    &	434	   & 1,909   &	1,653  &	10/10 &	10/10 \\
25 &	34.69652756 &	34.70564553  &	34.69392717 &	1,044  &	2,307  & 6,835   &	5,816  &	10/10 &	10/10 \\
26 &	36.05840859 &	36.07166003  &	36.02915819 &	981    &	794	   & 3,161   &	1,768  &	10/10 &	10/10 \\
27 &	37.32721394 &	37.35117334  &	37.31109810 &	6,268  &	962	   & 28,651  &	4,851  &	10/10 &	10/10 \\
28 &	38.68609137 &	38.69314892  &	38.62981649 &	16,538 &	3,843  & 28,586  &	4,327  &	10/10 &	10/10 \\
29 &	40.05783844 &	40.07711813  &	40.00191663 &	1,390  &	2,429  & 15,224  &	9,743  &	10/10 & 10/10 \\
30 &	41.42606085 &	41.45220322  &	41.38741929 &	2,917  &	1,846  & 7,565   &	3,012  &	10/10 &	10/10 \\
31 &	42.75687834 &	42.793380560 &	42.70018672 &	1,781  &	1,983  & 7,348   &	6,907  &	10/10 & 10/10 \\
32 &	44.04766016 &	44.063333662 &	44.03950493 &	2,728  &	4,212  & 52,999  &	15,471 &	10/10 &	10/10 \\
33 &	45.38587795 &	45.394745307 &	45.37281453 &	19,864 &	9,305  & 60,859  &	23,549 &	10/10 &	10/10 \\
34 &	46.75308313 &	46.752000809 &	46.71956130 &	6,204  &	3,189  & 33,474  &	18,681 &	10/10 &	10/10 \\
35 &	48.06709480 &	48.073923426 &	48.06074066 &	16,541 &	6,948  & 52,676  &	14,934 &	4/10  &	10/10 \\
36 &	49.40082616 &	49.400079475 &	49.37011019 &	9,568  &	5,513  & 17,251  &	9,626  &	2/10  &	10/10 \\
37 &	50.81979234 &	50.827145108 &	50,79142199 &	2,784  & 	4,367  & 7,033   &	19,238 &	10/10 &	10/10 \\
38 &	52.14070553 &	52.150810546 &	52.06979691 &	485    &	3,753  & 15,734  &	8,625  &	10/10 &	10/10 \\
39 &	53.44302697 &	53.473053122 &	53.37364937 &	3,995  &	2,364  & 21,022  &	17,682 &	10/10 &	10/10 \\
40 &	54.80450469 &	54.809098043 &	54.78167521 &	1,784  &	903	   & 10,028  &	7,108  &	10/10 &	9/10 \\
41 &	56.19655477 &	56.215141936 &	56.15964905 &	3,649  &	2,705  & 9,670   &	11,754 &	10/10 &	9/10 \\
42 &	57.47214913 &	57.484131297 &	57.40197437 &	3,406  &	1,983  & 14,909  &	13,421 &	10/10 &	9/10 \\
43 &	58.80263818 &	58.802206944 &	58.78746261 &	19,060 &	7,936  & 50,342  &	15,019 &	3/10  &	7/10 \\
44 &	60.20692438 &	60.210820103 &	60.15943733 &	4,821  &	9,208  & 21,833  &	18,229 &	10/10 &	7/10 \\
45 &	61.44936316 &	61.455016469 &	61.40695896 &	32,287 &	11,385 & 66,868  &	22,388 &	2/10  &	6/10 \\
50 &	68.20736878 &	68.231344973 &	68.16295751 &	3,799  &	3,748  & 20,153  &	17,997 &	8/10  &	6/10 \\
55 &	74.96860671 &	74.977762353 &	74.92900891 &	4,271  &	8,394  & 13,307  &	23,929 &	8/10  &	5/10 \\
60 &	81.54674520 &	81.546626989 &	81.51614965 &	85,661 &	34,091 & 106,258 &	52,672 &	2/10  &	4/10 \\

\noalign{\smallskip}\hline
\end{tabular}
\end{table}

\section{Discussion and conclusions}
\label{sec5}
This paper proposes a Partitioning Narrow Action Spaces and Circle Items (PAS-PCI) algorithm for packing unequal circles in a two-dimensional square container (PUC-SC). The effective LBFGS algorithm is applied to access a local minimum depending on the potential energy. To offer the best results of the search process and to improve on previous basin-hopping strategies, we present a new basin-hopping strategy consisting of two main ideas: the partition of the circular items based on their sizes and the partition of the narrow action spaces. We partition the circular items into four sets, $S_1$ to $S_4$, according to their radii from small to large and propose basin-hopping strategies on different sets to prevent local cycling and increase the possibility of finding appropriate unoccupied spaces for the circles with low computational complexity.

We approximate each circle item as a square item and measure the size of an action space in two ways, the length of the short side and the perimeter. We then sort all action spaces in non-ascending order based on the two metrics to order the two lists, which can find more suitable action spaces when moving squeezed circles, particularly small circles. Then, we partition all of the top narrow action spaces in the two lists by dividing each Narrow Action Space at the centre of the long side to produce two equal-size action spaces that we call Neighbour Action Spaces. We select two items with the greatest pain degree from $S_1$, or one from $S_1$ and the other from $S_2$, and perform Neighbour Space Occupying.

Furthermore, to enhance diversification in the process of research, we take the best features of the previous basin-hopping strategies and combine them with a perturbation operator by randomly swapping two large or small circles. Experimental results from two previous works, each of which consist of two sets of instances, show the effectiveness of the proposed method.

In future work, we will apply the idea of the Action Space (AS) and the Narrow Action Space (NAAS) to other circle packing problems, such as packing equal or unequal circles into a circular container. One could also expand our approach to address three-dimensional circle-packing problems.

\begin{acknowledgements}
We are grateful to the anonymous referees for valuable suggestions and comments that have helped us improve the paper. This work was supported by the National Natural Science Foundation of China (Grant no. 61472147, 61370183 and 61602196). We sincerely thank Eckard Specht for processing our results and publishing them on the Packomania website.
\end{acknowledgements}