The Max-cut problem is a well-known combinatorial optimization problem, which has many real-world applications. However, the problem has been proven to be non-deterministic polynomial-hard (NP-hard), which means that exact solution algorithms are not suitable for large-scale situations, as it is too time-consuming to obtain a solution. Therefore, designing heuristic algorithms is a promising but challenging direction to effectively solve large-scale Max-cut problems. For this reason, we propose a unique method which combines a pointer network and two deep learning strategies (supervised learning and reinforcement learning) in this paper, in order to address this challenge. A pointer network is a sequence-to-sequence deep neural network, which can extract data features in a purely data-driven way to discover the hidden laws behind data. Combining the characteristics of the Max-cut problem, we designed the input and output mechanisms of the pointer network model, and we used supervised learning and reinforcement learning to train the model to evaluate the model performance. Through experiments, we illustrated that our model can be well applied to solve large-scale Max-cut problems. Our experimental results also revealed that the new method will further encourage broader exploration of deep neural network for large-scale combinatorial optimization problems.

The service robots are becoming more and more popular in our daily life and bring us a lot of convenience. They also enter a few sports activities. For tennis playing, the tennis ball collection robot can relieve players' workload as people don't need to stoop to pick up tennis balls. There are two important tasks for a tennis ball collection robot. One is the recognition of tennis balls, and the other is the path planning of picking up balls. These two tasks can be fulfilled by machine learning algorithms. However, most conventional machine learning algorithms need hand-designed parameter, which are unable to design for these robotic tasks. Deep learning algorithms are base on nonlinear models which have great potential for these tasks. For this reason, we propose a tennis ball collection robot based on deep learning methods. For the path planning, we formulate it with the Travelling Salesman Problem (TSP) and then apply the Pointer Networks. And for tennis ball recognition, we use YOLO (You Only Look Once) model. These two models are implemented on NVIDIA Jetson TX1 board. With the proper training data set and training progress, these two models work well on the tennis ball collection robot.

In this paper, an improved you only look once (YOLOv3) algorithm is proposed to make the detection effect better and improve the performance of a tennis ball detection robot. The depth-separable convolution network is combined with the original YOLOv3 and the residual block is added to extract the features of the object. The feature map output by the residual block is merged with the target detection layer through the shortcut layer to improve the network structure of YOLOv3. Both the original model and the improved model are trained by the same tennis ball data set. The results show that the recall is improved from 67.70% to 75.41% and the precision is 88.33%, which outperforms the original 77.18%. The recognition speed of the model is increased by half and the weight is reduced by half after training. All these features provide a great convenience for the application of the deep neural network in embedded devices. Our goal is that the robot is capable of picking up more tennis balls as soon as possible. Inspired by the maximum clique problem (MCP), the pointer network (Ptr-Net) and backtracking algorithm (BA) are utilized to make the robot find the place with the highest concentration of tennis balls. According to the training results, when the number of tennis balls is less than 45, the accuracy of determining the concentration of tennis balls can be as high as 80%.