# T-BERT - Model for Sentiment Analysis of Micro-blogs
Integrating Topic Model and BERT

Sarojadevi Palani, Prabhu Rajagopal, and Sidharth Pancholi  Sarojadevi Palani
is with Center for Nondestructive Evaluation and Department of Mechanical
Engineering, Indian Institute of Technology, Madras, India (e-mail:
saroojadevi@gmail.com)Prof.Prabhu Rajagopal is with Center for Nondestructive
Evaluation and Department of Mechanical Engineering, Indian Institute of
Technology, Madras, India (e-mail: prajagopal@iitm.ac.in)Dr.Sidharth Pancholi
is with the Department of Electrical Engineering, Indian Institute of
Technology, Delhi, India (e-mail<EMAIL_ADDRESS>
###### Abstract

Sentiment analysis (SA) has become an extensive research area in recent years
impacting diverse fields including e-commerce, consumer business, and
politics, driven by increasing adoption and usage of social media platforms.
It is challenging to extract topics and sentiments from unsupervised short
texts emerging in such contexts, as they may contain figurative words,
strident data, and co-existence of many possible meanings for a single word or
phrase, all contributing to obtaining incorrect topics. Most prior research is
based on a specific theme/rhetoric/focused-content on a clean dataset. In the
work reported here, the effectiveness of BERT(Bidirectional Encoder
Representations from Transformers) in sentiment classification tasks from a
raw live dataset taken from a popular microblogging platform is demonstrated.
A novel T-BERT framework is proposed to show the enhanced performance
obtainable by combining latent topics with contextual BERT embeddings.
Numerical experiments were conducted on an ensemble with about 42000 datasets
using NimbleBox.ai platform with a hardware configuration consisting of Nvidia
Tesla K80(CUDA), 4 core CPU, 15GB RAM running on an isolated Google Cloud
Platform instance. The empirical results show that the model improves in
performance while adding topics to BERT and an accuracy rate of 90.81% on
sentiment classification using BERT with the proposed approach.

###### Index Terms:

BERT, Sentiment Analysis, Contextual topics, topic model.

##  I Introduction

The field of Sentiment Analysis (SA) studies opinions expressed in terms of
micro-blogs, texts, people’s interest or opinion towards a topic, about
product reviews, government policies, religion, etc. in natural human language
[1, 2, 3, 4].

Figure 1: Overall approach of proposed T-BERT

Businesses seek to use these contents in real time to understand how customers
perceive their products and formulate strategies accordingly. This information
can also be used to resolve product restrictions or monitor people’s attitudes
before new products are released [5]. The proliferation of these and also the
advancements in Natural Language Processing (NLP) has provided researchers in
giving more solutions to many engineered problems related to human language
focusing on people emotions and opinions. The explosion of online social
networking [3] on daily basis in turn demands the need of high Cloud computing
Graphics Processing Unit (GPU) and Tensor Processing Unit (TPU) processors
with a specialized purpose and architecture to store, process and analyse
them[6, 7, 8, 9, 10]. However, the critical part lies in mining people’s
opinions, intents towards discussions, emotions, any hidden patterns or latent
information in the form of any natural human-human readable canonical
language. Also, helpful data is covered in disarranged, inadequate, and
unstructured instant messages. Some researchers, propose to arrange a lot of
these messages or micro-blogs into groups with significant bunch marks, along
these lines give an outline of the substance to address clients data needs
[11, 12]. Statistical topic models fail to derive these patterns accurately
when it comes to large and heavy-tailed corpus texts [13, 14]. However,
transformer based pre-trained models such as BERT (Bidirectional Encoder
Representations from Transformers) overcomes the need of supervised learning
pattern. The transformers-based models [5] use a pre-trained sentence
embedding vectors which is trained on large corpora of data so that the
problem of supervised learning is not highly essential in here. It has been
argued that, today’s techniques limit the power of pre-trained
representations, especially for fine-tuning approaches due to the restriction
imposed on the standard uni-directional language models. For example, in
OpenAI GPT, where left-to-right architecture is used for pre-training ends up
in looking for only the previous tokens in the attention layers of the
transformers[15, 4]. This could be an acceptable approach while taking
sentence level tasks but while considering token level tasks such as question
answering, the fine-tuning tasks gets crucial as it involves processing from
both the directions[4]. In this research, a flexible framework to combine
latent topic information with BERT embeddings (T-BERT) to extract the
contextual topics from live twitter dataset is proposed to classify the
sentiments using BERT on the same. The main contributions of this proposed
approach are a) To build and develop modelS to extract latent topics b) To
develop BERT sentence embeddings to draw the contexts based on the semantic
similarity in the microblogs and merge them with LDA latent topics using a
deep learning auto-encoder. c) To propose and build a BERT Sentiment
classifier and to finally merge both contextual topics and sentiments for each
microblog using software engineering techniques. Some of the traditional
latent topics extraction methods plays excellent role in the areas of
Information Retrieval (IR), Cyberbullying, analysing political texts from
newspaper articles, large image content extraction, summarization etc. This
study could favour some real time applications as shown in Fig 1 where the
Topic/Aspect-based Sentiment analysis is taken advantage of: 1. Recommendation
systems 2. Market Research 3. Brand Monitoring 4. Earth quake detection
algorithms 5. Financial analysis 6. Bio-informatics 7. Social Network Analysis
(SNA) 8. Software engineering. The rest of the paper is structured as follows.
Section II Related Work walks through several Sentiment analysis, Topic
models, BERT based recent research papers. Section III; Explains algorithms
used and work methodology. Section IV; Explains the setup for numerical
experiments and various model hyper-parameters utilized. Empirical results of
the BERT contextual topics and BERT Sentiments are discussed in Section V,
after which the paper concludes with directions for further work.

##  II Related Work

Sentiment analysis on unstructured data such as micro-blogs or short-texts or
other inherently sparse data are conducted on various standard data sets where
the data is collected under specific theme or topics or politics or movie
reviews or using popular SemEval datasets [16, 17, 18, 5, 19]. However, in
this study the theme or topics or genre is unknown in the microblogs. [20]
conducted a theoretical study and comparison on the 3 levels of SA tasks on
short texts and gave a comprehensive state-of-art results based on the
algorithms implemented by multiple researchers. In recent years, research on
analysing short-texts and micro-blogs has peaked [13, 21, 22] due to the mass
usage of smart gadgets and social media platforms. [21] conducted numerical
experiments on Health Care Reform and United States Presidential election
debates in the year 2009 by taking polarity labeled datasets and proposed a
novel SA on micro-blogs incorporating homophily [23] in social networks,
additionally introducing topic context to cater the semantic relations between
them. In 2007, [14, 24] presented a sentiment polarity based TM to analyze
public satisfaction at the government in Surabaya city. A methodology based on
“Markov chain” was proposed by [14] where all the words in the same sentence
and its consecutive sentences falls under same topics and the model was
trained and inferred using Hidden Markov tools. A comparative study on various
TM techniques and Tool-kits from 2015 to 2020 evaluating performance metrics
on major application areas with an excellent high-level report are presented
in [25, 26, 27, 28, 29].

With the advancements in the Deep Learning Neural Networks and the increase in
the demand for many Natural Language Processing(NLP) tasks from various
domains and business intakes have led researches to make much deeper analyses
and helped develop the Transformers based architectures on top of DL networks
which could solve many NLP tasks in a much efficient and faster way
incorporating attention mechanism for robust training [30]. [Vaswani2017]
introduced a novel Transformer based architecture that uses the same encoder-
decoder network similar to seq2seq model with attention mechanism but does not
connote any LSTM, GRU or RNN networks. The Transformer architecture model
completely relies on Attention mechanism thereby avoiding recurrence to draw
global dependencies between the input and the output which in turn allows
parallelism. In late 2018, inspired by the Transformers architecture Google
[15] research team introduced a new deep Bidirectional Encoder Representations
from Transformers called BERT to alleviate the constraints imposed on
unidirectional methods. Sentiment analysis [31, 32, 22] outperformed with
improved F1 scores while pre-training with BERT classifiers. [32] performed a
sophisticated fine-grained sentiment analysis on publicly available popular
Stanford Sentiment Treebank (SST) dataset. A new algorithm formulating
specific training dataset for neural networks using Word2Vec and Bert to
detect sentiment values was introduced by [4]. Numerical experiments conducted
on Aspect-Based Sentiment Analysis (ABSA) [31, 33] by fine-tuning the
intermediate layers of BERT in the context of semantic detection between two
sentences [33]. BERT [15] performance on Semantic Textual Similarity(STS)
tasks such as sentence-pair regression had proven to be a state-art for many
NLP tasks but requires both the sentences to be fed to a cross-encoder
transformer network simultaneously to predict the output [34]. In this study,
SBERT(Sentence-BERT) introduced by [34] uses a different architecture called
Siamese and triplet network thereby comparing the semantically meaningful
sentences using cosine-similarity drastically reducing 65 hours of work load
to $\approx$5 seconds, with no compromise in accuracy from BERT is utilized
for generating sentence embedding vectors to ease computational power.

##  III METHODS

Inspired by BERT and the recent advancements in Transformers architecture [4]
T-BERT framework is proposed to show improved performance on topic model and
aims at predicting the sentiment polarity (positive, negative or neutral) of
the microblogs in study.

###  III-A DATASET AND PRE-PROCESSING

Data is extracted from popular micro-blogging platform Twitter via the link
https://apps.twitter.com/ using Tweepy API [35] credentials, python web
scrapping techniques and libraries without any search keywords or specific
topics of interest. In this study, around 40k raw microblog without any user
information are extracted into a spreadsheet and processed for data analysis.
The following pre-processing steps are performed before being fed into model
algorithms. 1. Canonicalization (Removal of numbers, Non-Ascii characters,
punctuation symbols, accents, and convert microblogs to lowercase.) 2. Removal
of URL links 3. Removal of Stop words 4. Replace emoticons with their original
text form 5. Stemming/Lemmatization – Converting to root words 6. Tokenization
of microblogs using tokenizer specific to BERT input and spacy libraries for
LDA topics.

$\displaystyle\noindent P(W,Z,\theta,\phi\mid\alpha,\beta)=$
$\displaystyle\prod_{j=1}^{M}P(\theta_{j};\alpha)\prod_{j=1}^{K}P(\phi_{i};\beta){\prod_{t=1}^{N}P(Z_{j,t}\mid\theta_{j}),P(W_{j,t}\mid\phi
Z_{j,t})}$ (1)

Figure 2: Detailed workflow of BERT + LDA using deep learning auto-encoder.

###  III-B LDA + BERT CONTEXTUAL TOPICS

LDA adopts a general probabilistic approach to model rich corpora of data.
Each tweet as input is represented as random mixture of latent topics (z),
where each topic is a collection or distribution of words (w) related to
topics. The goal of LDA is to arrive at a probabilistic model for a corpus of
documents that assigns high probability to the members of the documents and
also assigning high probability to other “similar” documents in the corpus.
The model algorithm works as to arrive at the topic’s distribution as referred
in the expanded equation in (III-A): Thus, $\alpha$ is the parameter of the
Dirichlet prior on the per-document topic distributions, $\beta$ is the
parameter of the Dirichlet prior on the per-topic word distribution. The
latent topic words are limited by the traditional structure of the LDA bag-of-
words and PoS tagging model, which cannot effectively compare the semantic
similarities in the tweet sentences and retrieve contextual information of the
text. Perhaps, BERT could alleviate this when combined with LDA and a detailed
process workflow of the same is shown in Fig. 2. In order to obtain the
contextual topics, the topic vectors ($\omega$) of LDA model are merged with a
collective contextual word embedding vectors (H) from Sentence-BERT model
using a gamma ($\gamma$) hyper-parameter to add relative importance to both
vectors as shown in (2). $H=BERT({x_{1}},...,{x_{T}})$

$\textit{Contextual Topic Vectors}(t)=\omega\gamma+H$ (2)

where ${x_{1},...,x_{T}}$ is a collective word vector of word embedding,
segment embedding, and position embedding of each tweet token; Trm stands for
Transformer encoder unit; $H=(w_{1},...,w_{T})$, and $w_{i}$ the averaged
output from 12 multi-headed transformer blocks given as token’s contextual
embedding vector representation. The combined vectors(t) are passed into a
deep learning auto-encoder latent vector space to ensure dimensionality
reduction and noise to arrive at the best topic clusters. The output of the
auto-encoder is a cluster of keywords, each falling into a specific unique
topic category using a K-Means clustering algorithm are labeled manually with
unique topics. This approach is expected to provide more accurate topic
semantic information for simulation on short tweet texts.

###  III-C BERT Sentiment Classification

The sentiment analysis model in Fig 3 aims to detect accurately the emotions
of the microblogs, grasp the semantic characteristics and rules of the
emotional evolution, and assist the contextual topics by adding value to the
business in terms of recommendations, aspect-based sentiments, understand user
intents to post relevant and appropriate ads etc. For the purpose of BERT pre-
training, SMILE Twitter Emotion dataset adapted from
https://figshare.com/articles/dataset/smile_annotations_final_csv/3187909 is
utilized and later the model is predicted for sentiments classes using twitter
dataset used for topics extraction in this study. Firstly, SMILE Twitter
emotion corpus is pre-trained in the BERT, after data pre-processing like
Canonicalization, tokenization using Bert tokenizer and finally the [CLS] and
[SEP] tokens are added at the appropriate positions by the model in itself.
Secondly, the tokenized corpus is used to perform in-depth pre-training of the
BERT target field on the constructed sentiment classifier. Fig 3 explains the
attention mechanism showing the weights of each word but the other words in
the tweet sentence and the words with contextual importance is highlighted in
darker color for each layer of the transformer blocks. For example, the word
‘Self’ carries importance when the word ‘you’ is read from left to right from
which the model learns the semantic similarities of the sentence thus
providing more accurate meaning behind the context, grammar and sentiments
being discussed. In order to learn semantic information from the twitter
texts, the transformer encoder connects the multi-headed self attention and
feed-forward through a residual network structure. The multi-headed mechanism
performs multiple linear transformations on the input vector to obtain
different linear values, and then calculates the attention weight as shown in
(3) and (4).

Figure 3: Workflow of BERT Sentiment Analysis detailing Self Attention

$\textit{MultiHead (Q, K, V)}=Concat(h_{1},h_{2},...,h_{T})W^{M}$ (3)
$HF=Attention(QW^{Q},KW^{K},VW^{V})$ (4)

where Q, K, V are the input word vector matrix of queries, keys and values
respectively. Attention is calculated after Q, K, and V are mapped through the
parameter matrix, and the calculation results are spliced after repeating t
times. $W^{M}$ is the weight matrix. $W^{Q}$, $W^{K}$, $W^{V}$ represents the
weight matrix corresponding to the $T^{th}$ hyper-parameter head. Thus, the
Transformer encoder learns and stores the semantic relationship and
grammatical structure information of the microblogs and based on this input
the SoftMax classifies the sentiments easily.

##  IV SETUP FOR NUMERICAL EXPERIMENTS

All numerical experiments were conducted with BERTBASE(uncased) with 12
transformer blocks, 768 hidden units, 12 self-attention heads and overall 110M
trainable parameters. Out of 42,626 raw tweets 23,329 tweets after pre-
processing are fed to LDA and Bert for contextual topic assessment and as test
dataset for sentiments predictions.

###  IV-A EVALUATION METRICS

The following metrics are used for Sentiment analysis

$\textit{{1) F1-Score}}=2\times\frac{(precision\times
recall)}{(precision+recall)}\in(0,1)$ (5)

$\textit{{2) Accuracy}}=\frac{(TN+TP)}{(TN+TP+FN+FP)}\in(0,1)$ (6)

Where TP is True Positive, FP is False Positive and FN is False Negative. For
topic model coherence scores measures and for Bert embeddings K-Means
clustering Silhouette metrics are considered.

$CoherenceScore=\sum_{i<j}score(w_{i},w_{j})$ (7)

###  IV-B Model Building and Hyper-parameters

In Engineering, LDA is set to automatically classify documents and estimate
their relevance to various latent topics hidden in them. In this study,
document term matrix after pre-processing is achieved using genism doc2bow
$($bag of words$)$ toolkit for a dictionary of 11057 unique words. Multiple
numerical experiments were conducted on LDA with random values of ($\alpha$)
alpha ranging between 0 $<$ $\alpha$ $<$ 1 (0.01, 0.1, 0.2 and 0.3) and the
optimal topic model(k) is arrived as shown from Fig 4.
Autoencoder Hyperparameters:
The list of hyper parameters to fine-tune auto encoder are:

  * •

Batch size

  * •

Epochs

  * •

Kernal_regularizers (L1 and L2) to add weights to the layers.

  * •

Dropouts to control over fitting.

  * •

Learning Rate.

  * •

Gamma parameter to control the relative importance of both LDA and Bert
vectors.

Extensive numerical experiments were conducted with various hyper-parameters
for fine tuning the auto-encoder layers for topics ranging from 5 – 17 are
displayed in Table I to compare the performance on each (k) value.

TABLE I: Summary of Auto-encoder Hyper-parameters used in LDA+BERT numerical
experiments Topics K (5,6,7,8,10,12,15,17), Optimizer = Adam, Gamma = 15
---
Epochs | Batch size | Regularizers | Dropout Rate
50 | 128 | L1(10e-4) | 0.01
100 | 128 | L1(10e-4) | 0.01
200 | 128 | L1(10e-4) | 0.01
300 | 128 | L1(10e-2) | 0.001
50 | 128 | L2(10e-4) | 0.1
500 | 128 |  | Bias_regularizer L2(1e-5),
---
Activity_regularizer L1(10e-2)
0.001
TABLE II: Experimental results of LDA and BERT Coherence scores for each topic(k) value in (%)  # of Topics(k) | LDA | BERT
---|---|---
5 | 0.402 | 0.481
6 | 0.430 | 0.490
7 | 0.474 | 0.451
8 | 0.501 | 0.521
10 | 0.483 | 0.504
12 | 0.537 | 0.459
15 | 0.567 | 0.441
17 | 0.621 | 0.460
Figure 4: Optimal Coherent model output showing (k) value 8 as cut-off point
Figure 5: Visualization of BERT Clustering experimented for varying number of
topic values (5,6,7,8,10,12,15,17)

##  V RESULTS and DISCUSSION

In this section, the empirical results of the numerical experiments and
related findings are evaluated to assess the effectiveness of the proposed
framework T-BERT. In particular the results of LDA are evaluated against BERT
and LDA+BERT. The metrics for each topic(k) shown in Fig 4 clearly indicating
a gradual rise in the coherence scores until the cut-off point, with k=8 being
optimal value. The dataset being unsupervised, BERT contextual embedding
results are clustered and visualized using K-Means clustering algorithm
grouping similar topics as shown in Fig 5 and the evaluation metrics from
Table II.

The weighted method obtains better accuracy’s in terms of coherence values
adding contexts to the topics(k=8) which makes the clustering of similar
topics look more meaningful than LDA topics. Adding weights to auto-encoder
layers using L1 Regularizers resulted in over-fitting. However, a dropout of
0.01 and Adam optimizer [Vaswani2017, 34, 33] at the input encoder layer
randomly turned off some redundant layers in the network avoiding over-fitting
and to ensure a robust model output displayed in Table III.

TABLE III: Final Auto-encoder Hyper-parameters Parameters | Values
---|---
Latent dimension | 64
Activation Function | RELU
Epochs | 50
Batch size | 128
Regularizers | L1(10e-4)
Gamma | 15
Dropout Rate | 0.01
Optimizer | Adam
TABLE IV: Final Metrics (%) for Contextual Topic Model (k = 8) comparing LDA, BERT and BERT+LDA  Metrics / Scores | LDA | BERT + Clustering |  | LDA + BERT +
---
Clustering
| C_V
---
(Coherence scores)
0.501 | 0.521 | 0.56
Silhouette | NA | 0.044 | 0.46

(a) BERT

(b) $LDA+BERT$

(c) Training and Validation Loss of Auto-encoder

Figure 6: Final Clusters for topic value k=8 along with Training and validation loss of Auto-encoder Figure 7: Visualization of word clouds after LDA and BERT merge. The contextual topic key words for optimal value k= 8 with each word cloud representing each topic clusters. TABLE V: BERT Hyper-parameters for Sentiments Classification Optimizer | AdamW (Pytorch)
---|---
Epochs | 10
Batch size | 32
Learning rate | 1e-5
Adam’s epsilon | 1e-8
Figure 8: BERT Sentiment predictions on test data-set TABLE VI: Accuracy per class – Validation results Class | Validation Accuracy (%)
---|---
Positive | 0.96
Negative | 0.78
Neutral | 0.69

The goal of this research to demonstrate performance improvement by adding
contextual sentence embedding of BERT with LDA topic model with proven
accuracy improvements as shown from Table IV. Fig 6(a) shows the clustering
results of BERT and Fig 6(b) the improved results of LDA+BERT showing a
balanced and quite separated clusters. The gains between each model are
relatively small, but the improvements of the method are reasonably straight
forward and flexible which makes it easier to apply to a variety of other
tasks. Visualization of word clouds for final 8 topics in Fig 7 shows that
each cluster highlights the proportionality and the frequency of words in
similar topics are grouped together. The words bigger in size directly relates
to its probability of the word occurrences within the topic. The goal for the
numerical experiments on BERT sentiment analysis is two-fold. First, is to
evaluate whether the training on the labeled is useful for validation on
sentiments classifier on Smile twitter dataset. Second, to evaluate the
performance and accuracy on testing the proposed twitter dataset and how well
the sentiments are classified on the test data. The model architecture is
built in such a way the data loader for both training and validation is
sampled from a random and sequential sampler respectively with a batch size of
32 using pytorch pre-trained bert uncased model on a 12GB GPU machines with a
fully connected layer. The summary of parameters used in the numerical
experiments are shown in the Table V. BERT significantly performs well in
classifying the emotions in terms of accuracies (%) as shown from Table VI. In
this this study, BERT pre-trained model with its bi-directional and attention
mechanism outperforms the predictions of emotions with its improved semantic
search approach compared to other state-of-art models.

##  VI CONCLUSION

The potential of leveraging the BERT attention mechanism is investigated in
this work, and the recommended contextual subjects and sentiments underlying
those topics (positive, negative, or neutral) are realized through the
enhanced performance of T-BERT. Results from numerical experiments demonstrate
the effectiveness and generality of the proposed approach. Future study could
concentrate on merging direct topic information into BERT pre-trained models
with more advanced ways to manage complicated data features, linguistic
skills, and semantic search, as well as identifying attitudes in languages
other than English.

## Acknowledgment

The first author would like to thank Liverpool John Moores University(LJMU),
UK for approving this research work as part of her Masters thesis
dissertation.

## References

  * [1] W. Medhat, A. Hassan, and H. Korashy, “Sentiment analysis algorithms and applications: A survey,” _Ain Shams Engineering Journal_ , vol. 5, no. 4, pp. 1093–1113, 12 2014. [Online]. Available: http://dx.doi.org/10.1016/j.asej.2014.04.011https://linkinghub.elsevier.com/retrieve/pii/S2090447914000550
  * [2] V. Sharma, V. Sharma, D. Shukla, P. Tanwar, and B. Kumar, “Live Twitter Sentiment Analysis,” _SSRN Electronic Journal_ , 2020. [Online]. Available: https://www.ssrn.com/abstract=3609792
  * [3] A. Hasan, S. Moin, A. Karim, and S. Shamshirband, “Machine Learning-Based Sentiment Analysis for Twitter Accounts,” _Mathematical and Computational Applications_ , vol. 23, no. 1, p. 11, 2018.
  * [4] V. Moshkin, A. Konstantinov, and N. Yarushkina, “Application of the BERT Language Model for Sentiment Analysis of Social Network Posts,” in _NAACL HLT 2019 - 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies - Proceedings of the Conference_ , J. J. Park, L. T. Yang, Y.-S. Jeong, and F. Hao, Eds. Singapore: Springer Singapore, 2020, vol. 1, no. Mlm, pp. 274–283. [Online]. Available: http://link.springer.com/10.1007/978-3-030-59535-7_20
  * [5] U. Naseem, I. Razzak, K. Musial, and M. Imran, “Transformer based Deep Intelligent Contextual Embedding for Twitter sentiment analysis,” _Future Generation Computer Systems_ , vol. 113, pp. 58–69, 12 2020. [Online]. Available: https://doi.org/10.1016/j.future.2020.06.050https://linkinghub.elsevier.com/retrieve/pii/S0167739X2030306X
  * [6] Q. Li, S. Li, S. Zhang, J. Hu, and J. Hu, “A Review of Text Corpus-Based Tourism Big Data Mining,” _Applied Sciences_ , vol. 9, no. 16, p. 3300, 8 2019. [Online]. Available: https://www.mdpi.com/2076-3417/9/16/3300
  * [7] S. N. Balaji, P. V. Paul, and R. Saravanan, “Survey on sentiment analysis based stock prediction using big data analytics,” in _2017 Innovations in Power and Advanced Computing Technologies (i-PACT)_ , vol. 2017-Janua. IEEE, 4 2017, pp. 1–5. [Online]. Available: http://ieeexplore.ieee.org/document/8244943/
  * [8] I. E. Alaoui, Y. Gahi, and R. Messoussi, “Full Consideration of Big Data Characteristics in Sentiment Analysis Context,” in _2019 IEEE 4th International Conference on Cloud Computing and Big Data Analysis (ICCCBDA)_. IEEE, 4 2019, pp. 126–130. [Online]. Available: https://ieeexplore.ieee.org/document/8725728/
  * [9] C. K.-S. Leung, F. Jiang, A. G. M. Pazdor, and A. M. Peddle, “Parallel social network mining for interesting ‘following’ patterns,” _Concurrency and Computation: Practice and Experience_ , vol. 28, no. 15, pp. 3994–4012, 10 2016. [Online]. Available: http://doi.wiley.com/10.1002/cpe.3773
  * [10] S. Dwivedi and V. S. K. Roshni, “Recommender system for big data in education,” in _2017 5th National Conference on E-Learning & E-Learning Technologies (ELELTECH)_, vol. 2. IEEE, 8 2017, pp. 1–4. [Online]. Available: http://ieeexplore.ieee.org/document/8074993/
  * [11] Z. Shah and A. G. Dunn, “Event detection on Twitter by mapping unexpected changes in streaming data into a spatiotemporal lattice,” _IEEE Transactions on Big Data_ , vol. 1, no. 1, pp. 1–1, 3 2019. [Online]. Available: http://ieeexplore.ieee.org/document/7153539/https://ieeexplore.ieee.org/document/8883055/
  * [12] X. Hu, L. Tang, and H. Liu, “Embracing information explosion without choking: Clustering and labeling in microblogging,” _IEEE Transactions on Big Data_ , vol. 1, no. 1, pp. 35–46, 2015.
  * [13] X. Cheng, X. Yan, Y. Lan, and J. Guo, “BTM: Topic Modeling over Short Texts,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 26, no. 12, pp. 2928–2941, 12 2014. [Online]. Available: http://ieeexplore.ieee.org/document/6778764/
  * [14] G. Amit, R.-Z. Michal, and Y. Weiss, “Hidden Markoc Topic Models,” 2007.
  * [15] J. Devlin, M. W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of deep bidirectional transformers for language understanding,” in _NAACL HLT 2019 - 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies - Proceedings of the Conference_ , vol. 1, 10 2019, pp. 4171–4186. [Online]. Available: http://arxiv.org/abs/1810.04805
  * [16] Q. Chen and M. Sokolova, “Word2Vec and Doc2Vec in Unsupervised Sentiment Analysis of Clinical Discharge Summaries,” 5 2018. [Online]. Available: http://arxiv.org/abs/1805.00352
  * [17] Z. Jianqiang, G. Xiaolin, and Z. Xuejun, “Deep Convolution Neural Networks for Twitter Sentiment Analysis,” _IEEE Access_ , vol. 6, pp. 23 253–23 260, 2018. [Online]. Available: https://ieeexplore.ieee.org/document/8244338/
  * [18] A. Abdi, S. M. Shamsuddin, S. Hasan, and J. Piran, “Deep learning-based sentiment classification of evaluative text based on Multi-feature fusion,” _Information Processing & Management_, vol. 56, no. 4, pp. 1245–1259, 7 2019. [Online]. Available: https://doi.org/10.1016/j.ipm.2019.02.018https://linkinghub.elsevier.com/retrieve/pii/S0306457318307416
  * [19] P. Ray and A. Chakrabarti, “A Mixed approach of Deep Learning method and Rule-Based method to improve Aspect Level Sentiment Analysis,” _Applied Computing and Informatics_ , vol. ahead-of-p, no. ahead-of-print, 8 2020. [Online]. Available: https://www.emerald.com/insight/content/doi/10.1016/j.aci.2019.02.002/full/html
  * [20] A. Alsaeedi and M. Z. Khan, “A study on sentiment analysis techniques of Twitter data,” _International Journal of Advanced Computer Science and Applications_ , vol. 10, no. 2, pp. 361–374, 2019.
  * [21] X. Zou, J. Yang, and J. Zhang, “Microblog sentiment analysis using social and topic context,” _PLoS ONE_ , vol. 13, no. 2, pp. 1–24, 2018.
  * [22] J. Zheng, X. Chen, Y. Du, X. Li, and J. Zhang, “Short Text Sentiment Analysis of Micro-blog Based on BERT,” in _Lecture Notes in Electrical Engineering_. Springer Verlag, 2020, vol. 590, pp. 390–396. [Online]. Available: http://link.springer.com/10.1007/978-981-32-9244-4_56
  * [23] F. Ren and Y. Wu, “Predicting user-topic opinions in twitter with social and topical context,” _IEEE Transactions on Affective Computing_ , vol. 4, no. 4, pp. 412–424, 2013.
  * [24] M. N. Aziz, A. Firmanto, A. M. Fajrin, and R. V. Hari Ginardi, “Sentiment Analysis and Topic Modelling for Identification of Government Service Satisfaction,” in _2018 5th International Conference on Information Technology, Computer, and Electrical Engineering (ICITACEE)_. IEEE, 9 2018, pp. 125–130. [Online]. Available: https://ieeexplore.ieee.org/document/8576974/
  * [25] R. Albalawi, T. H. Yeap, and M. Benyoucef, “Using Topic Modeling Methods for Short-Text Data: A Comparative Analysis,” _Frontiers in Artificial Intelligence_ , vol. 3, no. July, pp. 1–14, 7 2020. [Online]. Available: https://www.frontiersin.org/article/10.3389/frai.2020.00042/full
  * [26] C. Li, H. Wang, Z. Zhang, A. Sun, and Z. Ma, “Topic modeling for short texts with auxiliary word embeddings,” _SIGIR 2016 - Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pp. 165–174, 2016.
  * [27] W. Gao, M. Peng, H. Wang, Y. Zhang, Q. Xie, and G. Tian, “Incorporating word embeddings into topic modeling of short text,” _Knowledge and Information Systems_ , vol. 61, no. 2, pp. 1123–1145, 2019. [Online]. Available: https://doi.org/10.1007/s10115-018-1314-7
  * [28] A. B. Dieng, F. J. R. Ruiz, and D. M. Blei, “Topic Modeling in Embedding Spaces,” _Transactions of the Association for Computational Linguistics_ , vol. 8, pp. 439–453, 2020.
  * [29] F. Hu, G.-s. Xia, W. Yang, and L. Zhang, “Mining Deep Semantic Representations for Scene Classification of High-Resolution Remote Sensing Imagery,” _IEEE Transactions on Big Data_ , vol. 6, no. 3, pp. 522–536, 9 2020. [Online]. Available: https://ieeexplore.ieee.org/document/8713925/
  * [30] I. Sutskever, O. Vinyals, and Q. V. Le, “Sequence to sequence learning with neural networks,” _Advances in Neural Information Processing Systems_ , vol. 4, no. January, pp. 3104–3112, 2014.
  * [31] M. Hoang, O. A. Bihorac, and J. Rouces, “Aspect-Based Sentiment Analysis using {BERT},” _Proceedings of the 22nd Nordic Conference on Computational Linguistics_ , pp. 187–196, 2019. [Online]. Available: https://www.aclweb.org/anthology/W19-6120
  * [32] M. Munikar, S. Shakya, and A. Shrestha, “Fine-grained Sentiment Classification using BERT,” _International Conference on Artificial Intelligence for Transforming Business and Society, AITB 2019_ , pp. 2–5, 2019\.
  * [33] Y. Song, J. Wang, Z. Liang, Z. Liu, and T. Jiang, “Utilizing BERT Intermediate Layers for Aspect Based Sentiment Analysis and Natural Language Inference,” 2 2020. [Online]. Available: https://arxiv.org/abs/2002.04815http://arxiv.org/abs/2002.04815
  * [34] N. Reimers and I. Gurevych, “Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks,” in _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_. Stroudsburg, PA, USA: Association for Computational Linguistics, 8 2019, pp. 3980–3990. [Online]. Available: https://arxiv.org/abs/1908.10084http://arxiv.org/abs/1908.10084https://www.aclweb.org/anthology/D19-1410
  * [35] B. Lwowski, P. Rad, and K.-K. R. Choo, “Geospatial event detection by grouping emotion contagion in social media,” _IEEE Transactions on Big Data_ , vol. 6, no. 1, pp. 159–170, 2018.


Scaling Motion Planning Infeasibility Proofs

Sihui Li^1 and Neil T. Dantam^1

This work was supported by NSF IIS-1849348,
NSF CCF-2124010,
ONR N00014-21-1-2418, and ARL TBAM-CRP [W911NF-
^1 Sihui Li and Neil T. Dantam are with the Department of Computer Science,
Colorado School of Mines, USA.
{li<EMAIL_ADDRESS>
Achieving completeness in the motion planning problem demands substantial computation power, especially in high dimensions. Recent developments in parallel computing have rendered this more achievable. We introduce an embarrassingly parallel algorithm for constructing infeasibility proofs. Specifically, we design and implement a manifold triangulation algorithm on GPUs based on manifold tracing with Coxeter triangulation. To address the challenge of extensive memory usage within limited GPU memory resources during triangulation, we introduce batch triangulation as part of our design. The algorithm provides two orders of magnitude speed-up compared to the previous method for constructing infeasibility proofs. The resulting asymptotically complete motion planning algorithm effectively leverages the computational capabilities of both CPU and GPU architectures and maintains minimum data transfer between the two parts. We perform experiments on 5-DoF and 6-Dof manipulator scenes.

§ INTRODUCTION

A complete motion planer returns a plan or report plan non-existence in finite time. Previous work has shown that motion planning is PSPACE-hard <cit.>, which means solving the motion planning problem completely is an inherently computationally heavy process in high dimensions. Because of this, most previous works in motion planning <cit.> focus on solving one part of this problem - finding a valid plan. The second part, which is proving path non-existence, is largely omitted.
Path non-existence guarantees, or what we call infeasibility proofs, are becoming more crucial as we move into higher-level planning problems <cit.>, where motion planning is a sub-routine.

In our previous work, we proposed an asymptotically complete algorithm framework <cit.>. A motion planner is asymptotically complete if it returns a plan or an infeasibility proof given long enough time. The algorithm runs alone-side a sampling-based motion planner <cit.>, finds a plan if a plan exists, or returns an infeasibility proof otherwise. For finding infeasibility proofs, the core idea is to create a “closure” in the obstacle region of the configuration space that separates the start and the goal. The algorithm first learns a manifold from samples in the configuration space, and then triangulation the manifold to make sure it is entirely in the obstacle region. The algorithm scales up to 5-DoF <cit.>. The main limitation is on the manifold triangulation step and collision checking, which takes over $95\%$ of the total runtime.

To deal with the increased computation needs in higher dimensions, one way is to take advantage of multi-core or specialized hardware. Prior work has used
multi-core CPUs to parallelize
sampling <cit.> or nearest
neighbor search <cit.>, GPUs for nearest
neighbor search <cit.> and collision
checking <cit.>, and FPGAs for collision
checking <cit.>.

[node_style/.style=draw, rectangle, rounded corners,
inf_node/.style=node_style, fill=orange!30,
arrow_style/.style=thick, -Stealth]
[node_style,fill=blue!10, dashed, minimum width = 8.8cm, minimum height=2cm] (cpu) at (-0.1cm, -0.5cm) ;
[node_style,fill=blue!20] (planner) at (0, 0) Sampling-Based Planner;
[label=left:CPU] (s0) at (-2.8cm, 0.2cm);
below left=0.4cm and -1cm of planner] (learnm) Learn Manifold;
[inf_node, below right=0.4cm and -1cm of planner] (samplem) Sample Manifold;
[->, arrow_style] ($(planner.south) - (0.5cm, 0cm)$) – (learnm.north east);
[->, arrow_style] (samplem.north west)–($(planner.south) + (0.5cm, 0cm)$);

[arrow_style] (learnm.east) – (samplem.west);

[single arrow, draw=black, fill=yellow!50,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=10mm, below left=2.1cm and -1.5cm of planner, rotate=-90] (cpu2gpu) ;
[single arrow, draw=black, fill=yellow!50,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=10mm, below right=2.2cm and -1.5cm of planner, rotate=90] (gpu2cpu);
[align=center, below left=-0.5 cm and 0.3cm of cpu2gpu, minimum width=1.5cm, minimum height=1cm] Manifold,
Manifold Points,
Scene information;
[align=center, below right=-0.4cm and 0.2cm of gpu2cpu, minimum width=1.5cm, minimum height=1cm] Manifold Points,
in $\CFree$;

[node_style,fill=red!10, dashed, minimum width = 8.8cm, minimum height=6.2cm] (gpu) at (-0.1cm, -6.2cm) ;
[label=left:GPU] (s0) at (-2.8cm, -3.4cm);
[inf_node, above left =-2cm and -2.4cm of gpu] (triangulation)Triangulation;
decoration = brace,
amplitude=10pt] ($(triangulation.east) + (0.3cm, -0.7cm)$) –  ($(triangulation.east) + (0.3cm, 0.7cm)$);

xshift=0, every node/.append style=

[black, thick] ($(triangulation.east) + (\x + \dx, \y)$) rectangle  ($(triangulation.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(triangulation.east) + (\x, \y + \i * 0.2)$) –  ($(triangulation.east) + (\x + \dx, \y + \i * 0.2)$);

xshift=0, every node/.append style=

[black, thick] ($(triangulation.east) + (\x + \dx, \y)$) rectangle  ($(triangulation.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(triangulation.east) + (\x, \y + \i * 0.2)$) –  ($(triangulation.east) + (\x + \dx, \y + \i * 0.2)$);

[align=center, above right=+0.15 and +of triangulation.east] ...;

[draw, align=center, above right=0.2cm and 0.4cm of triangulation, minimum width=1.5cm, minimum height=1cm] (le)Locate

xshift=0, every node/.append style=

[black, thick] ($(triangulation.east) + (\x + \dx, \y)$) rectangle  ($(triangulation.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(triangulation.east) + (\x, \y + \i * 0.2)$) –  ($(triangulation.east) + (\x + \dx, \y + \i * 0.2)$);

xshift=0, every node/.append style=
[black, thick] ($(triangulation.east) + (\x + \dx, \y)$) rectangle  ($(triangulation.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(triangulation.east) + (\x, \y + \i * 0.2)$) –  ($(triangulation.east) + (\x + \dx, \y + \i * 0.2)$);

[align=center, above right=+0.15 and +of triangulation.east] ...;

[draw, align=center, above right=0.2cm and 2.6cm of triangulation] (se) Search

xshift=0, every node/.append style=
[black, thick] ($(triangulation.east) + (\x + \dx, \y)$) rectangle  ($(triangulation.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(triangulation.east) + (\x, \y + \i * 0.2)$) –  ($(triangulation.east) + (\x + \dx, \y + \i * 0.2)$);

xshift=0, every node/.append style=
[black, thick] ($(triangulation.east) + (\x + \dx, \y)$) rectangle  ($(triangulation.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(triangulation.east) + (\x, \y + \i * 0.2)$) –  ($(triangulation.east) + (\x + \dx, \y + \i * 0.2)$);

[align=center, above right=+0.15 and +of triangulation.east] ...;

[draw, align=center, above right=0.2cm and 4.4cm of triangulation] (fs) Find

[single arrow, draw=black, fill=black!20,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=7mm, below right=0.7cm and 2cm of triangulation, rotate=-90] ;

[inf_node, minimum width= 2cm, align=center, above left =-5.7cm and -2.4cm of gpu] (batchtri) Batch
decoration = brace,
amplitude=7pt] ($(batchtri.east) + (0.3cm, -0.7cm)$) –  ($(batchtri.east) + (0.3cm, 0.7cm)$);

xshift=0, every node/.append style=
[black, thick] ($(batchtri.east) + (\x + \dx, \y)$) rectangle  ($(batchtri.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(batchtri.east) + (\x, \y + \i * 0.2)$) –  ($(batchtri.east) + (\x + \dx, \y + \i * 0.2)$);

xshift=0, every node/.append style=
[black, thick] ($(batchtri.east) + (\x + \dx, \y)$) rectangle  ($(batchtri.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(batchtri.east) + (\x, \y + \i * 0.2)$) –  ($(batchtri.east) + (\x + \dx, \y + \i * 0.2)$);

[align=center, above right=+0.15 and +of batchtri.east] ...;

[draw, align=center, above right=0.2cm and -0.1cm of batchtri, minimum width=1.5cm, minimum height=1cm] (fle) Find Local

xshift=0, every node/.append style=
[black, thick] ($(batchtri.east) + (\x + \dx, \y)$) rectangle  ($(batchtri.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(batchtri.east) + (\x, \y + \i * 0.2)$) –  ($(batchtri.east) + (\x + \dx, \y + \i * 0.2)$);

xshift=0, every node/.append style=
[black, thick] ($(batchtri.east) + (\x + \dx, \y)$) rectangle  ($(batchtri.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(batchtri.east) + (\x, \y + \i * 0.2)$) –  ($(batchtri.east) + (\x + \dx, \y + \i * 0.2)$);

[align=center, above right=+0.15 and +of batchtri.east] ...;

[draw, align=center, above right=0.2cm and 2.2cm of batchtri, minimum height=1cm] (ci) Compute

xshift=0, every node/.append style=
[black, thick] ($(batchtri.east) + (\x + \dx, \y)$) rectangle  ($(batchtri.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(batchtri.east) + (\x, \y + \i * 0.2)$) –  ($(batchtri.east) + (\x + \dx, \y + \i * 0.2)$);

xshift=0, every node/.append style=
[black, thick] ($(batchtri.east) + (\x + \dx, \y)$) rectangle  ($(batchtri.east) + (\x+\dx + 0.08, \y+\dy)$);
ıin 0,...,3
[draw=blue, very thick, decorate,
decoration = snake,
pre length=0.3pt,post length=5pt,
, arrow_style] ($(batchtri.east) + (\x, \y + \i * 0.2)$) –  ($(batchtri.east) + (\x + \dx, \y + \i * 0.2)$);

[align=center, above right=+0.15 and +of batchtri.east] ...;

[draw, align=center, above right=0.2cm and 4.7cm of batchtri] (cc) Collision
[->, arrow_style] (le.east)–(se.west);
[->, arrow_style] (se.east)–(fs.west);
[->, arrow_style] (fle.east)–(ci.west);
[->, arrow_style] (ci.east)–(cc.west);

[label=above: Run in Batches] (rb) at ($(ci.east) + (-0.8, 0.9)$);

Algorithm overview. The algorithm maximizes resource utilization by efficiently distributing its components across both CPU and GPU. The triangulation and the collision checking steps are completed entirely on GPU.

In this work, we present an embarrassingly parallel algorithm for constructing infeasibility proofs on GPUs.
This algorithm runs two orders of magnitudes faster than our previous algorithm through vast parallelism in the triangulation step and collision checking.
<ref> shows the overall algorithm structure. The entire triangulation and collision checking step runs on GPU, which ensures minimum data transfer between CPU and GPU.
We design the triangulation algorithm based on manifold tracing with Coxeter triangulation <cit.> to fit the computation architecture of GPUs. To handle the significant memory requirements within the constraints of limited GPU memory during triangulation, we design the algorithm to support batch triangulation. We also perform collision checking on GPU based on spherical robots and primary-shaped environments. We perform experiments on up to 6-DoF robots to show the scalability of our algorithm.

§ RELATED WORK

§.§ Infeasibility Proof

Many sampling-based motion planners are probabilistically complete <cit.>, meaning they can find a plan given long enough time. However, they cannot provide path non-existence guarantees. There are previous works that construct exact path non-existence
guarantees. <cit.> proves path non-existence for
single, rigid objects in a 2D or 3D workspace to guarantee stable
<cit.> considers the specific problem of a
rigid body passing through a narrow gate.
<cit.> constructs alpha-shapes in the obstacle
region to query the connectivity of two configurations, which works
for up to 3-dimensional configuration spaces. These methods do not
apply to general manipulators' configuration spaces.

There are also methods that provide approximate path non-existence guarantees.
In visibility <cit.> and
sparsity <cit.> based planners,
if no plan is found when the algorithm terminates, the problem
may be considered infeasible to some extent since they achieve high coverage of the free space <cit.>.

In deterministic sampling-based motion planning, if no plan is found, then either
no solution exists or a solution exists only through some narrow
passages <cit.>.
Previous works have also proposed learning-based methods to
predict infeasible
plans <cit.>.
All of these methods do not provide exact plan non-existence guarantees.

Previously, we have done a series of work on constructing infeasibility proofs in general configuration spaces. In <cit.>, we defined infeasibility proof and proposed our first method for infeasibility proof construction. Based on this work, we proposed a learning and sampling framework to construct infeasibility proof <cit.>. We scaled this work by adapting Coxeter triangulation <cit.> into our framework <cit.>, which eventually got the algorithm to run for up to 5-DoF manipulators' configuration space. In this work, we scale this algorithm framework further to run in 6-D by re-designing the triangulation algorithm for GPU parallelization.

§.§ Parallel Computing in Motion Planning

Because motion planning is a computational-heavy problem, previous work has made various efforts in paralleling the processes to improve runtime. In this section, we provide an overview of parallelism utilization in prior works, categorizing them according to hardware types, as parallelizing schemes could differ significantly across different hardware platforms.

Parallelism on CPUs usually happens at the algorithmic level, where tasks are divided into smaller, independent units that can be executed simultaneously. Early works <cit.> looked at how to distribute search efforts among many processors based on gradient descent and random walk.
Previous work has also looked at parallelizing sampling-based motion planners <cit.>, through parallelizing sampling and growth of the search tree or graph; and parallelizing search of decomposed configuration space. Search-based planning has also seen application with parallel computing <cit.>. CPU fine-grained parallelization is also possible. In a recent work <cit.>, the authors achieve microsecond-level motion planning through fine-grained parallelism for forward kinematics and collision checking using CPU SIMD instructions.

Modern GPUs have a significantly higher number of cores compared to CPUs, enabling the potential for greater speed-ups. Recent work <cit.> provides a GPU-accelerated library that runs trajectory optimization in parallel with many seeds. Previous work has explored the utilization of GPUs to accelerate particular time composing parts of motion planning such as collision checking and nearest neighbor calculation <cit.>. Computation of Generalized Voronoi Diagrams on GPUs has also been explored for real-time motion planning <cit.>.
Field-programmable gate arrays (FPGAs) are employed in motion planing <cit.>, substantially speeding up collision checking and edge validation.
In this work, we employ GPUs to construct infeasibility proofs.

§ PROBLEM DEFINITION

The inputs of motion planning
problem <cit.> consist of a configuration space
$\CSpace$ of dimension $n$, a start configuration $\qstart$, and a
goal configuration $\qgoal$.  The configuration space $\CSpace$ is the
union of the disjoint obstacle region $\CObs$ and free space
$\CObs$ and $\CFree$ are
implicitly defined through a validity checking function. Given a configuration, the function returns whether the robot in the configuration collides
with obstacles or not.  Both $\qstart$ and
$\qgoal$ are in $\CFree$.

The output is either a plan or an infeasibility proof in the limit.
When a plan exists, the output is a plan $\sigma$ such that
$\sigma[0, 1] \in \CFree$, $\sigma[0] = \qstart$,
$\sigma[1] = \qgoal$.  When there is no feasible plan, the output is
an infeasibility proof.  An infeasibility proof
is a closed manifold defined through an implicit function $\infproof(\conf) = 0$ that lies entirely in the obstacle
region, $\{\conf \mid \infproof(\conf) = 0\} \subseteq \mathcal{C}_{obs}\}$, and separates $\qstart$ and $\qgoal$, $\infproof(\qstart) \infproof(\qgoal) < 0$ <cit.>.

In this work, we consider kinematic problems only, that is, $\CObs$ is only caused by robot and obstacle geometries in the workspace. Also, we assume an Euclidean configuration space instead of a
metric space (e.g. $\SEthree$). More details on configuration space requirements are in <cit.>.

§ BACKGROUND

§.§ Infeasibility Proof Construction

This work is based on a previous algorithm framework we proposed <cit.> that combines learning and sampling to construct infeasibility proofs. The algorithm runs in parallel with sampling-based motion
planners (i.e. PRM). We treat the sampled configurations as data. One class contains all samples connectable to the start (or goal); The other class contains all other samples. Then we train a classifier with these two classes of samples. The resulting manifold converges to an infeasibility proof as we defined in <ref> <cit.>. Then we triangulate the manifold to produce a piece-wise linear approximation of the manifold. Lastly, we check that the triangulation is entirely in $\CObs$ with configuration space penetration depth <cit.> or simplex decomposition <cit.>.
The major scalability limit of this algorithm is the demanding computation time for the triangulation and checking step in high dimensions. In this work, we address this challenge by employing GPU computation for both triangulation and collision checking.

§.§ Permutahedral Representation

This section provides a brief introduction of the permutahedral representation <cit.> used in the manifold tracing algorithm with Coxeter triangulation.
Coxeter triangulation is a way to triangulate any $n$-dimensional Euclidean space $\Re^n$, and is defined using root systems <cit.>. A root system can be viewed as a set of basis vectors for the triangulation. Permutahedral representation <cit.> provides a compact way to represent simplices in $\Re^n$ Coxeter triangulation.
For a $k$-simplex in $\Re^n$ Coxeter triangulation, the representation has two parts, a vertex and a partition.
The vertex is the smallest vertex of the $k$-simplex in the lexicographical order, represented with a list of $n$ integer values $[v_0, v_1, ..., v_{n-1}]$ that corresponds to the coordinate of the vertex in $\Re^n$.
The partition is an ordered partition of $\{0, 1, ..., n\}$ in $k+1$ parts, and represents the cycle of how other vertices of the simplex are located using the triangulation's root system. <ref> shows the permutahedral representation of two $2$-simplices in a square.
The permutahedral representation supports several essential queries within the triangulation algorithm based on manifold tracing. These queries include finding vertices, faces, and cofaces of a simplex, as well as locating points within $n$-simplices. For further details on how to perform these queries, please refer to <cit.>.

on each segment/.style=
show path construction,
moveto code=,
lineto code=
() – ();
curveto code=
[#1] ()
.. controls
() and ()
closepath code=
() – ();

mid arrow/.style=postaction=decorate,decoration=
mark=at position .5 with [#1]stealth
left arrow/.style=postaction=decorate,decoration=
mark=at position .7 with [#1]stealth

[label=below left:$v_0: [0, 0]$] (v0) at (0, 0);
[label=below right:$v_1$: [1, 0]] (v1) at (, 0);
[label=above right:$v_2$: [1, 1]] (v2) at (, );
[label=above left:$v_3$: [0, 1]] (v3) at (0, );
[label=above left:$v: [0, 0]$] (s0) at (+ 1.45cm, /2);
[label=above left:$p:\{\{0\}, \{1\}, \{2\}\}$] (s0) at (+ 3cm, /2-0.4cm);
[label=above left:$v: [0, 0]$] (s1) at (- 3.5cm, /2);
[label=above left:$p:\{\{1\}, \{0\}, \{2\}\}$] (s1) at (- 2cm, /2-0.4cm);

[draw, fill=red!30!white, line width=1pt, postaction=on each segment=mid arrow=black]  (v0) – (v1)–(v2)–cycle;
[draw, fill=blue!30!white, line width=1pt, postaction=on each segment=mid arrow=black]  (v0) – (v3)–(v2)–cycle;

Example 2D permutahedral representation, “v” for vertex, “p” for partition, for the two triangles (blue and red) in a square.

§ ALGORITHM

The algorithm leverages the computational power of both CPUs and GPUs. We keep the parts that already run reasonably fast and/or require a lot of branching on the CPU, and move the highly parallelizable and time-consuming parts to the GPU. <ref>
shows the overall algorithm structure.
Using this structure, we can maintain minimum data transfer between the CPU and the GPU. We run manifold learning and manifold sampling on CPU. The CPU transfers the learned manifold and a set of manifold points to the GPU for triangulation, and robot kinematic and world geometry information to the GPU for collision checking. The triangulation and collision checking steps are completed on GPU. The computation on the GPU generates a large amount of data but only needs to transfer the $\CFree$ manifold points to the CPU.
Previously, we also need to decompose the facets of the triangulation for collision checking within a minimum distance. In this work, batch triangulation in the triangulation algorithm removes the need for facet decomposition, as batch triangulation can produce a sufficiently refined triangulation.

§.§ Triangulation on GPU

In this section, we discuss the GPU triangulation algorithm in detail. Contemporary GPUs offer greater parallel processing power compared to CPUs. This makes GPUs particularly well-suited for manifold triangulation tasks, which have a lot of parallelizable components.

On the other hand, GPUs have specialized architecture and memory hierarchy compared to CPUs. For GPUs to perform optimally, we need to consider these characteristics when designing our algorithm.

First, GPU threads are SIMD (single-instruction multiple-data). It works best when all threads perform the same instructions on different pieces of data with as less diverging branches as possible. To take advantage of this architecture, it is best to run a large number of threads at one time that each performs simple tasks so that all GPU cores are fully utilized.
Secondly, GPUs usually have very limited shared memory resources between threads. This requires us to carefully manage memory to ensure that the memory consumption remains within limits while all threads still have the necessary resources to execute the tasks. This is especially important for the triangulation step since some of the intermediate steps in triangulation require a large amount of memory. We discuss this further in <ref>.

Our GPU triangulation algorithm is based on the manifold tracing algorithm with Coxeter triangulation <cit.>.
The manifold tracing algorithm produces a piece-wise linear approximation of a $m$-dimensional smooth manifold in $\Re^n$. The inputs to the manifold tracing algorithm are the
manifold, in our case the learned manifold as described in <ref>, and a set of points on the manifold.
These points are the seeds for constructing the triangulation, noted by $\Qseeds$. We obtain $\Qseeds$ by sampling points on the manifold, which involves solving a nonlinear optimization program that minimizes the absolute value of the manifold function with a given configuration.
The output of the manifold tracing algorithm is a set of $k$-dimensional simplices that intersect the manifold, where $k=n-m$ is called the codimension. In our case, the learned manifold is always
($n$-$1$)-dimensional for $\Re^n$ configuration space. This means the
codimension is always $1$ and the output simplices are always
$1$-simplices, i.e., line segments.

The algorithm starts with a Coxeter triangulation of the entire $\Re^n$ space ($\Tri$ in the following).

First, the algorithm locates the
$n$-simplices containing $\Qseeds$ by querying the permutahedral
representation of $\Tri$.  Then, the algorithm saves all $k$-simplices that are
in the located $n$-simplices and intersect the manifold.
This process requires face querying using permutahedral representation.

Starting from these $k$-simplices, the algorithm runs
breadth-first search on $\Tri$ by visiting neighboring $k$-simplices
of the saved $k$-simplices and saving all neighbors that intersect the
manifold.  A $k$-simplex is considered a neighbor of another
$k$-simplex if they share the same ($k$+$1$)-simplices. Finding neighboring $k$-simplex requires coface and face querying.
The algorithm terminates when graph traversal ends, and outputs the $k$-simplices and their intersection points with the manifold. A complete
description is
in <cit.>.
$\Re^n$ triangulation size is adjustable with a parameter $\lambda_T$,
which also determines the final manifold triangulation size. Smaller
triangles produce intersection points that are closer to each other, ,
a finer manifold triangulation.

To make this algorithm run on GPU, the first step is to perform the same types of queries for vertices, faces, cofaces, and locating points.
On CPUs, these queries are the same functions that work for any dimension, which requires dynamic memory allocations.
On GPUs, we want to avoid dynamic memory management since it is expansive, can lead to fragmentation, and requires changes to the manageable memory size limit <cit.>.
Since our co-dimension is always $1$, we only need limited types of queries and simplices, which means we can design fixed-size versions of these queries and allocate fixed-size shared memory for the computation.
The types of queries we need are, 1) locating $n$-simplices for points; 2) querying edges ($1$-simplex faces) of $n$-simplices; 3) querying $2$-simplex cofaces of $1$-simplices; 4) querying $1$-simplex faces of $2$-simplices; 5) querying vertices of simplices and calculating their coordinates in $\Re^n$. The types of simplices we need are, 1) $n$-simplex; 2) $1$-simplex; 3) $2$-simplex.
The fixed dimensionality of a given $n$ makes it possible to perform these queries on GPU without dynamic memory allocation.

[node_style/.style=draw, rectangle,
data_node/.style=node_style, fill=orange!50, rounded rectangle,
kernel_node/.style=node_style, fill=blue!40, rounded rectangle,
arrow_style/.style=thick, -Stealth]
[node_style,fill=blue!10, dashed, minimum width = 8.8cm, minimum height=5.2cm] (le) at (-0.1cm, -0.5cm) ;
[above left =-0.8cm and -2.2cm of le]Locate Edges;

[above=-0.2cm of le] (marker) ;
[trapezium, trapezium angle=60, minimum width=45mm, draw, thick, above=-1.29cm of marker] Parallelized for each seed;
[data_node, above=-0.8cm of marker, minimum width=4.5cm, ] (ns)Malloc: $n$-simplices;
above =-1.83cm of marker, minimum width=5cm] (fn) Kernel: find all $n$-simplices;

[above=-2.3cm of le] (marker1) ;
[trapezium, trapezium angle=30, minimum width=55mm, draw, thick, above=-1.30cm of marker1] Parallelized for each $n$-simplex;
[data_node, above=-0.8cm of marker1, minimum width=5.5cm] (se)Malloc: $n$-simplices' edges;
above =-1.83cm of marker1, minimum width=5cm] (ie) Kernel: find all interesting $n$-simplices's edges;
above =-2.9cm of marker1, minimum width=5cm] (he) Kernel: hash all edges;
[single arrow, draw=black, fill=yellow!50,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=5mm, above=0.28cm of he, rotate=-90] (cpu2gpu) ;
[single arrow, draw=black, fill=yellow!50,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=5mm, above=0.28cm of se, rotate=-90] (cpu2gpu) ;

The steps for locating edges from seed points.

With these GPU versions of querying functions, we can perform the manifold tracing algorithm. We discuss the algorithm in two steps. In the first step, we locate from $\Qseeds$ the edges ($1$-simplices) that intersect the manifold. This step has three GPU kernels.
In the first kernel, we parallelize for each point in $\Qseeds$ to locate its $n$-simplex.
We pre-allocate memory for the $n$-simplices since each seed point is contained in one and only one $n$-simplex.
In the second kernel, we parallelize for each $n$-simplex, query its edges, and save the edges that intersect with the manifold. We pre-allocate memory for all edges. A $n$-simplex has $n(n-1)/2$ edges.
An edge with vertices $v_1$ and $v_2$ intersects a manifold if $\infproof(v_1) \infproof(v_2) < 0$. Lastly, we save the edges to a hashset to make sure there are no duplicates. An overview of these steps is shown in <ref> on the left.

In the second step, we perform graph traversal starting with the edges we saved in the first step. Breadth-first search graph traversal on GPU has been studied before <cit.>.
A common approach is to expand the current frontiers to find new nodes, remove any duplicates, and add the remaining new nodes as the next level's frontier. We take a similar approach.

To fully utilize the cores and create less thread divergence, we design the algorithm to perform one task in one kernel.

In each iteration, we start by parallelizing for each frontier edge and query their cofaces.
We can calculate the maximum number of cofaces from the permutahedral representation's coface querying process and the fact that our co-dimension is always $1$.
In $\Re^n$, an edge with partition $\{p_1, p_2\}$ has $(|osp(p+1)| + |osp(p_2)|)$ $2$-simplex cofaces, where $|op(p_i)|$ is the number of ordered two set partitions for $p_i$, which results naturally from the coface querying process of permutahedral representation.

Next, we parallelize for each $2$-simplex coface and save edges of the cofaces if the edges intersect with the manifold and have not been visited before. We can pre-allocate memory space for the cofaces' edges from the following. Each $2$-simplex coface has three edges, and two and only two edges in a $2$-simplex intersect with the manifold assuming the manifold locally does not pass through a single edge twice. One of the two intersecting edges must have been visited before, which is the edge that we query to find the coface previously.
This means the total number of new edges equals the number of cofaces.
Lastly, we hash the new edges to remove any duplication and add the hashed edges as the next level's frontier. An overview of this step is shown in <ref> on the right.

[node_style/.style=draw, rectangle,
data_node/.style=node_style, fill=orange!50, rounded rectangle,
kernel_node/.style=node_style, fill=blue!40, rounded rectangle,
arrow_style/.style=thick, -Stealth]
[node_style,fill=blue!10, dashed, minimum width = 8.8cm, minimum height=5.2cm] (le) at (-0.1cm, -0.5cm) ;
[above left =-0.8cm and -2.2cm of le]Search Edges;

[above=-0.2cm of le] (marker) ;
[trapezium, trapezium angle=60, minimum width=45mm, draw, thick, above=-1.35cm of marker] Parallelized for each edge;
[data_node, above=-0.8cm of marker, minimum width=4.5cm, ] (ns)Malloc: $2$-simplex cofaces;
above =-1.77cm of marker, minimum width=5.5cm] (fn) Kernel: find all cofaces;

[above=-2.25cm of le] (marker1) ;
[trapezium, trapezium angle=50, minimum width=55mm, draw, thick, above=-1.30cm of marker1] Parallelized for each coface;
[data_node, above=-0.8cm of marker1, minimum width=5.5cm] (se)Malloc: $2$-simplex cofaces' edges;
above =-1.83cm of marker1, minimum width=5cm] (ie) Kernel: find all interesting cofaces' edges;
above =-2.9cm of marker1, minimum width=5cm] (he) Kernel: hash all edges;
[single arrow, draw=black, fill=yellow!50,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=5mm, above=0.30cm of he, rotate=-90] (cpu2gpu) ;
[single arrow, draw=black, fill=yellow!50,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=5mm, above=0.31cm of se, rotate=-90] (cpu2gpu) ;
[arrow_style](he.east) to[bend right=80]  (ns.east);

The steps for searching edges in iteration.

To summarize, because our co-dimension is always $1$, we can eliminate dynamic memory management in our GPU triangulation algorithm design. All memory allocations for new data structures have fixed maximum size. Also, we design the kernels such that all threads run one task at one time, which eliminates as many diverging branches as possible.

[line join = round, line cap = round]
[label=below left:$v_0$] (v0) at (0, 0);
[label=below right:$v_1$] (v1) at (, 0);
[label=] (vd) at (/2, 0);
[label=above right:$v_2$] (v2) at (, );
[label=above right:] (v01) at (/2, 0);
[label=above right:] (v02) at (/2, /2);
[label=above right:] (v12) at (, /2);

[label=above left:$v: [0, 0]$] (s1) at (-0.1cm, 1.4cm);
[label=above left:$p:\{\{0\}, \{1, 2\}\}$] (s1) at (1.1cm, 1cm);

[draw, fill=blue!20!white, line width=1pt, postaction=on each segment=left arrow=black]  (v0) – (v1)–(v2)–cycle;
[dashed] (v01)–(v02);
[dashed] (v12)–(v02);
[dashed] (v12)–(v01);
[thick,red,-, line width=2pt]  (v0) to (vd);

[line join = round, line cap = round]
[label=below:$v_0$] (v0) at (0,0,0*);
[label=below:$v_1$] (v1) at (2,0,0*);
[label=right:$v_2$] (v2) at (2,0,-2*);
[label=left:$v_3$] (v3) at (2,2,-2*);

[label=below:] (v01) at (1,0,0*);
[label=below:] (v02) at (1,0,-1*);
[label=below:] (v03) at (1,1,-1*);
[label=below:] (v12) at (2,0,-1*);
[label=below:] (v13) at (2,1,-1*);
[label=below:] (v23) at (2,1,-2*);
[label=above left:$v: [0, 0, 0]$] (s1) at (1.4cm, 1.6cm);

[label=above left:$p:\{\{0\}, \{1, 2, 3\}\}$] (s1) at (1.4cm, 1.2cm);

[dashed] (v01)–(v02);
[dashed] (v12)–(v02);
[dashed] (v12)–(v01);

[dashed] (v01)–(v13);
[dashed] (v13)–(v03);
[dashed] (v03)–(v01);

[dashed] (v23)–(v12);
[dashed] (v12)–(v13);
[dashed] (v13)–(v23);

[dashed] (v03)–(v23);
[dashed] (v02)–(v03);
[dashed] (v23)–(v02);

[-, fill=red!30, opacity=.5] (v0)–(v1)–(v2)–cycle;
[-, fill=blue!30, opacity=.5] (v0) –(v1)–(v3)–cycle;
[-, fill=purple!30, opacity=.5] (v1)–(v2)–(v3)–cycle;
[draw, line width=1pt, postaction=on each segment=left arrow=black]  (v0) – (v1)–(v2)–(v3)–cycle;
[thick,red,-, line width=2pt]  (v0) to (v01);

First edge (marked in red) and its permutahedral presentation in the new triangulation, for subdivision of a 2-simplex and a 3-simplex, with $k=2$.

§.§ Batch Triangulation

[node_style/.style=draw, rectangle,
data_node/.style=node_style, fill=orange!50, rounded rectangle,
kernel_node/.style=node_style, fill=blue!40, rounded rectangle,
arrow_style/.style=thick, -Stealth]
[node_style,fill=blue!10, dashed, minimum width = 8.8cm, minimum height=8.0cm] (le) at (-0.1cm, -0.5cm) ;
[above left =-0.8cm and -5.5cm of le]In each batch of $n$-simplices:;

[above=-0.9cm of le] (marker) ;
[trapezium, trapezium angle=20, minimum width=45mm, draw, thick, above=-1.33cm of marker] Parallelized for each edge;
[data_node, above=-0.8cm of marker, minimum width=4.5cm, ] (ns)Malloc: sub-division edges;
above =-1.83cm of marker, minimum width=5cm] (fn) Kernel: compute sub-division edges for each n-simplex;

[above=-3.0cm of le] (marker1) ;
[trapezium, trapezium angle=20, minimum width=55mm, draw, thick, above=-1.30cm of marker1] Parallelized for each edge;
[data_node, above=-0.8cm of marker1, minimum width=5.5cm] (se)Malloc: edge intersection points;
above =-1.83cm of marker1, minimum width=5cm] (ie) Kernel: compute sub-division edges’ intersection points;
above =-2.9cm of marker1, minimum width=5cm] (he) Kernel: hash all edges;
above =-2.9cm of marker1, minimum width=5cm] (he) Kernels: hash intersection points;
above =-3.99cm of marker1, minimum width=5cm] (cc) Kernels: collision checking;
[draw, rectangle, fill=black!20,
above =-4.99cm of marker1, minimum width=5cm] (tra) Kernels: Transfer $\CFree$ intersection points to CPU;
[single arrow, draw=black, fill=yellow!50,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=5mm, above=0.28cm of he, rotate=-90] (cpu2gpu) ;
[single arrow, draw=black, fill=yellow!50,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=5mm, above=0.28cm of cc, rotate=-90] (cpu2gpu) ;
[single arrow, draw=black, fill=yellow!50,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=5mm, above=0.28cm of se, rotate=-90] (cpu2gpu) ;
[single arrow, draw=black, fill=yellow!50,
minimum width = 8pt, single arrow head extend=3pt,
minimum height=5mm, above=0.28cm of tra, rotate=-90] (cpu2gpu) ;

The steps in each batch triangulation of $n$-simplices.

In the manifold tracing algorithm, with a given manifold in $\Re^n$, the number of intersecting edges ($1$-simplices) is related to the resolution of the $\Re^n$ Coxeter triangulation and the dimension $n$. If we use a smaller resolution, then the algorithm will produce more intersecting edges. If we run in high dimensions, the algorithm also produces more intersecting edges. Because of this, the algorithm sometimes requires more memory to store the data structures (the edges and cofaces in particular) than what the GPU can offer. We resolve this issue with limited memory resources through batch triangulation.
While we cannot change the dimensionality of the problem, we can change the resolution of the $\Re^n$ triangulation, which would produce a coarser manifold triangulation. Then, we perform a finer sub-triangulation on top of the existing triangulation to get to the refinement we need.

The first step is to find the $n$-simplices that intersect with the manifold from the intersection edges of the triangulation algorithm in <ref>.
We begin by querying the $n$-simplex cofaces of the intersection edges.
We can compute the maximum number of $n$-simplex cofaces using the permutahedral presentation.
In $\Re^n$, an edge with partition $\{p_1, p_2\}$ has $|p1|!|p2|!$ $n$-simplex cofaces, where $|p_i|!$ is the factorial of $p_i$'s size.
Then, we hash the $n$-simplices to remove any duplicates.
The $n$-simplices that intersect with the manifold decompose the manifold into coarse pieces. Next, we perform finer triangulation within each piece.

The core idea is to decompose each $n$-simplex with symmetric subdivision <cit.>, find all sub-simplices' edges, and then iterate through all the edges to find the ones intersecting with the manifold. To make sure the resulting sub-simplices' edges inside a $n$-simple are the edges of a Coxeter triangulation with finer resolution, we define and find all sub-simplices' edges through permutahedral presentation inside a $n$-simplex.

Assume we want the resolution of the triangulation to be $\lambda_T$, and the coarse triangulation uses a resolution of $\lambda_T * k$, where $k$ is the decompose resolution we need and we decompose each edge of the $n$-simplex into $k$ pieces. In $\Re^n$, given a $n$-simplex in a coarse triangulation, with vertex $[v_0, v_1, ..., v_{n-1}]$ and partition $\{\{p_1\}, \{p_2\} ..., \{p_{n+1}\}\}$, $p_1, p_2, ..., p_{n+1} \in \{1, 2, ..., n+1\}$, we start a new “local” triangulation in the simplex. In the local triangulation, the vertex $[v_0, v_1, ..., v_{n-1}]$ becomes $[0, 0, ...,0]$, and we can define our first edge in the new triangulation as
vertex: $[0, 0, ...,0]$, partition $\{\{0\}, \{1, 2, ..., n\}\}$, which corresponds to the first decomposed line segment on the root system cycle's first edge based on the partition of $n$-simplex. This local edge's representation is the same within all $n$-simplices. <ref> shows the subdivision and the first edge in a $2$-simplex and a $3$-simplex, with $k=2$. From this first edge, we can use the same queries we used in the manifold tracing algorithm to find all sub-simplices' edges by first querying the cofaces and then querying the edges.

We also need to ensure the edges we find are in the $n$-simplex. For this, we check that the two vertices of the edge are in the $n$-simplex. Given a vertex $v' = \{v'_0, v'_1, ..., v'_{n-1}\}$ in the local triangulation, The value of $v'_i$ denotes the proportion of the edge $(v_{i+1}, v_i)$ occupied by the vertex.  We can compute the barycentric coordinates of the vertex in the $n$-simplex from the coordinate of the vertex in the original triangulation frame,

\begin{equation}
\begin{aligned}
v' &= \Vec{v}_0 + v'_0/k(\Vec{v}_1 - \Vec{v}_0) + v'_1/k(\Vec{v}_2 - \Vec{v}_1) + ... \\
&+ v'_{n-1}/k(\Vec{v}_{n} - \Vec{v}_{n-1})\\
&=  (1 - v'_0/k) \Vec{v}_0 + (v'_0/k - v'_1/k) \Vec{v}_1
+ (v'_1/k - v'_2/k) \Vec{v}_2 \\
&+ ... + (v'_{n-2}/k - v'_{n-1}/k) \Vec{v}_{n-1} + (v'_{n-1}/k)\Vec{v}_{n},
\end{aligned}
\label{eq:bc}
\end{equation}

which gives the barycentric coordinates $(1 - v'_0/k, v'_0/k - v'_1/k, ..., v'_{n-2} - v'_{n-1}, v'_{n-1}/k)$.

A point is inside a simplex if its barycentric coordinates are all no less than $0$, which gives us,

\begin{equation}
\left\{\begin{aligned}
&1 - v'_0/k > 0,\\
&v'_0/k - v'_1/k > 0, \\
&v'_{n-2}/k - v'_{n-1}/k > 0, \\
&v'_{n-1}/k > 0\\
\end{aligned}\right. \Rightarrow
\left\{\begin{aligned}
&k - v'_0 > 0,\\
&v'_0 - v'_1 > 0, \\
&v'_{n-2} - v'_{n-1} > 0, \\
&v'_{n-1} > 0\\
\end{aligned}\right.
\label{eq:local}
\end{equation}

We also multiply both sides by $k$ to remove floating-point computation. With <ref>, we can easily check whether a vertex in the local triangulation is in the $n$-simplex or not.

The resulting cofaces and edges' permutahedral presentation within a $n$-simplex are the same across all $n$-simplice, so we only need to compute this once and we can use it to sub-divide all the $n$-simplices we computed from the triangulation step. Also, by using permutahedral presentation in the local triangulation, the resulting sub-simplices' edges are the same as the simplices' edges in a triangulation with $\lambda_T$, and we have reached the original triangulation resolution.

With this sub-division, we perform triangulation by batch. We estimate the overall memory usage for the sub-division of each $n$-simplex, and then we compute how many $n$-simplices the current remaining memory of the GPU could work with at one time to put them into batches. Within each batch, we use the sub-division to get the edges' vertices, then compute the intersection points of the edges with the manifold. These kernels are parallelized on each edge. Then, we hash the intersection points to remove any duplicates and check for collision with the remaining intersection points. If there are intersection points in $\CFree$, we transfer those points back to the CPU side to retrain the manifold. We free all GPU memory for the computation related to the batch triangulation and collision checking at the end of each batch, so we can take another batch of $n$-simplices. <ref>
shows these steps in each batch.

§.§ Collision checking on GPU

In <ref>, we observe that the collision checking is performed by batch on a large set of configurations (the intersection points). This is ideal for collision checking on GPU, where it takes a large number of configurations at one time and parallelizes collision checking of each configuration in each thread. We implemented a forward kinematics (FK) kernel and a collision-checking kernel for batch collision checking on GPU.

The collision-checking kernel is based on primary shapes, more specifically, spheres vs $\{$cylinders, boxes, spheres$\}$. With a new robot and a new scene, we need to configure the robot's geometries into enclosing spheres and represent the world geometries using cylinders, boxes, and/or spheres.
Our geometry checking is based on exact shapes instead of bounding boxes <cit.>, see Appendix <ref> for detail.
The threads are first parallelized for each sphere forming the robot, then for each configuration. When there are too many points to check such that there is not enough memory to hold all the FK and intermediate collision checking results, we perform collision checking by batch.

§.§ Analysis

Our computational design minimizes data transfer between the CPU and GPU. For triangulation, we complete the triangulation part entirely on GPU and only require the data for the manifold we are triangulating to be transferred to GPU. For batch collision checking after triangulation, we only need geometry information about the scene and the robot. The time required for data transfer would not increase with dimensionality. In practice, memory usage is less than $5\%$ of total GPU time.

We emphasize that most of the kernels we use for triangulation and collision checking have very high GPU occupancy. The kernels for finding $n$-simplice, finding new edges of $n$-simplices, finding cofaces of edges, and hashing new edges have $100\%$ theoretical occupancy. Finding new edges of cofaces does not have $100\%$ theoretical occupancy because we also check for whether the edge intersects with the manifold. Calculating intersection points of edges also does not have $100\%$ theoretical occupancy because not all threads have the same number of iterations for the computation.
Because of the high GPU occupancy, the algorithm demonstrates strong scalability with increased GPU cores and memories. With more powerful GPUs, infeasibility proofs for 7-DoF robots can be completed within a reasonable time.

[width=0.3, clip=true, trim = 184mm 110mm 182mm 90mm]figures/packbot.png
0.05 START
0.05 GOAL

(a) PackBot Scene

[width=0.3, clip=true, trim = 54mm 57mm 72mm 10mm]figures/universal.png
0.06 START
0.05 GOAL

b) Universal Robot Scene

[width=0.3, clip=true, trim = 24mm 20mm 42mm 12mm]figures/schunk.png
0.05 GOAL
0.05 START

c) Schunk Robot Scene

Experiment Scenes. The packbot scene is 5-DoF. The universal robot scene run in 5-D0F and 6-DoF. The Schunk scene is 6-DoF. We experiment with 4 scenes in total.

§ EXPERIMENT

In this section, we validate our algorithm through experiments.
We run two 5-DoF scenes, similar to the configuration outlined in our prior publication <cit.>, to evaluate the speedup achieved through GPU implementation. We also run two 6-DoF scenes to show the scalability of our algorithm.

We run our
experiment on a desktop system with an NVIDIA GeForce RTX 4070 GPU with 12G memory and an Intel i9-13900K CPU with 48 cores.  We use
PRM <cit.> in OMPL <cit.> as the sampling-based motion planner that runs in parallel with our infeasibility proof construction, and get samples from the planner to train the manifold and sample the manifold. We solve the nonlinear optimization problems using
sequential least-squares quadratic programming
(SLSQP) <cit.> in
NLopt <cit.>.  We adopt the Coxeter triangulation module in
GUDHI <cit.>, and implemented our own GPU kernels for permutahedral representation with necessary queries for triangulation. Our triangulation, batch triangulation, and collision checking are all based on CUDA <cit.>.  We train the RBF-kernel SVM
using ThunderSVM <cit.>, which supports
GPU-accelerated SVM training.  We model robot kinematics using
Amino <cit.>, which is interpreted on the CPU, and then geometry information is transferred to the GPU.

§.§ 5-DoF experiments

We have two 5-DoF experiment scenes, using a similar setup as described in our previous paper <cit.>.  We configure the robot with inscribing spheres for fast collision checking on GPU. The scenes and the start and goal configurations are shown in <ref>. The first scene is with Packbot <cit.>. The second experiment uses the Universal robot <cit.> with the last joint fixed to make it 5-DoF.

§.§ 6-DoF experiments

We have two 6-Dof experiment scenes, as shown in <ref>. The first scene uses the same universal robot scene with all 6 joints. The second scene uses a Schunk LWA4D manipulator, with the third joint fixed to make it 6-DoF. The scene is shown in <ref>. The goal in the scene is to reach inside a shelf from a location of the arm outside of the shelf.

Total (s)     Tri (s)     Check (s)

Packbot     22.16 $\pm$14.88     5.56 $\pm$6.03     1.62 $\pm$2.13

Universal-5     8.42 $\pm$2.30     0.40 $\pm$0.17     0.32 $\pm$0.19

Universal-6     58.62 $\pm$29.66     2.86 $\pm$1.71     11.80 $\pm$6.29

Schunk    58.12 $\pm$37.75     12.65 $\pm$7.97     34.49 $\pm$28.33

Runtime results for 5-DOF and 6-DOF manipulators, mean (s) $\pm$STD, averaged over 30 trials. “Tri" is for triangulation, including batch triangulation. “Check" is for collision checking.

We summarize the experimental results in <ref>. For the two 5-DoF scenes, compared with previous results, we achieve more than two orders of magnitude speed up for collision checking in both scenes. The triangulation time in the 5-DoF universal robot scene is also two orders of magnitude faster. The triangulation in the Packbot scene takes slightly longer because the “size” of the manifold is larger with a wider goal region in the configuration space.
The two 6-DoF scenes both take less than 1 minute on average, triangulation takes several seconds to tens of seconds, and collision checking takes tens of seconds.

§.§ Discussion

Comparing the 5-DOF Packbot scene and the 6-DoF Universal robot scene, we can see that the triangulation for the Packbot takes longer than the triangulation for the 6-DoF Universal robot. This is caused by the size of the manifold. A larger manifold takes much longer to triangulate than a smaller manifold in the same dimension. The reason for this is that the triangulation algorithm runtime is sensitive to the output size <cit.> since we need to trace the entire manifold to find the triangulation. This also becomes more noticeable in higher dimensions, as the manifold also becomes higher dimension.

We also noticed some delays on the planner side. The results for the Packbot, and the Universal robot in 5-DoF and 6-DoF show a difference between the sum of the triangulation and checking time and the total planning time. The primary reason for this difference is that after checking, we provide all the $\CFree$ manifold points back to the planner side, and the planner needs to process these $\CFree$ points and add them to the planning graph. This step helps with the convergence of the manifold, which is the basis of a successful triangulation and checking. If the triangulation and checking on GPU find a larger number of points, then the planner would take a longer time to process those points, thus causing the delay.

As we mentioned in <ref>, many kernels in our algorithm can achieve very high theoretical occupancy and achieved occupancy. In practice, many factors can effect GPU occupancy, but we still achieve very high measured GPU occupancy.
Finding new edges of n-
simplices achieves an occupancy of around 80%;
finding cofaces of edges achieves an occupancy of around 88%;
finding new edges of cofaces achieves an occupancy of around 80%;
and calculating
intersection points of edges achieves an occupancy of around 53%. Calculating intersection points has lower occupancy because the calculation is based on an iterative algorithm that terminates when a desired accuracy is reached, which could have a lot of branching.

§ FUTURE WORK AND CONCLUSION

§ COLLISION CHECKING

In this appendix, we record the exact collision checking method between sphere and primacy shapes (box, cylinder, sphere) for our batch collision checking. Sphere vs sphere can be easily checked, so we omit this case.

§.§ Sphere vs Box

The box has dimension $[l_x, l_y, l_z]$, and coordinate frame $\{F_b\}$. The origin of this frame is at the geometric center of the box and the axes of the frame align with the three edges of the box.
The sphere is located at $\Vec{c_s}$, with a radius of $r$.
We first transform the sphere into the box's coordinate frame, which gives the center of the sphere at $^b\Vec{c_s}$ in $\{F_b\}$.
Because the box is symmetric for all three axes, we can map the center of the sphere to the first octant by computing the absolute values of x, y, z in $^b\Vec{c_s}$, we note this mapped coordinate with $\{p_{x}, p_{y}, p_{z}\}$. We only need to consider the first octant from now on.

Exact collision checking between sphere and box three steps.
In the first step, we check whether

\begin{equation}
\exists i \in \{x, y, z\}, \quad \mathrm{s.t.} \quad p_i - l_i/2 > r,
\label{eq:sb-bb}
\end{equation}

which means the sphere center is located outside a bounding box region of radius plus the box dimensions, so the sphere does not collide with the box. We have $l_i/2$ since we are only considering the box's part in the first octant at this point.

If <ref> is not true, then we check whether the sphere center is in the “edge” region or the “vertex” region of the box.
For a sphere center in the edge regions, we have

\begin{equation}
\begin{aligned}
&(p_i < l_i/2) \land (p_j > l_j/2) \land (p_k > l_k/2),\\ &i,j,k \in \{x, y, z\}, i \neq j \neq k.
\end{aligned}
\label{eq:edge-region}
\end{equation}

The edge regions are shown as the yellow regions in <ref>.
For sphere centers in edges regions following <ref>, if

\begin{equation}
(p_j - l_j/2)^2 + (p_k - l_k/2)^2 > r^2,
\end{equation}

which means the distance of the sphere center to the edge is larger than the radius, then the sphere does not collide with the box.

For a sphere center in the vertex region, we have

\begin{equation}
p_i > l_i/2, \forall i \in \{x, y, z\}.
\label{eq:vertex-region}
\end{equation}

The vertex region is shown as the red region in <ref>.
For sphere centers in the vertex region, if

\begin{equation}
\sum_{i \in \{x, y, z\}}(p_i > l_i/2)^2 > r^2,
\end{equation}

which means the distance of the sphere center to the vertex is larger than the radius, then the sphere does not collide with the box.
If none of the above-mentioned cases are true, the sphere collides with the box.

[->, thick] (0,0,0) – (+ ,0,0) node[right] $x$;
[->, thick] (0,0,0) – (0, 0, + 2*) node[below] $z$;
[->, thick] (0,0,0) – (0, + , 0) node[above] $y$;

[-,fill=blue!30] (0,0,) – ++(,0,0) – ++(0,,0) – ++(-,0,0) – cycle;
[-,fill=blue!30] (,0,) – ++(0,0,-) – ++(0,,0) – ++(0,0,) – cycle;
[-,fill=blue!30] (,,) – ++(-,0,0) – ++(0,0,-) – ++(,0,0) – cycle;
[dashed, fill=yellow!30, opacity=.5] (,,) – ++(0,0,-) – ++(0,,0) – ++(0,0,2*) – ++(0,-2*,0) –++(0, 0, -) – cycle;

[dashed, fill=yellow!30, opacity=.5] (0,,) – ++(0,0,) – ++(* 2,0,0) – ++(0,0,-2*) – ++(-,0,0) –++(0, 0, ) – cycle;

[dashed, fill=yellow!30, opacity=.5] (0,,) – ++(0,,0) – ++(* 2,0,0) – ++(0,-2*,0) – ++(-,0,0) –++(0, , 0) – cycle;

[yellow!30, opacity=.5] (0,,) – ++(0,,0) – ++(0,0,) –++(0, -, 0) – cycle;

[yellow!30, opacity=.5] (,0,) – ++(,0,0) – ++(0,0,) –++(-, 0, 0) – cycle;

[yellow!30, opacity=.5] (,,0) – ++(,0,0) – ++(0,,0) –++(-, 0, 0) – cycle;

[dashed,fill=red!30, opacity=.5] (,,) – ++(,0,0) – ++(0,,0) – ++(-,0,0) – cycle;
[dashed,fill=red!30, opacity=.5] (,,2*) – ++(0,0,-) – ++(0,,0) – ++(0,0,) – cycle;
[dashed,fill=red!30, opacity=.5] (2*,,2*) – ++(-,0,0) – ++(0,0,-) – ++(,0,0) – cycle;

[dashed] (0, 0, 0)–(0, , 0);
[dashed] (, 0, 0)–(0, 0, 0);
[dashed] (0, 0, )–(0,0,0);
[label=left:$l_y / 2$] (ly) at (0, /2, );
[label=left:$l_z / 2$] (ly) at (0, , /2);
[label=below:$l_x / 2$] (ly) at (/2-0.2, -0.4, /2);
[label=below:$r$] (ly) at (/2*3, , );
[label=right:$r$] (ly) at (, /2*3, );
[label=right:$r$] (ly) at (, , *3/2);

Collision Checking for Sphere vs Box, in the first cotant.

[->, thick] (,̊0,0) – (3,0,0) node[right] $x$;
[->, thick] (0,0,) – (0,0,4) node[below] $z$;
[->, thick] (0,,̊0) – (0,3,0) node[above] $y$;

[fill=blue!30] (0, 0, 0) – (,̊ 0, 0) arc [x radius = ,̊ y radius =,̊ start angle=0, end angle=90] – cycle;
[-] (,̊ 0, 0) arc [x radius = ,̊ y radius =,̊ start angle=0, end angle=90];
[fill=blue!30] (0, 0, 0) –++ (0, ,̊ 0) –++ (0, 0, ) –++ (0, -,̊ 0) – cycle;
[fill=blue!30] (0, 0, 0) –++ (,̊ 0, 0) –++ (0, 0, ) –++ (-,̊ 0, 0) – cycle;
[-,fill=blue!30] (0, 0, ) – (,̊ 0, ) arc [x radius = ,̊ y radius =,̊ start angle=0, end angle=90] –cycle;
[-] (,̊ 0, ) –++ (0, 0, -);
[-] (0, ,̊ ) –++ (0, 0, -);
[dashed] (0, 0, 0) –++ (0, 0, );
[dashed] (0, 0, 0) –++ (,̊ 0, 0);
[dashed] (0, 0, 0) –++ (0, ,̊ 0);
[fill=red!30, opacity=.5] (,̊ 0, ) – (+̊, 0, ) arc [x radius = +̊, y radius =+̊, start angle=0, end angle=90] –++ (0, -, 0) arc [x radius = ,̊ y radius =-,̊ start angle=-90, end angle=0] – cycle;
[fill=red!30, opacity=.5]  (,̊ 0, +) arc [x radius = ,̊ y radius =,̊ start angle=0, end angle=90]  – (0, ,̊ ) arc [x radius = ,̊ y radius =-,̊ start angle=-90, end angle=0] –cycle;
[fill=red!30, opacity=.5] (,̊0,+) arc [start angle=-90,end angle=-4,x radius=2.05,y radius=0.62]– (,̊ 0, ) –cycle;
[dashed] (,̊ 0, ) – (+̊, 0, );
[dashed] (,̊ 0, ) –++ (0, 0, );
[fill=red!30, opacity=.5] (0,+̊,) arc [start angle=90,end angle=183,x radius=0.62,y radius=2]– (0, ,̊ ) –cycle;
[dashed] (0, ,̊ ) –++ (0, , 0);
[dashed] (0, ,̊ ) –++ (0, 0, );
[label=below:$h / 2$] (h) at (0, 0, /2-1);
[label=below:$r_c$] (h) at (/̊2, 0, );
[label=below:$r_s$] (h) at (/2 + ,̊ 0, );

Collision Checking for Sphere vs Cylinder, in the first cotant.

§.§ Sphere vs Cylinder

The cylinder has height $h$, and radius $r_c$, and coordinate frame $\{F_c\}$. The origin of this frame is at the geometric center of the cylinder and the z-axis of the frame aligns with the central axis of the cylinder.
Same as before, we first transform the sphere into the cylinder's coordinate frame, then map the sphere to the first octant, we note this mapped coordinate with $\{p_{x}, p_{y}, p_{z}\}$. We only need to consider the first octant in the following.

Exact collision checking between sphere and cylinder two steps.
In the first step, we check whether

\begin{equation}
p_z - h/2 > r_s \lor \sqrt{p_x^2 + p_y^2} > r_s + r_c
\label{eq:sc-bb}
\end{equation}

which means the sphere center is located outside a padded cylindrical region of radius plus the cylinder dimensions, so the sphere does not collide with the cylinder.

If <ref> is not true, then we check whether the sphere center is in the “ring” region of the cylinder.
For a sphere center in the ring regions, we have

\begin{equation}
(p_z > h/2) \land (\sqrt{p_x^2 + p_y^2} > r_c)
\label{eq:ring-region}
\end{equation}

The ring region is shown as the red region in <ref>.
For sphere centers in ring region following <ref>, if

\begin{equation}
(\sqrt{(p_x^2 + p_y^2)} - r_c)^2 + (p_z - h/2)^2 > r_s^2,
\end{equation}

which means the distance of the sphere center to the edge of the cylinder is larger than the radius of the sphere, the sphere does not collide with the cylinder.
If none of the above-mentioned cases are true, the sphere collides with the cylinder.