The key idea of our approach is, there can be many optimal charging paths for
a request with the same minimum travel time. Hence, The seeks to find such an
OCP(r) for the current request $r$ in the stream, which excludes the CSs
and/or the timeslots that are expected to be in the OCP of the future
requests, as much as possible. In the following, we present our solution with
the details of the steps.

##  0.1 Pre-processing

In this section, we present the pre-processing steps that we propose to
improve the efficiency of our NP-hard problem for stream of EV requests.

Reduction of the search space to charging network only Given the fixed
locations of CSs and the expectation for users to choose the fastest path
between CSs during long trips, we first reduce the routing network to a graph
with CSs only. This strategic pre-processing step eliminates redundant
computations between fixed locations, enhancing overall solution efficiency.
The resultant CS-only graph is constructed with vertices representing CSs and
edges connecting CS pairs within a specified threshold, i.e., maximum range of
EVs. The edges maintain their weight $w(e)$, denoting travel time of an edge
$e$ between the pair of CSs, and resource changes during traversal are
captured by $u(e)$. Self-loops $L$ at CSs remain unchanged. Note that the
values associated with an edge in this graph can easily be updated in real
time to incorporate any changes in travel times and energy consumption.
Throughout this paper, we refer to this simplified graph, focused exclusively
on CSs without road intersections, as the routing network.

Landmarks to substitute source and destination When a request $r$ arrives, one
approach is to add its origin and destination as vertices in the graph
[schoenberg2022reducing], create the necessary edges, and compute their weight
$w(e)$ and resource $u(e)$ values. However, to further reduce runtime
computations in this NP-hard problem, we introduce ‘landmark’ vertices.
Landmarks are selected from the routing graph and are connected to CSs within
the maximum range of EVs. The weight $w(e)$ and the resource $u(e)$ of each
such edge $e$ are calculated and included in the routing network.
Subsequently, when a request $r$ is received, we replace its origin and
destination locations with the nearest landmark vertices. This substitution
renders other landmarks irrelevant for the OCP calculation, allowing for the
inclusion of a larger number of landmarks in the routing network without
affecting subsequent computations.

Future request predictor As we mentioned, given a stream of requests, our
objective is to find an optimal charging path for each request $r_{i}$, while
also minimizing the total travel time for the other requests in the stream.
While finding the OCP for $r_{i}$, we are unaware of the upcoming requests
$\\{\forall r_{j}|t_{r_{j}}>t_{r_{i}}\\}$ due to the streaming nature of
requests. To tackle the , we propose a solution involving a request predictor,
treated as a black box for finding a proactive optimal solution.

Our paper focuses on utilizing future demand information, rather than
predicting it directly, to plan optimal charging paths. For simplicity, we
assume that upon each request arrival, a set $R^{\prime}$ of future $n$
requests is provided, each containing the relevent information similar to any
EV routing request. It is also feasible to adapt the existing spatial-temporal
prediction method [yao2018deep] for predicting such future requests.

Importantly, our approach maintains the optimality of the charging path
solution for the current request regardless of the accuracy of the future
request predictor. This means that even if all $n$ future requests are
predicted incorrectly, the solution for the current request remains guaranteed
to be optimal.

##  0.2 Influence factor

In the following, we first propose some key concepts of the influence of one
charging path on another, which will be later used to present the steps of our
approach in details.

Correlation of two paths In a GTDS $G$, two optimal charging paths $p$ and
$p’$ of two different EVs exhibit correlation iff there exists a time $t$
where both paths use the same self-loop edge in $G$ (i.e., a specific timeslot
at a particular CS is part of the optimal charging paths of both EVs). If
function $co(p,p’)$ defines the correlation between $p$ and $p’$, then it
results in 1 if there is a correlation between $p$ and $p’$, otherwise 0.

######  Example 0.1.

Consider the following charging paths (Superscripts denote timeslots, and
subscripts denote CS or landmark):
$p_{1}=\\{l_{1}^{0},c_{1}^{10},c_{1}^{11},c_{1}^{12},c_{1}^{13},c_{1}^{14},l_{2}^{26}\\}$
, $p_{2}=\\{l_{2}^{1},c_{2}^{10},c_{2}^{11}\\\
,c_{2}^{12},c_{2}^{13},l_{1}^{26}\\}$,
$p_{3}=\\{l_{2}^{1},c_{1}^{13},c_{1}^{14},c_{1}^{15},c_{1}^{16},l_{1}^{26}\\}$,
$p_{4}=\\{l_{3}^{4},c_{1}^{15},\\\
c_{1}^{16},c_{1}^{17},c_{1}^{18},l_{1}^{28}\\}$, where $p_{1}\in OCP(r_{1})$,
$p_{2},p_{3}\in OCP(r_{2})$, and $p_{4}\in OCP(r_{3})$. No correlation exists
between $p_{1}$ and $p_{2}$ since they are charged at different CSs. The same
holds true for $p_{1}$ and $p_{4}$ as their charging times do not overlap,
despite using the same CS. Conversely, $p_{1}$ and $p_{3}$ exhibit correlation
because these paths consist of the same CS ($c_{1}$) at the same timeslots
($c_{1}^{13},c_{1}^{14}$). So, the values of $co(p_{1},p_{2})$,
$co(p_{1},p_{3})$, and $co(p_{1},p_{4})$ are 0, 1, and 0, respectively.

The correlation of a path $p$ indicates which paths for the future requests
become unavailable if $p$ is chosen for the current request. The
unavailability of a specific path of the upcoming requests can result in an
increase in their travel time. Therefore, it is essential to establish a
factor that quantifies the influence of a path on future requests.

Influence factor of a charging path on a set of requests The influence of
charging path $p\in OCP(r)$ on a set of requests $R’=\\{r’\in
R|t_{r’}>t_{r}\\}$ can be characterized from two perspectives: i) Direct
influence: Since our goal is to minimize travel times for all vehicles, we
denote the direct impact of a path $p$ on a set of requests $R’$ as the
increased travel time that future requests $R’$ will experience as a result of
their correlation with $p$. ii) Indirect influence: Although the correlation
with path $p$ does not always result in extended travel times for
$R^{\prime}$, due to the presence of multiple optimal charging paths with the
same minimum travel time, it may lead to a decrease in the number of available
optimal paths for each request in $R’$. The likelihood of experiencing longer
travel times for future requests is higher when there are fewer optimal paths
with the minimum travel time available. So we define indirect influence of
path $p$ on $R’$ as the number of optimal paths for $R^{\prime}$ which has a
correlation with path $p$.

Proactive-optimal charging path Given a set of optimal charging path $OCP(r)$
and a predicted upcoming requests set $R^{\prime}$, the charging path
$p_{po}\in OCP(r)$ is referred to as proactive-optimal charging path when
$p_{op}$ exhibits the lowest direct influence factor. If there are multiple
paths with the same direct influence, the path with the lowest indirect
influence factor among them is considered as $p_{op}$.

Our proposed solution to find a proactive optimal charging path for each $r\in
R$ contains two components: an algorithm to find all $OCP(r)$ of the current
request $r$, and calculating influence factor for each charging path in
$OCP(r)$. We propose an efficient two-phase algorithm to find all $OCP(r)$ of
a request $r$ in Section 0.3, and an effective refinement-based approach to
calculate influence factor in Section 0.4.

##  0.3 Finding OCP of a request

As mentioned in Section IV, the problem of finding OCP for one request is an
NP-hard problem. Hence, we propose an efficient solution to calculate the
travel time of paths that include charging and waiting time using TRT
(presented in Section IV), and a routing table (explained later). In the
initial phase, we proceed forward from the source point and compute the
various potential departure times for each CS based on a specific SoC.
Subsequently, these values are stored in the routing table and the process
persists until the destination is reached. Upon arrival at the destination and
obtaining an upper bound for the length of a feasible route, we commence our
second phase, which is reverse traversal from the destination to the source.
Employing the information stored in the routing table, various alternative
paths are constructed while considering the latest permissible departure time
from each CS. Before explaining the algorithm, we define ‘Routing table’.

Routing table The routing table serves as a straightforward mechanism for
storing arrival and leaving information for each CS during the forward phase.
Each row of the table stores the following information: the arrived node,
arrival time and SoC, the ancestor node (i.e., immediate predecessor to the
arrived node in the current path), charging time, departure SoC, and departure
time from the CS. Now we present our algorithm.

###  0.3.1 Forward Pass

Each EV possesses SoC and requires recharging, which can take a different
amount of time considering the charging rate and status of a CS (i.e.,
reserved or available) at different times. Thus, arriving earlier may not
necessarily lead to departing from the CS earlier. Moreover, the path with the
shortest travel time can consist of multiple partial recharging. So, we
propose our efficient techniques that utilize the TRT and routing table to
find the OCP.

Leaving Charging Bucket In our algorithm, each vehicle is capable of departing
from any CS with a SoC that corresponds to a predefined value referred to as a
Leaving Charging Bucket ($LCB$). For example, $LCB=\\{50,100\\}$ means each EV
can leave the CS with SoC equal to either 50 or 100 percent.

Figure 1: GTDS of Example 4. $l_{1}$ and $l_{2}$ are the source and destination, $c_{1}$ and $c_{2}$ are CSs with effective charging rate $2$ and $1$ per timeslot, respectively.  Table 1: Routing table of Example 4 Rows | V | anc | $t^{a}$ | $SoC^{anc}$ | $SoC^{a}$ | $SoC^{d}$ | $t^{ch}$ | $t^{d}$
---|---|---|---|---|---|---|---|---
1 | $l_{1}$ | - | - | - | - | 5 | - | 0
2 | $c_{1}$ | $l_{1}$ | 1 | 5 | 1 | 3 | 1 | 2
3 | $c_{1}$ | $l_{1}$ | 1 | 5 | 1 | 5 | 2 | 5
4 | $c_{2}$ | $l_{1}$ | 2 | 5 | 0 | 3 | 3 | 7
5 | $c_{2}$ | $l_{1}$ | 2 | 5 | 0 | 5 | 5 | 9
6 | $c_{2}$ | $c_{1}$ | 3 | 3 | 2 | 3 | 1 | 5
7 | $c_{2}$ | $c_{1}$ | 3 | 3 | 2 | 5 | 3 | 7
8 | $c_{2}$ | $c_{1}$ | 5 | 5 | 4 | 5 | 1 | 6
9 | $l_{2}$ | $c_{1}$ | 6 | 5 | 1 | - | - | 6
10 | $l_{2}$ | $c_{2}$ | 6 | 3 | 0 | - | - | 6

Algorithm Our algorithm employs a best-first search over $GTDS$, utilizing a
list to track nodes (vertices in $GTDS$) and their associated SoC for
expansion. In each iteration, the algorithm selects the node-SoC pair with the
lowest time for expansion and identifies reachable neighbor nodes at the
current SoC level. Instead of considering arrival time, the algorithm
calculates the earliest time to reach a specified SoC level in each neighbor
node and stores it in the list. The routing table captures all details
regarding arrivals, leave times, and leave SoC. Additionally, the algorithm
maintains an upper bound based on the best-travel-time path found so far from
the source to the destination, aiding in pruning paths that cannot surpass
this upper bound. Algorithm 0.3.1 describes the proposed algorithm in details.
The steps are explained as follows:

  * •

Initialization: The origin node with the initial $SoC$ is added to the open
list $\Lb$ (Line 1).

  * •

The iteration over $\Lb$ persists until all items are explored. Every time,
the item with the minimum time is selected and the node-SoC pair is marked as
visited (Line 3).

  * •

Using the $GTDS$, all reachable neighbor nodes based on the available $SoC$ is
determined (Line 4). The arrival time for each reachable node $n$ from the
current node $m$ is the summation of the departure time from $m$ and the
driving time from $n$ to $m$ (Line 5). The remaining charge upon arrival at
$m$, denoted by $SoC^{a}$, is calculated by subtracting the required charge
for travel from $n$ to $m$ with the $SoC$ at the departure time from $n$ (Line
6).

  * •

Records in routing table: For charge value in $LCB$, we find the first
possible consecutive timeslots that the vehicle can get charged (Lines 7 to
14). So, the earliest leave time for node $n$, given its arrival time $t^{a}$
and charge $SoC^{a}$ for each bucket in $LCB$, is considered as $t^{d}$ for
that node. We record ancestor node ($anc$), arrival time from the
ancestor($t^{a}$), leaving $SoC$ from ancestor ($SoC^{anc}$), departure state
of charge ($SoC^{d}$) and time ($t^{d}$) in the routing table (Line 17).

  * •

Upper bound computation: When we reach the destination for the first time, we
set the arrival time as upper bound $ub$, indicating the existence of a
charging path with a travel time of at least $ub$, and from now on any path
with a longer time will be rejected. If the neighboring node $n$ is the
destination and the travel time is less than the current $ub$, we update the
upper bound (Lines 18-19).

  * •

If $n$ is the destination and the travel time is not less than the current
$ub$, we check if $n$ with SoC $b$ is visited. If not, we include $n$ along
with the current charge and departure time in $\Lb$ for later exploration
(Lines 20-21). If $n$ is in $\Lb$ but has not been explored, we check whether
the current solution provides a better travel time and update $\Lb$
accordingly (Lines 22-23).

[t]

GTDS $G$, EVRoutingRequest $r$ Routing table and optimal path upper bound

$\Lb\leftarrow(r.origin,r.SoC,r.time)$, $\Lt\leftarrow null$,
$ub\leftarrow\infty$, $\Lv\leftarrow null$

$\Lb$ has items $(m,s_{m},t_{m})\leftarrow$ Sort $\Lb$ by $time$ and Pop

$\Lv.add((m,s_{m}))$

reachable neighbor $n$ from $m$

$t^{a}=t^{d}\leftarrow t_{m}+w_{m,n}$

$SoC^{a}=SoC^{d}\leftarrow s_{m}-(r_{m,n}/B_{r})$

$b\in LCB$ $t^{w}\leftarrow 0,t^{ch}\leftarrow 0$

$SoC^{d}<b$ $r_{c,t^{d}}$ = 0 $SoC^{d}=SoC^{a},t^{ch}\leftarrow 0$
$SoC^{d}+=r_{c,t^{d}},\>\>t^{d}+=w_{c,t^{d}}$

$t^{ch}+=w_{c,t^{d}}$

$t^{d}>ub$ Go to line 2 Add $(n,m,t^{a},c.SoC,SoC^{a},b,t^{d})$ to $\Lt$

$n=r.dest$ and $ub<t^{d}$ $ub\leftarrow t^{d}$

$(n,b)$ not in $\Lv$ $\Lb.add(n,b,t^{d})$

$t^{d}<$ leave time from $n$ with $b$ in $\Lb$ Update $\Lb$ with $(n,b,t^{d})$
$\Lt,ub$ ForwardPass($G$, $r$)

Complexity If $\eta_{min}$ represents the minimum charging rate of CSs, the
computation of charge time is in the order of $O(B_{r}/\eta_{min})$. Since
this calculation is performed for each pair of edges and LCB, the worst-case
complexity of the forward path algorithm is
$O(|E|\cdot|LCB|\cdot(B_{r}/\eta_{min}))$.

######  Example 0.2.

In Figure 1, we want to find OCPs from $l_{1}$ to $l_{2}$ for an EV with
$B_{r}=5$ and $LCB=\\{3,5\\}$, starting at $t=0$. We start from $l_{1}$ and
find all reachable neighbors, $c_{1}$ and $c_{2}$. The arrival time ($t^{a}$)
and state of charge ($SoC^{a}$) upon reaching $c_{1}$ are 1 and 1, and for
$c_{2}$ are 2 and 0, respectively. Considering $c_{1}$, with $LCB=\\{3,5\\}$,
we need 2 or 4 units of charge start from $t=1$ to leave $c_{1}$. As
$e_{c_{1}}$ at $t=1$ is $<1,2>$, i.e., spending one timeslot results in
$SoC^{d}=3$. Therefore, $(c_{1},3,2)$ is added to $\Lb$, which means there is
a path from source to $c_{1}$ where we can leave $c_{1}$ at $t^{d}=2$ with
$SoC^{d}=3$. The routing table is shown in Table 1. The first row indicates
the starting node, starting $SoC^{d}=5$ and departure time $t^{d}=0$. The
second row is for $(c_{1},3,2)$. As $e_{c_{1}}$ at $t=2$ is $<1,0>$, this
timeslot is already reserved. So, $t=3$ and $t=4$ will be chosen. For $SoC=5$,
the departure time will be 5. Hence, $(c_{1},5,5)$ is added to $\Lb$ and the
corresponding values are shown in row 3 of Table 1. This procedure is also
done for $c_{2}$, where $(c_{2},3,7)$ and $(c_{2},5,9)$ are added to $\Lb$,
and rows 4, 5 are added in routing table.

Next, we choose the option from $\Lb$ with the lowest travel time, which is
$(c_{1},3,2)$. Traversing from $c_{1}$ to $l_{2}$ is not possible, as the
required energy is 4. The only reachable neighbor is $c_{2}$. So, it is
possible to reach $c_{2}$ again, this time from $c_{1}$ with $SoC^{a}=2$,
which entails to have a leave times from node $c_{2}$ at 5 and 7, respectively
(rows 6 and 7). As we have found a faster departure time from node $c_{2}$,
the previous values in $\Lb$ is updated from $(c_{2},3,7)$ and $(c_{2},5,9)$
to $(c_{2},3,5)$ and $(c_{2},5,7)$, respectively. Then, the subsequent
iteration selects $(c_{1},5,5)$. By exploring $c_{1}$ with $SoC^{d}=5$ at
$t=5$, we find a path to destination $l_{2}$ at $t=6$ with $SoC^{a}=1$ (row
9). So, $ub$ is set to 6. The next option is $(c_{2},3,5)$. We find another
path to $l_{2}$ reaching at $t=6$ from $c_{2}$ (row 10). Consequently, all
other options from $\Lb$ are discarded as their departure time is larger than
6.

###  0.3.2 Backward Pass

The purpose of this step is to generate all possible paths utilizing the
routing table generated in the previous step. To accomplish this objective, we
initiate reverse exploration from the destination, considering the upper bound
using the algorithm presented in Algorithm 0.3.2.

Algorithm Initially we create an open list $\Lb$ and add the destination and
$ub$ (found at the end of forward pass) in it (Line 1). In each iteration, an
item is selected from $\Lb$ representing the current node $n$, departure SoC
$s_{n}$, departure upper bound $ub_{n}$, and the constructed path up to that
point (Line 3). Then, Rows from the routing table where departure from $n$
occurred within the specified upper bound ($t^{d}\leq ub$) and $SoC^{d}$
matches the determined value are retrieved (Line 4). Each row corresponds to a
potential distinct path. For each retrieved row, the upper bound of the
ancestor node is calculated by subtracting the driving time from the ancestor
to $n$ and the charging time at $n$ (Lines 5 to 8). Note that, the charge time
is zero when $n$ is either the origin or the destination. If there is waiting
time at the current node, this wait time is considered as a late arrival at
$n$. An ancestor node capable of reaching $n$ at a later time than other
nodes, while still allowing the vehicle to depart within the upper bound and
meeting the required SoC level, is deemed a viable route and added to the list
of paths for exploration. If the ancestor is the origin of $r$, the generated
path is designated as a charging path (Lines 9-10); otherwise, exploration
continues through all open nodes until reaching the origin.

[h] BackwardPass($G$, $r$, $\Lt$, $ub$) GTDS $G$, EVRoutingRequest $r$,
RoutingTable $\Lt$, UpperBound $ub$ All charging paths with minimum travel
time Beginnbeginnende $\Lcp\leftarrow null$,
$\Lb\leftarrow(n=r.dest,soc=*,t=ub,p=[(r.dest,*)])$

$\Lb$ has items $(n,s_{n},ub_{n},p_{n})\leftarrow$ Pop first item from $\Lb$

$Rows\leftarrow$ All rows from $\Lt$ where $V=n$ & $t^{a}<=ub_{n}$ &
$SoC^{d}=s_{n}$

$r\in Rows$

$m=r.anc,s_{m}=r.SoC^{anc}$

$ub_{m}=ub_{n}-w_{m,n}-r.t^{ch}$

$p_{m}\leftarrow p_{n},p_{m}.add(m,s_{m})$

$m=r.origin$ $\Lcp.add(p_{m})$ $\Lb.add(m,s_{m},ub_{m},p_{m})$ $\Lcp$

Complexity If $E_{max}$ defines the maximum number of edges satisfying the
upper-bound constraint for a specific node, then the worst-case complexity of
the backward algorithm is $O(|V|.|E_{max}|)$.

######  Example 0.3.

Here, we demonstrate the backward phase using Table 1. Initially, we put
$(l_{2},*,6,[])$ to $\Lb$. This entry shows that we are looking for any row in
the Table 1 where $V=l_{2}$, $t^{d}=6$. The value matches with rows 9 and 10.
First consider row 9 with ancestor $c_{1}$. Since $l_{2}$ is the destination,
we deduct the driving time from $c_{1}$ to $l_{2}$ from the current $ub$ and
add ($c_{1},5,5,[(l_{2},*)]$) to $\Lb$. Similarly, for row 10,
($c_{2},3,5,[(l_{2},*)]$) is added to $\Lb$. By choosing the next item from
$\Lb$, we retrieve all rows from the routing table that satisfy $v=c_{1}$,
$SoC^{d}=5$, and $t^{d}\leq 5$ (the third row). As $c_{1}$ is a CS, we
subtract the charge and drive time between $c_{1}$ and its ancestor.
Therefore, considering a charge time of 2, the ancestor’s $ub$ will be
$5-2-1$, and SoC will be 5. Consequently, a new item is added to $\Lb$ as
$(l_{1},5,2,[(l_{2},*),(c_{1},5)])$. The procedure is carried out for
$(c_{2},3,5,[(l_{2},*)])$, and $(c_{1},3,3,[(l_{2},*),(c_{2},3)])$ is added to
$\Lb$. For $(l_{1},5,2,[(l_{2},*),(c_{1},5)])$, as $l_{1}$ is the source, the
path $\\{(l_{1},5),(c_{1},5),l_{2}\\}$ is one of the optimal paths. By
exploring the other item $(c_{1},3,3,[(l_{2},*),(c_{2},3)])$ in $\Lb$, we
reach to $(l_{1},5,1,[(l_{2},*),(c_{2},3),(c_{1},3)])$, which leads to the
source. So, the second optimal path will be
$\\{(l_{1},5),(c_{1},3),(c_{2},3),l_{2}\\}$. The travel time of both paths is
6.

##  0.4 Influence factor calculation

The proposed influence factor for a set of optimal paths $OCP(r)$ depends on
the optimal paths of every predicted future requests. So, we utilize the two-
phase algorithm again, but this time for calculating the influence factor. As
not all OCPs of the current request have influence on all future requests, we
first propose a refinement step to determine the future requests for which
calculating influence is not necessary.

Refining the future requests The purpose of the refinement algorithm is to
limit exploration of the search space for requests that exhibit no correlation
with the optimal paths for request $r$. For this purpose, we propose ‘Latest
Leave Time To Impact’ ($LLTI$) in Algorithm 0.4. Initially, the leave time
from any CS for any $OCP(r)$ is recorded in the $LLTI$ (Lines 2-5).
Subsequently, for every node in the $GTDS$, we compute the upper bound
$ub_{m}$ for node $m$ as a neighbor of $n$ to demonstrate that a vehicle must
depart from $m$ no later than $ub_{m}$ to potentially affect one of the paths
in $OCP(r)$ (Lines 8 to 11). This condition is later used to refine future
requests, where calculating influence is unnecessary.

[h] OCP $P$, GTDS $G$ Latest Leave time to Influence on $P$ $\Ln\leftarrow$all
nodes in $G$, $LLTI[\Ln]\leftarrow-1$

$p\in P$ $s\in p$ $LLTI[s]<$ latest charge time at $s$ $LLTI[s]=$ latest
charge time at $s$ $\Ln$ has items $n\leftarrow$ pick from $\Ln$ with highest
$LLTI$, $\Ln.remove(n)$

neighbor $m$ from $n$ $ub_{m}\leftarrow LLTI[n]-w_{n,m}$

$LLTI[m]<ub_{m}$ $LLTI[m]=ub_{m}$ $LLTI$ LeaveTimeToImpact($P$, $G$)

Algorithm for influence factor calculation To calculate influence, we need to
calculate $OCP(r’)$ for all requests $r’\in R’$. However, by utilizing LLTI,
we can determine if further exploration of the search space to find the
optimal path for $r’$ can generate paths that are correlated with any of the
paths $p\in OCP(r)$. If it is not possible to create a correlated path with
OCP(r), we will stop exploring the search space for $r’$.

Since $OCP(r’)$ generates all optimal paths with the minimum travel time, it
is guaranteed that all the paths will have the same travel time. This makes it
impossible to calculate the direct influence. To overcome this, we introduce a
threshold, denoted as $\epsilon$, to establish an upper bound limit for the
travel time of paths included in $OCP(r’)$. In Algorithm 0.5, we compute all
paths with a length equal to or less than the shortest possible travel time
plus $\epsilon$ for each $r’\in R’$ (Lines 3-13). The feasibility of
generating a path to impact $OCP(r)$ is examined (Line 6), and the upper bound
is set as the sum of the travel length of the shortest found path plus
$\epsilon$ (Lines 11-12). After generating all paths using the backward pass
in Line 14, we determine the direct influence of path $p$ on future requests
in Lines 16-19 by calculating the amount of increase in the travel time of
future requests $R^{\prime}$ for each path $p\in P_{r}$. If path $p$ renders
all paths for request $r^{\prime}\in R^{\prime}$ unavailable, then we set the
$ub$ for request $r^{\prime}$ as travel time for that request (Line 18).
Finally, the indirect influence in Lines 20-21 is calculated as the number of
paths that become unavailable because of $p$.

##  0.5 Proactive route planning algorithm

The Algorithm 0.5 presents the overall proactive route planner. First, all
optimal paths for request $r$ are identified in Lines 1-2. Then, the influence
factor for each path is calculated (Line 3). The proactive path for $r$ is
then determined by selecting the path with the lowest direct influence. If
there are multiple paths with the same minimum direct influence, the proactive
path is chosen based on the minimum indirect influence.

[t]

GTDS $G$, OCP $P_{r}$, RoutingRequests $R^{\prime}$, Threshold $\epsilon$ All
charging paths with minimum travel time

$LLTI\leftarrow LeaveTimeToImpact(P_{r},G)$

$DirectInf[P_{r}]\leftarrow 0$, $IndirectInf[P_{r}]\leftarrow 0$

$r^{\prime}\in R^{\prime}$
$\Lb\leftarrow(r^{\prime}.origin,r^{\prime}.SoC,r^{\prime}.time)$,
$\Lt=\Lv\leftarrow null$, $ub\leftarrow\infty$

$\Lb$ has items $t_{m}<=LLTI[m]\>\>\forall(m,s_{m},t_{m})\in\Lb$ Lines 4 - 16
of ForwardPath Algorithm

$t^{d}>ub+\epsilon$ Go to line 3 Add $(n,m,t^{a},c.SoC,SoC^{a},b,t^{d})$ to
$\Lt$

$n=r.dest$ and $ub<t^{d}+\epsilon$ $ub\leftarrow t^{d}+\epsilon$ Lines 22 - 25
of ForwardPass algorithm $P_{r^{\prime}}=BackwardPass(G,r^{\prime},\Lt,ub)$

$p\in P_{r}$

$P^{nco}_{r^{\prime}}$ = paths from $P_{r^{\prime}}$ where
$co(p_{r^{\prime}},p)=0$

$t_{p_{r^{\prime}}}$ = min travel time in $P_{r^{\prime}}$

$t^{\prime}_{p_{r^{\prime}}}$ = min travel time in $P^{nco}_{r^{\prime}}$, set
$ub_{r^{\prime}}$ if $P^{nco}_{r^{\prime}}$ is $Null$

$DirectInf[p]+=t^{\prime}_{p_{r^{\prime}}}-t_{p_{r^{\prime}}}$

$P^{co}_{r^{\prime}}$ = paths from $P_{r^{\prime}}$ where
$co(p_{r^{\prime}},p)=1$

$IndirectInf[p]+=len(P^{co}_{r^{\prime}})$ $DirectInf$, $IndirectInf$
InfluenceFactorCalculator($G$, $P_{r}$, $R^{\prime}$, $\epsilon$)

EVRoutingRequest $r$, RoutingRequests $R^{\prime}$, GTDS $G$ A proactive path

$\Lt,ub=ForwardPass(G,r)$

$P_{r}=BackwardPass(G,r,\Lt,ub)$

$Inf_{d},Inf_{i}=InfluenceFactorCalculator(G,P_{r},R^{\prime},\epsilon)$

$idx=argmin(Inf_{d})$

No. of elements in $Inf_{d}$ with value equal to $Inf_{d}[idx]>1$

$idx=argmin(Inf_{i})$ while $inf_{d}[idx]=min(inf_{d})$

$P_{r}[idx]$ ProactiveRoutePlanning($r$,$R^{\prime}$ $G$ )


# MM-PhyRLHF: Reinforcement Learning Framework for Multimodal Physics
Question-Answering

Avinash Anand<EMAIL_ADDRESS>IIIT DelhiDelhiIndia ,  Janak Kapuriya
<EMAIL_ADDRESS>IIIT DelhiDelhiIndia ,  Chhavi Kirtani
<EMAIL_ADDRESS>IIIT DelhiDelhiIndia ,  Apoorv Singh
<EMAIL_ADDRESS>IIIT DelhiDelhiIndia ,  Jay Saraf
<EMAIL_ADDRESS>IIIT DelhiDelhiIndia ,  Naman Lal
<EMAIL_ADDRESS>IIIT DelhiDelhiIndia ,  Jatin Kumar
<EMAIL_ADDRESS>IIIT DelhiDelhiIndia ,  Adarsh Raj Shivam
<EMAIL_ADDRESS>IIIT DelhiDelhiIndia ,  Astha Verma
<EMAIL_ADDRESS>IIIT DelhiDelhiIndia ,  Rajiv Ratn Shah
<EMAIL_ADDRESS>IIIT DelhiDelhiIndia and  Roger Zimmermann
<EMAIL_ADDRESS>National University of SingaporeSingaporeSingapore

(2018)

###### Abstract.

Recent advancements in LLMs have shown their significant potential in tasks
like text summarization and generation. Yet, they often encounter difficulty
while solving complex physics problems that require arithmetic calculation and
a good understanding of concepts. Moreover, many physics problems include
images that contain important details required to understand the problem’s
context. We propose an LMM-based chatbot to answer multimodal physics MCQs.
For domain adaptation, we utilize the MM-PhyQA dataset comprising Indian high
school-level multimodal physics problems. To improve the LMM’s performance, we
experiment with two techniques, RLHF (Reinforcement Learning from Human
Feedback) and Image Captioning. In image captioning, we add a detailed
explanation of the diagram in each image, minimizing hallucinations and image
processing errors. We further explore the integration of Reinforcement
Learning from Human Feedback (RLHF) methodology inspired by the ranking
approach in RRHF to enhance the human-like problem-solving abilities of the
models. The RLHF approach incorporates human feedback into the learning
process of LLMs, improving the model’s problem-solving skills, truthfulness,
and reasoning capabilities, minimizing the hallucinations in the answers, and
improving the quality instead of using vanilla-supervised fine-tuned models.
We employ the LLaVA open-source model to answer multimodal physics MCQs and
compare the performance with and without using RLHF.

Large Language Models, Large Multimodal Models, Reinforcement Learning,
Physics, Educational AI

††copyright: acmlicensed††journalyear: 2018††doi: XXXXXXX.XXXXXXX††conference:
Make sure to enter the correct conference title from your rights confirmation
emai; June 03–05, 2018; Woodstock, NY††isbn: 978-1-4503-XXXX-X/18/06††ccs:
Applied computing Physics

##  1\. Introduction

The current generation of LLMs like Chat-GPT and GPT4 have shown impressive
performance in tasks like text generation, translation, summarization,
sentiment analysis, and question answering, enabling more accurate and
contextually relevant language understanding and generation. With newer
research, these models have also shown impressive performance in domain-
specific tasks through fine-tuning. Moreover, newer capabilities of handling
multimodal input data are making strides in the academic landscape,
exemplified by GPT-4V, Gemini, and open-source LLaVA models that can process
and generate content across multiple modalities, including images, audio, and
video.

Combining the LLM’s capability of data processing, text generation, contextual
reasoning, and pattern recognition with its capabilities of handling multiple
modalities has made it a popular option for educational question-answering.
LLMs can serve as 24/7 virtual assistants for answering student queries in
various subjects, thus enhancing understanding and clearing doubts outside the
traditional classroom setting. These LLMs can revolutionize exam preparation
by creating well-rounded question-answering systems with domain-specific
assistance and instant clarifications. LLMs can also tailor content according
to each student’s learning style, needs, and preferences by analyzing the way
a student interacts and performs.

Recent research has portrayed LLM’s ability to retrieve and provide accurate
information from vast knowledge bases, essential for educational question-
answering systems (Li et al., 2023; Xiao et al., 2023) noted positive feedback
received from middle school teachers about using LLMs in education stating
that LLMs significantly reduce the time and cost of obtaining diverse and
personalized learning materials. (Abbasiantaeb et al., 2024) underscore LLMs’
capability of simulating high-quality student-teacher interaction while
covering a broader aspect of the given topic, suggesting LLMs’ potential to
enhance the depth and breadth of educational content. Hence, developing open-
source educational question-answering models using LLMs is promising. While
some work has been done in the field of multimodal question-answering in
science, maths, etc., this work is fresh in the Indian context, especially for
high-quality physics problems at the level of Indian competitive examinations
like JEE and NEET.

(Li et al., 2023) underline the importance of developing LLMs capable of
handling multimodal information for educational problems that include text and
images, which is crucial for creating more comprehensive and effective
educational tools. Moreover, (Xiao et al., 2023) highlighted the importance of
feedback collection as a method to enhance domain-adaptation of subjects and
offer further improvement of LLMs in the educational domain. As noted by (Li
et al., 2023), it is imperative to enhance the multimodal capabilities of
currently available LLMs to create a more well-rounded question-answering
system. Multi-modal processing problems such as hallucinations where the model
perceives information that is non-existent and non-sensical, inability to
integrate modalities to understand the context and the significance of all
modalities about each other, and domain adaptation issues are still
persistent. Improving the multimodal capabilities of models is crucial,
especially in the field of question-answering, where the inclusion of images
can exponentially increase the understandability of the question and result in
more accuracy. Furthermore, as noted by (Anand et al., 2023f, e; Xiao et al.,
2023) LLMs’ contextual reasoning and capability of generating more human-like
responses in the educational domain can be improved.

MICoT-QA (Anand et al., 2024) compared the performance of fine-tuning open-
source LLMs, while additionally exploring the technique of Chain-of-Thought
Prompting. To tackle the problems faced by LLMs in multimodal processing as
well as domain-specific reasoning as discussed above, we propose improvements
to MICoT-QA by utilizing two techniques, Reinforcement Learning and Human
Feedback (RLHF) and Image Captioning.

For every image in the training dataset, we add a detailed explanation of the
diagram to provide the model with extra context helping it avoid
hallucinations. We utilize the Infi-MM captioning model to generate captions
for every image, before passing these images along with the accompanying
question and answers to the fine-tuning pipeline.

To enhance the model’s reasoning capabilities and align their response to a
more humanized version is where Reinforcement Learning from Human
Feedback(RLHF) plays an important role. At the core of RLHF lies preference
data which involves rating and comparing various responses generated by
different models to the same prompt. The model is further trained on this
preference data and thereafter multiple reinforcement learning algorithms like
Proximal Policy Optimization (PPO) (Schulman et al., 2017) and Direct
Preference Optimization (DPO) (Rafailov et al., 2024) are applied to fine-tune
the LMMs to optimize the rewards. RLHF technique has been proven to boost LLMs
reasoning by bridging the gap between human intuition and AI and generating
more rational and human-aligned solutions (ref: Boosting LLMs Physics
Reasoning with Human-AI Guided Reinforcement Learning Conclusion section).

The three stages of RLHF are:

  1. (1)

Collecting human feedback to rank multiple responses to the same questions
based on the quality of their reasoning.

  2. (2)

Training the reward model: The Reward Model (RM) is trained methodologically
using our dataset MM-PhyQA.

  3. (3)

Refining the policy: An iterative process where the policy keeps getting
updated based on new feedback and changes.

Overall, our contributions to this paper are as follows:

  1. (1)

Enhance the MM-PhyQA dataset by using the image captioning methodology. This
benefits the LLM by reducing hallucinations and adding more context to the
problem.

  2. (2)

Applying the RLHF technique to encourage more human-like responses to complex
problems.

  3. (3)

Compare results of the LLM-based physics question answering between the
following experiment settings:

    1. 3.1

Fine Tune LLaVa Models using (Sample Question and Answer, Image, Caption) with
RLHF technique

    2. 3.2

Fine Tune LLaVa Models using (Sample Question and Answer, Caption) with RLHF
technique

    3. 3.3

Fine Tune LLaVa Models using (Sample Question and Answer, Image) with RLHF
technique

##  2\. Related Work

###  2.1. Vision LLMs

Recent advancements have led to the creation of Vision Language Models, models
capable of processing and interpreting visual information along with textual
information. Flamingo has been designed to leverage visual and language inputs
as prompts, showing remarkable few-shot performance in visual question-
answering tasks. Models like GPT4 (Achiam et al., 2023), LLaVA series (Liu et
al., 2024a), and MiniGPT4 (Zhu et al., 2023) introduced the method of visual
instruction tuning to enhance the instruction-following abilities of VLLMs,
meaning training the model to interpret and process visual cues in conjunction
with textual instructions. VisionLLM (Wang et al., 2024), Kosmos-2 (Peng et
al., 2023), Qwen-VL (Bai et al., 2023) have been improved by using visual
grounding capabilities, enabling them to perform tasks such as describing
specific regions within an image (region description) and identifying the
location of objects or elements within an image (localization), making them
more adept at tasks that require nuanced understanding of the visual elements.
PaLM-E (Driess et al., 2023) and EmbodiedGPT (Mu et al., 2024) models are
designed to interact with and navigate through physical or simulated
environments, understanding visual inputs in the context of actions and
interactions, which represents significant strides in adapting VLLMs for
embodied applications.

###  2.2. RLHF

In addressing the limitations of traditional LLM approaches, the emergence of
Reinforcement Learning from Human Feedback (RLHF) has been pivotal, as noted
in research by (Xie et al., 2023). This method, initially focused on tasks
such as text summarization (Stiennon et al., 2020) and question answering
(Nakano et al., 2021), has evolved to improve general-purpose language models.
The RLHF domain has expanded further with Reinforcement Learning from AI
Feedback (RLAIF) by (Lee et al., 2023), addressing the scalability challenges
and the need for quality human labels, as analyzed by (Zheng et al., 2024).
Additionally, UltraFeedback (Cui et al., 2023) represents a significant
advancement in ranking diverse human and AI preferences, highlighting the
ongoing evolution and adaptation in language model development. In the context
of question-answering systems, (Kirk et al., 2023; Goel et al., 2023) presents
an in-depth analysis of the impact of RLHF on LLMs by evaluating each stage of
an RLHF pipeline separately, showcasing the importance of RLHF in improving
Out-Of-Distribution performance suggesting that RLHF models are more adaptable
to a wider variety of scenarios not seen during training. (Nakano et al.,
2021) explored the benefit of RLHF in browser-assisted question answering with
human feedback on the performance in question answering. We utilize the PPO
method for the RLHF implementation in our application. The Proximal Policy
Optimization (PPO) Algorithm was introduced by (Schulman et al., 2017) by
ChatGPT creator OpenAI’s scientist as a method to implement policy updates and
reward models in RLHF. It proposes a mechanism that restricts the policy
update steps, preventing them from being too large and potentially
destabilizing the training process, and unlike standard policy gradient
methods that perform one update per data sample, PPO allows for several epochs
of minibatch updates on the same set of sampled data, offering a balance
between performance and ease of implementation.

###  2.3. Image Captioning

To address the limitations of multimodal processing of LLMs and to reduce the
hallucinations of the models, image captioning has been effective as noted by
research conducted by (Salaberria et al., 2023) and (Zhang et al., 2024).
(Salaberria et al., 2023) conducted experiments comparing the performance of
available LMMs with multimodal text and image input to the performance of LLMs
with text-only input accompanied by image captioning instead of the image in
Visual Question Answering tasks. The research reported improved accuracy for
LLMs given text-only image-captioned input, representing the benefit of
providing the model with more context by adding image captions. (Zhang et al.,
2024) explored image captioning for mathematical question answering by giving
6 varied versions of a problem, each offering varying degrees of multi-
modality information as image captions. They report that most MLLMs struggle
to understand mathematical diagrams and heavily rely on textual data,
signifying the importance of image captioning.

###  2.4. Application in Education

(Filippo et al., 2024) studies the many applications of LLMs, including
education. LLMs present opportunities for personalized learning materials,
improved productivity, and increased accessibility. (Mitra et al., 2024)
developed an LLM-based student-facing assistant in the discussion forum and
tested the performance in upper-division data science courses, suggesting the
practicality of deploying LLMs as tutoring and question-answering assistants.
(Prather et al., 2023) present an extensive literature review of the usage of
LLMs in education, specifically in the computing domain, as an AI assistant
for teaching coding (Puryear and Sprint, 2022), answering questions on the
course discussion boards (Jaipersaud et al., 2023), providing feedback for
programming assignments (Balse et al., 2023; Pankiewicz and Baker, 2023), and
more. The advancements in Large Language Models (LLMs) within high-school
physics education are highlighted in the research ”Revolutionizing High School
Physics Education: A Novel Dataset” (Anand et al., 2023a). This study
showcases the creation of a specialized dataset from NCERT exemplar solutions,
expanding from 766 to 7,983 physics questions. The primarily text-based
dataset, formatted in JSON, demonstrates LLMs’ potential in handling complex
educational content, as evidenced by significant METEOR and BERTScore F1
metrics. This development is pivotal in LLM applications for high-school
education, enriching the scope of multimodal learning environments. (Sapkota
and Bondurant, 2024) reported the limitations of ChatGPT in mathematical
education tasks like question generation, suggesting a need for further
improvement in domain adaptation and contextual understanding of LLMs.

##  3\. Dataset

We possess the MMPhy-QA dataset, which is an extensive compilation comprising
a diverse range of multimodal multiple-choice physics questions along with
their corresponding answers. This dataset has been meticulously curated to
serve as a valuable resource for promoting a comprehensive understanding and
assessment of physics principles. Within this dataset, the training section
consists of 3700 samples, carefully selected to cover a broad spectrum of
physics topics, while the test section comprises 676 samples, intentionally
designed to evaluate the performance and adaptability of models.

In our efforts to further strengthen the robustness and effectiveness of our
model, we strategically extracted 2000 instances from the training set to
create a specialized preference dataset, tailored specifically for
Reinforcement Learning with Human Feedback (RLHF) training. This strategic
augmentation aims to leverage human feedback to refine and enhance the model’s
responses, thereby fostering deeper understanding and more refined reasoning
abilities. Each of the 2000 selected samples underwent meticulous inference
using models llava_13b, llava_1_5_7b, llava_1_5_13b, llava_1_5_13b_lora_large,
and GPT4 to generate 5 responses. These 5 responses were then passed on to
Gemini Pro, an advanced evaluation tool renowned for its sophisticated ranking
algorithms and analytical capabilities. Leveraging the capabilities of Gemini
Pro, we meticulously evaluated and ranked the generated responses,
scrutinizing their overall coherence in reasoning and adherence to the
provided prompts.

Based on the rankings obtained from Gemini Pro, we arranged the responses into
paired sets, pairing the highest-ranked response with every other response.
This meticulous pairing approach resulted in four distinct preference pairs
per sample, effectively quadrupling the dataset’s size and infusing it with
diverse viewpoints and nuanced variations. Consequently, our preference
dataset now comprises a comprehensive array of 8000 samples, each meticulously
crafted to foster nuanced comprehension and facilitate robust model training.

To provide a deeper understanding of the structure and composition of the
dataset, we have included a detailed diagram delineating the intricate
relationships and pairings within the preference dataset. This graphical
representation serves as a valuable tool, offering insights into the dataset’s
organizational framework and aiding in the comprehension of its complexities
and subtleties.

Preference dataset Pipeline

Figure 1. Preference dataset Pipeline

##  4\. Proposed Methodology

###  4.1. Dataset

We utilize the MM-PhyQA dataset from ”MM-PhyQA: Multimodal Physics Question-
Answering With Multi-Image CoT Prompting” (Anand et al., 2023a, d, b, c) for
experimentation in this paper. MM-PhyQA addresses the lack of multimodal
datasets that comprise physics questions and are catered to high school
students. The dataset is geared toward competitive examinations conducted
throughout India. 300 questions in the dataset were initially manually
created, each sample consists of a question, four options, and a final answer
along with an explanation. Further, ChatGPT was used for data augmentation by
giving a prompt to create other variations of the text while ensuring that the
meaning remained the same, bringing the total count of the questions in the
dataset to 4500.

###  4.2. Preference dataset creation for RLHF

We employed the MM-PhyQA dataset to construct a preference dataset for the
training of the Reward Model (RM) component. The dataset incorporates
contributions from five open-source models: llava_13b, llava_1_5_7b,
llava_1_5_13b, llava_1_5_13b_lora_large, and GPT4, each generating five
distinct responses. These responses were subjected to an evaluation process
using Gemini Pro, a sophisticated evaluation tool renowned for its advanced
ranking algorithms and analytical prowess. Leveraging the capabilities of
Gemini Pro, we conducted a thorough assessment and ranking of the responses,
focusing on their coherence in reasoning and adherence to the provided
prompts. The evaluation outcomes facilitated the organization of the responses
into paired sets by pairing the highest-ranked response with each of the other
responses. This method of pairing yielded four unique preference pairs per
sample, effectively augmenting the dataset’s volume and introducing a rich
diversity of perspectives and subtle distinctions. As a result, the preference
dataset was expanded to include a total of 8000 samples, each carefully
curated to enhance nuanced understanding and support the effective training of
the model.

###  4.3. Fine-Tuning

We use the MM-PhyQA dataset consisting of 4500 samples to fine-tune each of
these pre-trained models: Llava1.5 7b, Llava1.5 13b, Llava1.5 13b lora large.
The dataset is split into training and testing sets with a 70:30 ratio To
optimize the training of these LLMs, we employed PEFT (Parameter Efficient
Fine Tuning) (Liu et al., 2022). Additionally, the hyper-parameter
configuration utilized for training the SFT module includes 4 epochs, a batch
size of 8, a learning rate of 3e-4, and an Adam optimizer.

###  4.4. RLHF Pipeline

We incorporate the Reinforcement Learning from Human Feedback (RLHF)
methodology into the training process of our LLM to enhance its contextual
reasoning capabilities and ensure its outputs are in line with human
preferences. The Preference Dataset mentioned in section 4.2 serves as the
foundation for training a Reward Model (RM), selected as LLaVA2-13B for this
research. By training the RM on the preference dataset, it learns to predict
the quality of a response based on the rankings. It utilizes the criteria of
coherence in reasoning and adherence to initial prompts as established during
the creation of the Preference Dataset to predict the anticipated reward for
any response produced by the LLM. After training the RM, we use it to apply
the PPO algorithm to each of the fine-tuned LLMs. During this phase, the LLM
generates responses that are evaluated by the RM, and it receives feedback in
the form of predicted rewards from the RM. The process of generating
responses, evaluating them with the RM, and updating the LLM using policy
optimization is repeated iteratively.

###  4.5. Image Captioning

To enhance multimodal processing and reduce the hallucinations of the model,
we add captions to every image in the training dataset during fine-tuning. We
utilized Infi-MM (Liu et al., 2024b), a novel architecture designed to
recognize and understand detailed information in high-resolution images
accurately, in our pipeline that takes input as the sample dataset MM-PhyQA
and returns the samples accompanied with image captions. This modified dataset
is then used for the fine-tuning of the pre-trained model, as described in
section 4.3.

##  5\. Experiments

Using the above methodology, we experiment to evaluate and compare the
performance of physics question-answering LLM in the context of Indian high
schools. We will integrate the RLHF and Image Captioning techniques with the
novel method introduced by (Anand et al., 2023b; Goel et al., 2023) which is
multi-image chain-of-thought prompting to enhance LLM’s performance for
physics-based question-answering. By integrating RLHF and Image Captioning
techniques, we aim to improve the accuracy and contextual reasoning of the
LLMs and contribute to the advancement of educational chatbots.

We experiment with the following six training settings:

  1. (1)

Fine Tune LLaVa Models using (Sample Question and Answer, Image, Caption)

  2. (2)

Fine Tune LLaVa Models using (Sample Question and Answer, Caption)

  3. (3)

Fine Tune LLaVa Models using (Sample Question and Answer, Image)

  4. (4)

Fine Tune LLaVa Models using (Sample Question and Answer, Image, Caption) with
RLHF technique integrated

  5. (5)

Fine Tune LLaVa Models using (Sample Question and Answer, Caption) with RLHF
technique integrated

  6. (6)

Fine Tune LLaVa Models using (Sample Question and Answer, Image) with RLHF
technique integrated

By comparing the performance of the LLM across the above six different
settings, we will be able to understand the extent of improvement Image
Captioning and RLHF techniques provide.

Furthermore, we use the following three LLMs as our base model:

  1. (1)

Llava -1.5 7b

  2. (2)

Llava -1.5 13b

  3. (3)

Llava -1.5 13b LoRA large

We experimented with different LoRA values in the case of the LLaVA 1.5 model.
LoRA or Low-Rank Adaptation (Hu et al., 2021), is a method to represent the
weight changes during the training process in lower-ranked matrices. This is
especially useful while fine-tuning general-purpose LLMs, as it speeds up the
training process. A lower LoRA rank means fewer parameters are learned during
the adaptation process, however, it results in a faster training process as
well. We tested the 7b (7 billion) and 13b (13 billion) variants of LLaVA
which correspond to the number of learning parameters. The different LLaVA
configurations also formed the basis of our comparison of the performance of
our technique.

##  6\. Results and Discussion

Tables 1, 2, and 3 show the accuracy scores on the test dataset for the
experiment settings 1-3 mentioned in section 5 - Experiments.

SFT Training Input: Text + Image
---
Model |  Accuracy |  LoRA
Llava -1.5 7b |  53.3% |  64
Llava -1.5 13b |  52.7% |  64
Llava -1.5 13b lora large |  53.1% |  128
Table 1. Accuracy recorded when the training dataset contained only the
Question and Answer text and the accompanying image. This experiment involves
only Supervised Fine-Tuning. SFT Training Input: Text + Image + Caption
---
Model |  Accuracy |  LoRA
Llava -1.5 7b |  82.52% |  64
Llava -1.5 13b |  83.28% |  64
Llava -1.5 13b lora large |  82.1% |  128
Table 2. Accuracy recorded when the training dataset contained only the
Question and Answer text, the accompanying image, and the image’s caption.
This experiment involves only Supervised Fine-Tuning. SFT Training Input: Text
+ Caption
---
Model |  Accuracy |  LoRA
Llava -1.5 7b |  66.95% |  64
Llava -1.5 13b |  64.0% |  64
Llava -1.5 13b lora large |  74.56% |  128
Table 3. Accuracy recorded when the training dataset contained only the
Question and Answer text and the caption of the accompanying image (Image was
not provided). This experiment involves only Supervised Fine-Tuning.

##  7\. Conclusion

## References

  * (1)
  * Abbasiantaeb et al. (2024) Zahra Abbasiantaeb, Yifei Yuan, Evangelos Kanoulas, and Mohammad Aliannejadi. 2024.  Let the llms talk: Simulating human-to-human conversational qa via zero-shot llm-to-llm interactions.  , 8–17 pages.
  * Achiam et al. (2023) Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023\.  Gpt-4 technical report.
  * Anand et al. (2023a) Avinash Anand, Krishnasai Addala, Kabir Baghel, Arnav Goel, Medha Hira, Rushali Gupta, and Rajiv Ratn Shah. 2023a.  Revolutionizing High School Physics Education: A Novel Dataset.  , 64–79 pages.
  * Anand et al. (2023b) Avinash Anand, Arnav Goel, Medha Hira, Snehal Buldeo, Jatin Kumar, Astha Verma, Rushali Gupta, and Rajiv Ratn Shah. 2023b.  SciPhyRAG-Retrieval Augmentation to Improve LLMs on Physics Q &A.  , 50–63 pages.
  * Anand et al. (2023c) Avinash Anand, Mohit Gupta, Kritarth Prasad, Ujjwal Goel, Naman Lal, Astha Verma, and Rajiv Ratn Shah. 2023c.  KG-CTG: Citation Generation Through Knowledge Graph-Guided Large Language Models.  , 37–49 pages.
  * Anand et al. (2023d) Avinash Anand, Mohit Gupta, Kritarth Prasad, Navya Singla, Sanjana Sanjeev, Jatin Kumar, Adarsh Raj Shivam, and Rajiv Ratn Shah. 2023d.  Mathify: Evaluating Large Language Models on Mathematical Problem Solving Tasks.
  * Anand et al. (2023e) Avinash Anand, Atharv Jairath, Naman Lal, Siddhesh Bangar, Jagriti Sikka, Astha Verma, Rajiv Ratn Shah, and Shin’ichi Satoh. 2023e.  GEC-DCL: Grammatical Error Correction Model with Dynamic Context Learning for Paragraphs and Scholarly Papers.  , 95–110 pages.
  * Anand et al. (2024) Avinash Anand, Janak Kapuriya, Apoorv Singh, Jay Saraf, Naman Lal, Astha Verma, Rushali Gupta, and Rajiv Shah. 2024.  MM-PhyQA: Multimodal Physics Question-Answering With Multi-Image CoT Prompting.
  * Anand et al. (2023f) Avinash Anand, Kritarth Prasad, Ujjwal Goel, Mohit Gupta, Naman Lal, Astha Verma, and Rajiv Ratn Shah. 2023f.  Context-Enhanced Language Models for Generating Multi-paper Citations.  , 80–94 pages.
  * Bai et al. (2023) Jinze Bai, Shuai Bai, Shusheng Yang, Shijie Wang, Sinan Tan, Peng Wang, Junyang Lin, Chang Zhou, and Jingren Zhou. 2023.  Qwen-vl: A versatile vision-language model for understanding, localization, text reading, and beyond.
  * Balse et al. (2023) Rishabh Balse, Bharath Valaboju, Shreya Singhal, Jayakrishnan Madathil Warriem, and Prajish Prasad. 2023.  Investigating the potential of gpt-3 in providing feedback for programming assessments.  , 292–298 pages.
  * Cui et al. (2023) Ganqu Cui, Lifan Yuan, Ning Ding, Guanming Yao, Wei Zhu, Yuan Ni, Guotong Xie, Zhiyuan Liu, and Maosong Sun. 2023.  Ultrafeedback: Boosting language models with high-quality feedback.
  * Driess et al. (2023) Danny Driess, Fei Xia, Mehdi SM Sajjadi, Corey Lynch, Aakanksha Chowdhery, Brian Ichter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong, Tianhe Yu, et al. 2023\.  Palm-e: An embodied multimodal language model.
  * Filippo et al. (2024) Chiarello Filippo, Giordano Vito, Spada Irene, Barandoni Simone, and Fantoni Gualtiero. 2024.  Future applications of generative large language models: A data-driven case study on ChatGPT.  _Technovation_ 133 (2024), 103002.
  * Goel et al. (2023) Arnav Goel, Medha Hira, Avinash Anand, Siddhesh Bangar, and Dr Rajiv Ratn Shah. 2023.  Advancements in Scientific Controllable Text Generation Methods.
  * Hu et al. (2021) Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2021.  Lora: Low-rank adaptation of large language models.
  * Jaipersaud et al. (2023) Brandon Jaipersaud, Paul Zhang, Jimmy Ba, Andrew Petersen, Lisa Zhang, and Michael R Zhang. 2023.  Decomposed Prompting to Answer Questions on a Course Discussion Board.  , 218–223 pages.
  * Kirk et al. (2023) Robert Kirk, Ishita Mediratta, Christoforos Nalmpantis, Jelena Luketina, Eric Hambro, Edward Grefenstette, and Roberta Raileanu. 2023.  Understanding the effects of rlhf on llm generalisation and diversity.
  * Lee et al. (2023) Harrison Lee, Samrat Phatale, Hassan Mansoor, Kellie Lu, Thomas Mesnard, Colton Bishop, Victor Carbune, and Abhinav Rastogi. 2023.  Rlaif: Scaling reinforcement learning from human feedback with ai feedback.
  * Li et al. (2023) Qingyao Li, Lingyue Fu, Weiming Zhang, Xianyu Chen, Jingwei Yu, Wei Xia, Weinan Zhang, Ruiming Tang, and Yong Yu. 2023.  Adapting Large Language Models for Education: Foundational Capabilities, Potentials, and Challenges.
  * Liu et al. (2024a) Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. 2024a.  Visual instruction tuning.
  * Liu et al. (2022) Haokun Liu, Derek Tam, Mohammed Muqeeth, Jay Mohta, Tenghao Huang, Mohit Bansal, and Colin A Raffel. 2022.  Few-shot parameter-efficient fine-tuning is better and cheaper than in-context learning.  _Advances in Neural Information Processing Systems_ 35 (2022), 1950–1965.
  * Liu et al. (2024b) Haogeng Liu, Quanzeng You, Xiaotian Han, Yiqi Wang, Bohan Zhai, Yongfei Liu, Yunzhe Tao, Huaibo Huang, Ran He, and Hongxia Yang. 2024b.  InfiMM-HD: A Leap Forward in High-Resolution Multimodal Understanding.
  * Mitra et al. (2024) Chancharik Mitra, Mihran Miroyan, Rishi Jain, Vedant Kumud, Gireeja Ranade, and Narges Norouzi. 2024.  Elevating Learning Experiences: Leveraging Large Language Models as Student-Facing Assistants in Discussion Forums.  , 1752–1753 pages.
  * Mu et al. (2024) Yao Mu, Qinglong Zhang, Mengkang Hu, Wenhai Wang, Mingyu Ding, Jun Jin, Bin Wang, Jifeng Dai, Yu Qiao, and Ping Luo. 2024.  Embodiedgpt: Vision-language pre-training via embodied chain of thought.
  * Nakano et al. (2021) Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al. 2021\.  Webgpt: Browser-assisted question-answering with human feedback.
  * Pankiewicz and Baker (2023) Maciej Pankiewicz and Ryan S Baker. 2023.  Large Language Models (GPT) for automating feedback on programming assignments.
  * Peng et al. (2023) Zhiliang Peng, Wenhui Wang, Li Dong, Yaru Hao, Shaohan Huang, Shuming Ma, and Furu Wei. 2023.  Kosmos-2: Grounding multimodal large language models to the world.
  * Prather et al. (2023) James Prather, Paul Denny, Juho Leinonen, Brett A Becker, Ibrahim Albluwi, Michelle Craig, Hieke Keuning, Natalie Kiesler, Tobias Kohn, Andrew Luxton-Reilly, et al. 2023\.  The robots are here: Navigating the generative ai revolution in computing education.  , 108–159 pages.
  * Puryear and Sprint (2022) Ben Puryear and Gina Sprint. 2022.  Github copilot in the classroom: learning to code with AI assistance.  _Journal of Computing Sciences in Colleges_ 38, 1 (2022), 37–47.
  * Rafailov et al. (2024) Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. 2024.  Direct preference optimization: Your language model is secretly a reward model.
  * Salaberria et al. (2023) Ander Salaberria, Gorka Azkune, Oier Lopez de Lacalle, Aitor Soroa, and Eneko Agirre. 2023.  Image captioning for effective use of language models in knowledge-based visual question answering.  _Expert Systems with Applications_ 212 (2023), 118669.
  * Sapkota and Bondurant (2024) Bima Sapkota and Liza Bondurant. 2024.  Assessing concepts, procedures, and cognitive demand of ChatGPT-generated mathematical tasks.  _International Journal of Technology in Education_ 7, 2 (2024), 218–238.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal policy optimization algorithms.
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. 2020.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ 33 (2020), 3008–3021.
  * Wang et al. (2024) Wenhai Wang, Zhe Chen, Xiaokang Chen, Jiannan Wu, Xizhou Zhu, Gang Zeng, Ping Luo, Tong Lu, Jie Zhou, Yu Qiao, et al. 2024\.  Visionllm: Large language model is also an open-ended decoder for vision-centric tasks.
  * Xiao et al. (2023) Changrong Xiao, Sean Xin Xu, Kunpeng Zhang, Yufang Wang, and Lei Xia. 2023.  Evaluating reading comprehension exercises generated by LLMs: A showcase of ChatGPT in education applications.  , 610–625 pages.
  * Xie et al. (2023) Yuanzhen Xie, Tao Xie, Mingxiong Lin, WenTao Wei, Chenglin Li, Beibei Kong, Lei Chen, Chengxiang Zhuo, Bo Hu, and Zang Li. 2023.  Olagpt: Empowering llms with human-like problem-solving abilities.
  * Zhang et al. (2024) Renrui Zhang, Dongzhi Jiang, Yichi Zhang, Haokun Lin, Ziyu Guo, Pengshuo Qiu, Aojun Zhou, Pan Lu, Kai-Wei Chang, Peng Gao, et al. 2024\.  MathVerse: Does Your Multi-modal LLM Truly See the Diagrams in Visual Math Problems?
  * Zheng et al. (2024) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. 2024\.  Judging llm-as-a-judge with mt-bench and chatbot arena.
  * Zhu et al. (2023) Deyao Zhu, Jun Chen, Xiaoqian Shen, Xiang Li, and Mohamed Elhoseiny. 2023.  Minigpt-4: Enhancing vision-language understanding with advanced large language models.


in the disjoint cycle decomposition of $\tau$, as calculated in Proposition
3.14, we denote its corresponding basis element in $\ker(\mathcal{M}_{n,t})$
by $\mathbf{w}^{\eta_{i}}=(w^{\eta_{i}}_{1},\ldots,w^{\eta_{i}}_{N})^{T}$. We
apply Lemma 5.6 to each $\eta_{i}$, using the fact that
$\tau^{|R_{1}|+|C_{1}|+\cdots+|R_{k}|+|C_{k}|}(i)=i$ and noting that
$1^{\prime}=i$, to obtain:

$\sum_{j=1}^{N}w^{\eta_{i}}_{j}=v^{\eta_{i}}_{i}-v^{\eta_{i}}_{\tau^{|R_{1}|}(i)}+v^{\eta_{i}}_{\tau^{|R_{1}|+|C_{1}|}(i)}-\cdots-v^{\eta_{i}}_{\tau^{|R_{1}|+|C_{1}|+|R_{2}|+\cdots+|R_{k}|}(i)}.$

We saw in Proposition 3.14 that the odd cycles $\\{\eta_{i}\\}_{i=1}^{t}$ are
divided into 3 sets depending on whether $t<n-t,\,n-t<t,$ or $n-t=t$, with the
cycles in each set sharing similar permutation rules. Recall we can write
$n=ut+r$ for some $u\in\mathbb{N}$ and $r\in\llbracket 0,t-1\rrbracket$. Below
we look at the cycles in each of these 3 main sets, further dividing one of
these sets into 2 subsets based on the value of $r$:

    1. (a)

$n-t=t$: For all $i\in\llbracket 1,t\rrbracket$ we have
$\eta_{i}=(R_{1},\,C_{1})$, where $|R_{1}|=2$. Therefore,
$\sum_{j=1}^{N}w^{\eta_{i}}_{j}=v^{\eta_{i}}_{i}-v^{\eta_{i}}_{\tau^{2}(i)}=v_{i}-v_{i}=0$.

    2. (b)

$t<n-t$ we split into further subsets:

      1. (i)

$r=0$: For all $i\in\llbracket 1,t\rrbracket$ we have $\eta_{i}=(R_{1},C_{1})$
where $|R_{1}|=u$. Therefore,

$\sum_{j=1}^{N}w^{\eta_{i}}_{j}=v^{\eta_{i}}_{i}-v^{\eta_{i}}_{\tau^{u}(i)}=\begin{cases}0&\text{
if $u$ is even};\\\ 2v_{i}&\text{ if $u$ is odd}.\end{cases}$

If $u$ is even then $n=ut+r=2m^{\prime}t$, for some
$m^{\prime}\in\mathbb{N}_{>0}$, hence $n=2m$ and $t|m$. If $u$ is odd then
$n=(2m^{\prime}+1)t$ is odd when $t$ is odd; otherwise $n$ is even with $n=2m$
and $t\nmid m$. We therefore obtain:

$\left|\sum_{j=1}^{N}w^{\eta_{i}}_{j}\right|=\begin{cases}0&\text{ if
}n=2m\text{ and }t|m;\\\ 2&\text{ otherwise.}\end{cases}$

      2. (ii)

$r\in\llbracket 1,t-1\rrbracket$: For all $i\in\llbracket 1,t\rrbracket$ we
have $\eta_{i}=(R_{1},C_{1})$, where $|R_{1}|=u+1$ for all $i\in\llbracket
1,r\rrbracket$, and $|R_{1}|=u$ for all $i\in\llbracket r+1,t\rrbracket$.
Therefore, if $u$ is odd we obtain

$\displaystyle\sum_{j=1}^{N}w^{\eta_{i}}_{j}$
$\displaystyle{}=\begin{cases}v^{\eta_{i}}_{i}-v^{\eta_{i}}_{\tau^{u+1}(i)}=0&\text{
for all }i\in\llbracket 1,r\rrbracket;\\\
v^{\eta_{i}}_{i}-v^{\eta_{i}}_{\tau^{u}(i)}=2v_{i}&\text{ for all
}i\in\llbracket r+1,t\rrbracket,\end{cases}$

and if $u$ is even we obtain

$\displaystyle\sum_{j=1}^{N}w^{\eta_{i}}_{j}$
$\displaystyle{}=\begin{cases}v^{\eta_{i}}_{i}-v^{\eta_{i}}_{\tau^{u+1}(i)}=2v_{i}&\text{
for all }i\in\llbracket 1,r\rrbracket;\\\
v^{\eta_{i}}_{i}-v^{\eta_{i}}_{\tau^{u}(i)}=0&\text{ for all }i\in\llbracket
r+1,t\rrbracket.\end{cases}$

Since $r\in\llbracket 1,t-1\rrbracket$ then both of the sets $\llbracket
1,r\rrbracket$ and $\llbracket r+1,t\rrbracket$ are nonempty, therefore, for
any $n$ there exist $i,k\in\llbracket 1,t\rrbracket$ such that
$\left|\sum_{j=1}^{N}w^{\eta_{i}}_{j}\right|=0$ and
$\left|\sum_{j=1}^{N}w^{\eta_{k}}_{j}\right|=2$.

    3. (c)

$0<n-t<t$: For all $i\in\llbracket 1,t\rrbracket$ we have
$\eta_{i}=(R_{1},C_{1})$ where $|R_{1}|=2$ if $i\in\llbracket 1,r\rrbracket$
and $|R_{1}|=1$ if $i\in\llbracket r+1,t\rrbracket$. Therefore,

$\sum_{j=1}^{N}w^{\eta_{i}}_{j}=\begin{cases}v^{\eta_{i}}_{i}-v^{\eta_{i}}_{\tau^{2}(i)}=0&\text{
for all }i\in\llbracket 1,r\rrbracket;\\\
v^{\eta_{i}}_{i}-v^{\eta_{i}}_{\tau(i)}=2v_{i}&\text{ for all }i\in\llbracket
r+1,t\rrbracket,\end{cases}.$

If $r=0$ then the above sum takes only one value, $2v_{i}$, for all
$i\in\llbracket 1,t\rrbracket$. Therefore, for any $n$ there exists
$i\in\llbracket 1,t\rrbracket$ such that
$\left|\sum_{j=1}^{N}w^{\eta_{i}}_{j}\right|=2$.

If $n=2m$ with $t|m$ then we are in cases 1a and 1(b)i for $u$ even. Both of
these have $\left|\sum_{j=1}^{N}w^{\eta_{i}}_{j}\right|=0$ for all
$i\in\llbracket 1,t\rrbracket$, hence we have
$\ker(\mathcal{M}_{n,t})\subseteq\mathbf{1}^{\bot}$ and
$h_{s_{t}+1}(\mathcal{M}_{n,t}^{E})=0$.

If $n$ is odd, or $n=2m$ and $t\nmid m$, then we are in cases 1(b)i for $u$
odd, 1(b)ii, and 1c. In each of these cases we have at least one cycle
$\eta_{i}$ with $\left|\sum_{j=1}^{N}w^{\eta_{i}}_{j}\right|=2$ and no odd
cycles with an absolute sum greater than this. Therefore we conclude that
$\ker(\mathcal{M}_{n,t})\nsubseteq\mathbf{1}^{\bot}$ and
$\ker(\mathcal{M}_{n,t})\subseteq\mathbf{1}^{\bot}\mod 2$, hence
$h_{s_{t}+1}(\mathcal{M}_{n,t}^{E})\neq 0$. This proves part 1.

  2. 2.

Using [Tho79, Theorem 5] to obtain
$h_{i}(\mathcal{M}_{n,t}^{E})|h_{i}(\mathcal{M}_{n,t})$, for all
$i\in\llbracket 1,s_{t}\rrbracket$, it is clear that for all $t\in\llbracket
1,n-1\rrbracket$ and $i\in\llbracket 1,s_{t}\rrbracket$,
$h_{i}(\mathcal{M}_{n,t}^{E})$ is a power of 2. The question is therefore
regarding the value of $h_{s_{t}+1}(\mathcal{M}_{n,t}^{E})$.

When $n=2m$ with $t|m$ we see by part 1 of this lemma that
$h_{s_{t}+1}(\mathcal{M}_{n,t}^{E})=0$. Therefore the statement is true for
this case. When $n$ is not of this form, we note from part 1 of this lemma
that $\ker(\mathcal{M}_{n,t})\subseteq\mathbf{1}^{\bot}\mod 2$ and
$\ker(\mathcal{M}_{n,t})\nsubseteq\mathbf{1}^{\bot}\mod p$ for any $p>2$.
Therefore, the only prime dividing $h_{s_{t+1}}(\mathcal{M}_{n,t}^{E})$ is 2
by Proposition 5.5. This completes the proof of part 2.

  3. 3.

This result follows immediately from Lemma 5.2, parts 1 and 2 of this lemma,
and Theorem 3.13.

∎

###  5.4 PI degree of quantum affine spaces associated to the extended matrix
of a diagram matrix and application to quantum Schubert varieties

We are now in position to compute the PI degree of a quantum affine space
associated to the extended matrix of a Young diagram matrix. This allows the
computation of the PI degree of an arbitrary quantum Schubert variety.

######  Theorem 5.10.

Let $D$ be a diagram on the Young tableau $Y_{\lambda}$ with
$n=\lambda_{1}\geq\dots\geq\lambda_{m}>0$. Denote by $N$ the number of white
boxes, by $M=M(D)$ its associated matrix, and by $M^{E}$ the extended matrix.
Suppose $\tau$ has $r$ odd cycles and $M$ has $s=(N-r)/2$ nonzero invariant
factors. Let $q$ be a primitive $\ell^{\mathrm{th}}$ root of unity with $\ell$
odd and $\ell_{0}$ the smallest prime factor of $\ell$. Then the PI degree of
the quantum affine space associated to $M^{E}$ is

${\rm PI}\text{-}{\rm
deg}\left(\mathcal{O}_{q^{M^{E}}}\left(\mathbb{K}^{N+1}\right)\right)=\begin{cases}\ell^{\frac{N-r}{2}}&\text{
if $\ker(M)\subseteq\mathbf{1}^{\bot}$};\\\ \ell^{\frac{N-r}{2}+1}&\text{ if
$\ker(M)\nsubseteq\mathbf{1}^{\bot}$ and $\ell_{0}>\min(m,n)$};\\\
\ell^{\frac{N-r}{2}}\cdot\frac{\ell}{\gcd(h_{s+1}(M^{E}),\ell)}&\text{ if
$\ker(M)\nsubseteq\mathbf{1}^{\bot}$ and $\ell_{0}\leq\min(m,n)$}.\end{cases}$

###### Proof.

This easily follows from Lemma 3.1, Proposition 5.3 and Proposition 5.7.

∎

######  Example 5.11.

For the diagram of Example 5.8, we get the following for the PI degree of
$\mathcal{O}_{q^{M^{E}}}\left(\mathbb{K}^{N+1}\right)$:

${\rm PI}\text{-}{\rm
deg}\left(\mathcal{O}_{q^{M^{E}}}\left(\mathbb{K}^{N+1}\right)\right)=\begin{cases}\ell^{3}&\text{
if }\mathrm{gcd}(\ell,3)=1;\\\ \ell^{3}/3&\text{ if $3$ divides
$\ell$}.\end{cases}$

######  Corollary 5.12.

Let $q$ be a primitive $\ell^{\mathrm{th}}$ root of unity such that the
smallest prime factor $\ell_{0}$ of $\ell$ satisfies
$\ell_{0}>\min\\{m,n,2\\}$.

Let $\gamma=[\gamma_{1}<\dots<\gamma_{m}]$ be a quantum Plücker coordinate of
$\mathcal{O}_{q}(G_{m,n}(\mathbb{K}))$ and let $\lambda$ be the partition
associated to $\gamma$. We denote by $N$ the number of boxes in $Y_{\lambda}$
and by $r$ the number of odd cycles for the toric permutation associated to
$Y_{\lambda}$ (with all boxes being white).

Then the PI degree of the quantum Schubert variety
$\mathcal{O}_{q}(G_{m,n}(\mathbb{K}))_{\gamma}$ is given by

${\rm PI}\text{-}{\rm
deg}\left(\mathcal{O}_{q}(G_{m,n}(\mathbb{K}))_{\gamma}\right)=\begin{cases}\ell^{\frac{N-r}{2}}&\text{
if $\ker(M_{\lambda})\subseteq\mathbf{1}^{\bot}$};\\\
\ell^{\frac{N-r}{2}+1}&\text{ if
$\ker(M_{\lambda})\nsubseteq\mathbf{1}^{\bot}$}.\end{cases}$

It would be interesting to characterise when
$\ker(M_{\lambda})\subseteq\mathbf{1}^{\bot}$ via $\gamma$ or $\lambda$.
Theorem 5.13 in the following subsection suggests that this might be an
interesting question.

###  5.5 PI degree of quantum Grassmannians

We conclude this article with a computation of the PI degree of any quantum
Grassmannian. The dimension of the kernel of the relevant skew-symmetric
integral matrix was computed in [LL07, Proposition 2.4]. To prove the
following theorem, we will just need to prove that the kernel of that matrix
is contained in $\mathbf{1}^{\bot}$ exactly when this kernel is trivial.

If $i$ is a positive integer greater than or equal to $2$, we denote by
$\mu_{2}(i)$ the 2-adic valuation of $i$; that is, the largest integer $j$
such that $2^{j}$ divides $i$.

######  Theorem 5.13.

Let $q$ be a primitive $\ell^{\mathrm{th}}$ root of unity such that the
smallest prime factor $\ell_{0}$ of $\ell$ satisfies
$\ell_{0}>\min\\{m,n,2\\}$.

Then the PI degree of the quantum Schubert variety
$\mathcal{O}_{q}(G_{m,n}(\mathbb{K}))$ is given by

${\rm PI}\text{-}{\rm
deg}\left(\mathcal{O}_{q}(G_{m,n}(\mathbb{K}))\right)=\begin{cases}\ell^{\frac{m(n-m)}{2}}&\text{
if }\mu_{2}(m)\neq\mu_{2}(n);\\\ \ell^{\frac{m(n-m)-\gcd(m,n)}{2}+1}&\text{
otherwise}.\end{cases}$

###### Proof.

Given a positive integer $\eta$, we let $B_{\eta}$ denote the $\eta\times\eta$
skew-symmetric matrix with $1$’s in every entry above the diagonal. Given
positive integers $\mu,\eta$ with $\mu\leq\eta$, we let $U_{\eta,\mu}$ denote
the $\eta\times\mu$ matrix given by $(I_{\mu}~{}|~{}{\bf
0}_{\mu\times(\eta-\mu)})^{T}$. Finally, let ${\bf 1}_{\eta}$ denote the
$\eta\times 1$ column vector whose entries are all $1$. Let
$\lambda_{1}\geq\cdots\geq\lambda_{s}\geq 1$ with $\sum\lambda_{i}=N$. Then
the matrix $M_{\lambda}$ can be expressed as a block $s\times s$ matrix in
which the $(i,j)$-block is $U_{\lambda_{i},\lambda_{j}}$ if $i<j$;
$-U_{\lambda_{j},\lambda_{i}}^{T}$ if $i>j$; and $B_{\lambda_{i}}$ if $i=j$.
Let $v_{i}\in\mathbb{C}^{\lambda_{i}\times 1}$ and suppose that

${\bf v}=(v_{1}~{}|~{}v_{2}~{}|~{}\cdots~{}|~{}v_{s})^{T}$

is in the kernel of $M_{\lambda}$. We would like to know when this implies
that ${\bf 1}_{N}^{T}\cdot{\bf v}=0$.

In order to compute the PI degree of $\mathcal{O}_{q}(G_{m,n}(\mathbb{K}))$,
we need to apply Corollary 5.12 in the case when $\gamma=[1\dots m]$ since
$\mathcal{O}_{q}(G_{m,n}(\mathbb{K}))_{[1\dots
m]}=\mathcal{O}_{q}(G_{m,n}(\mathbb{K}))$. In this case, the partition
$\lambda$ is given by $(\lambda_{1}=n-m,\dots,\lambda_{m}=n-m)$.

In this case, we set $B:=B_{n-m}$. If we subtract the $i$-th row from our
block matrix $A_{\lambda}$ from the $(i+1)$-row of our block matrix, then we
get $(-I-B)v_{i}+(B-I)v_{i+1}=0$. Since $B$ is skew-symmetric, its eigenvalues
are purely imaginary and so $B-I$ is invertible. Then
$v_{i+1}=(B-I)^{-1}(B+I)v_{i}$ for $i=1,\ldots,m-1$. In particular, if we let
$C:=(B-I)^{-1}(B+I)$, then we see that $v_{j}=C^{j-1}v_{1}$ for
$j=1,\ldots,m$. Now looking at the first row of our block matrix and
multiplying it by ${\bf v}$ and using the fact that ${\bf v}$ is in the
kernel, we see that

$-v_{1}-Cv_{1}-\cdots-C^{m-2}v_{1}+BC^{m-1}v_{1}=0.$ (30)

Notice that the eigenvalues of $C$ are of the form $(\beta+1)/(\beta-1)$ with
$\beta$ a purely imaginary number and since $C$ and $B$ commute, we see that
$v_{1}=0$ unless $0$ is an eigenvalue of $-I-C-\cdots-C^{m-2}+BC^{m-1}$.
Notice that $B$ and $C$ commute and are simultaneously diagonalizable (since
$B$ is skew-symmetric). If $\gamma=(\beta+1)/(\beta-1)$ is an eigenvalue of
$C$ then the corresponding eigenvalue, $\beta$, of $B$ is
$(\gamma+1)/(\gamma-1)$. So the eigenvalues of
$X:=-I-C-\cdots-C^{n-2}+BC^{n-1}$ are of the form
$-(\gamma^{m-1}-1)/(\gamma-1)+\gamma^{m-1}(\gamma+1)/(\gamma-1)$. If $X$ has a
zero eigenvalue then since $\gamma\neq 0$ we must have

$-(\gamma^{n-1}-1)+\gamma^{n-1}(\gamma+1)=0,$

or equivalently

$1+\gamma^{m}=0.$

Thus $\gamma=\exp(\pi ij/m)$ for some odd $j$. Thus the kernel of
$A_{\lambda}$ in this case is spanned by the vectors of the form ${\bf
v}=(v~{}|~{}Cv~{}|~{}\cdots~{}|C^{m-1}v)^{T}$ with $v$ an eigenvector of $B$
with eigenvalue $\gamma$ with $\gamma^{m}=1$. It is easily checked that the
eigenspace (if such an eigenvector exists) associated with $\gamma$ is one-
dimensional and spanned by $(1,\gamma,\ldots,\gamma^{n-m-1})^{T}$, and that
this occurs only if $\gamma^{n-m}=-1$. In other words $(\gamma-1)^{2}{\bf
1}_{mn}^{T}\cdot{\bf v}=(\gamma^{n}-1)(\gamma^{m}-1)=4$. In other words, the
kernel is contained in the orthogonal complement of ${\bf 1}_{mn}^{T}$ if and
only if the kernel of $M_{(n-m,\dots,n-m)}$ is zero.

Now, by [LL07, Proposition 2.4], the kernel is zero if and only if
$\mu_{2}(m)\neq\mu_{2}(n)$, and in the case where $\mu_{2}(m)=\mu_{2}(n)$, the
kernel of $M_{(n-m,\dots,n-m)}$ has dimension $\gcd(m,n)$. We conclude thanks
to Corollary 5.12.

∎

## References

  * [BCL12] J. P. Bell, K. Casteels, and S. Launois.  Enumeration of $\mathcal{H}$-strata in quantum matrices with respect to dimension.  Journal of Combinatorial Theory. Series A, 119(1):83–98, 2012.
  * [BL10] J. P. Bell and S. Launois.  On the dimension of $H$-strata in quantum algebras.  Algebra & Number Theory, 4(2):175–200, 2010.
  * [BLL10] J. P. Bell, S. Launois, and J. Lutley.  An automaton-theoretic approach to the representation theory of quantum algebras.  Advances in Mathematics, 223(2):476–510, 2010.
  * [BG02] K. A. Brown and K. R. Goodearl.  Lectures on algebraic quantum groups.  Advanced Courses in Mathematics. CRM Barcelona. Birkhäuser Verlag, Basel, 2002.
  * [BY18] K.A. Brown and M.T. Yakimov.  Azumaya loci and discriminant ideals of PI algebras.  Adv. Math., 340:1219–1255, 2018.
  * [Cau03] G. Cauchon.  Spectre premier de $O_{q}(M_{n}(k))$: image canonique et séparation normale.  Journal of Algebra, 260(2):519–569, 2003.
  * [CP93] C. De Concini and C. Procesi.  Quantum groups.  In $D$-modules, representation theory, and quantum groups (Venice, 1992), volume 1565 of Lecture Notes in Math., pages 31–140. Springer, Berlin, 1993.
  * [CPWZ15] S. Ceken, J. H. Palmieri, Y.-H. Wang, and J. J. Zhang.  The discriminant controls automorphism groups of noncommutative algebras.  Advances in Mathematics, 269:551–584, 2015.
  * [CPWZ16] S. Ceken, J. H. Palmieri, Y.-H. Wang, and J. J. Zhang.  The discriminant criterion and automorphism groups of quantized algebras.  Advances in Mathematics, 286:754–801, 2016.
  * [Goo06] K. R. Goodearl.  Commutation relations for arbitrary quantum minors.  Pacific Journal of Mathematics, 228(1):63–102, 2006.
  * [GLL18] K R Goodearl, S Launois, and T H Lenagan.  Tauvel’s height formula for quantum nilpotent algebras.  Communications in Algebra, 47(10): 4194–4209, 2019.
  * [GL00] K. R. Goodearl and T. H. Lenagan.  Quantum determinantal ideals.  Duke Mathematical Journal, 103(1):165–190, 2000.
  * [GW04] K. R. Goodearl and R. B. Warfield, Jr.  An introduction to noncommutative Noetherian rings, volume 61 of London Mathematical Society Student Texts.  Cambridge University Press, Cambridge, second edition, 2004.
  * [Hay08] H. Haynal.  PI degree parity in $q$-skew polynomial rings.  Journal of Algebra, 319(10):4199–4221, 2008.
  * [JJ01] H. P. Jakobsen and S. Jøndrup.  Quantized Rank R Matrices.  Journal of Algebra, 246:70–96, 2001.
  * [JZ97] H. P. Jakobsen and H. Zhang.  The center of the quantized matrix algebra.  Journal of Algebra,196: 458–474, 1997.
  * [Jon00] S. Jøndrup.  Representations of skew polynomial algebras.  Proceedings of the American Mathematical Society, 128:1301–1305, 2000.
  * [KL00] G. R. Krause and T. H. Lenagan.  Growth of algebras and Gelfand-Kirillov dimension, volume 22 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, revised edition, 2000.
  * [LL07] S. Launois and T. H. Lenagan.  Primitive ideals and automorphisms of quantum matrices.  Algebras and Representation Theory, 10(4): 339–365, 2007.
  * [LLN] S. Launois, T.H. Lenagan and B. Nolan.  Total positivity is a quantum phenomenon: the Grassmannian case.  To appear in Memoirs of The Amercican Mathematical Society.  arXiv:1906.06199
  * [LLR08] S. Launois, T.H. Lenagan and L. Rigal.  Prime ideals in the quantum Grassmannian.  Selecta Mathematica (N.S.), 13(4):697–725, 2008.
  * [LLR] S. Launois, S. A. Lopes and A. Rogers.  A deleting derivations algorithm for quantum nilpotent algebras at roots of unity.  arXiv:2304.02151
  * [LZ98] B. Leclerc and A. Zelevinsky.  Quasicommuting families of quantum Plücker coordinates.  In Kirillov’s seminar on representation theory, volume 181 of Amer. Math. Soc. Transl. Ser. 2, pages 85–108. Amer. Math. Soc., Providence, RI, 1998.
  * [LR06] T. H. Lenagan and L. Rigal.  Quantum graded algebras with a straightening law and the AS-Cohen-Macaulay property for quantum determinantal rings and quantum Grassmannians.  Journal of Algebra, 301(2):670–702, 2006.
  * [LR08] T. H. Lenagan and L. Rigal.  Quantum analogues of Schubert varieties in the Grassmannian.  Glasgow Mathematical Journal, 50(1):55–70, 2008.
  * [LMO88] A. Leroy, J. Matczuk, and J. Okniński.  On the Gel’fand-Kirillov dimension of normal localizations and twisted polynomial rings.  In Perspectives in ring theory (Antwerp, 1987), volume 233 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 205–214. Kluwer Acad. Publ., Dordrecht, 1988.
  * [MR01] J. C. McConnell and J. C. Robson.  Noncommutative Noetherian rings, volume 30 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, revised edition, 2001.  With the cooperation of L. W. Small.
  * [New72] M. Newman.  Integral matrices.  Academic Press, New York-London, 1972.  Pure and Applied Mathematics, Vol. 45.
  * [NYM93] M. Noumi, H. Yamada, and K. Mimachi.  Finite-dimensional representations of the quantum group ${\rm GL}_{q}(n;{\bf C})$ and the zonal spherical functions on ${\rm U}_{q}(n-1)\backslash{\rm U}_{q}(n)$.  Japanese Journal of Mathematics. New Series, 19(1):31–80, 1993\.
  * [Pan94] A. N. Panov.  The skew field of rational functions on ${\rm GL}_{q}(n,K)$.  Functional Analysis and Its Applications, 28(2):134–136, Apr 1994\.
  * [Pan95] A. N. Panov.  Skew fields of twisted rational functions and the skew field of rational functions on ${\rm GL}_{q}(n,K)$.  Algebra i Analiz, 7(1):153–169, 1995.
  * [PW91] B. Parshall and J. P. Wang.  Quantum linear groups.  Memoirs of the American Mathematical Society, 89(439):vi+157, 1991\.
  * [Pos06] A. Postnikov.  Total positivity, Grassmannians, and networks.  arXiv Mathematics e-prints, page math/0609764, Sep 2006.
  * [Rog19] A. Rogers  Representations of Quantum Nilpotent Algebras at Roots of Unity, and Their Completely Prime Quotients.  Doctor of Philosophy (PhD) thesis, University of Kent, 2019.  Available at: https://kar.kent.ac.uk/73049/
  * [Tho79] R. C. Thompson.  Interlacing inequalities for invariant factors.  Linear Algebra and its Applications, 24:1–31, 1979.
  * [Zha96] J. J. Zhang.  On Gel’fand-Kirillov transcendence degree.  Transactions of the American Mathematical Society, 348(7):2867–2899, 1996.

J.P. Bell
Department of Pure Mathematics
University of Waterloo
Waterloo, ON, N2L 3G1
Canada
email<EMAIL_ADDRESS>

S. Launois
School of Mathematics, Statistics and Actuarial Science,
University of Kent
Canterbury, Kent, CT2 7FS,
UK
email<EMAIL_ADDRESS>

A. Rogers
email<EMAIL_ADDRESS>