text:
# Web chat using Strophe and Apache Vysper

I was told about Apache Vysper by a colleague at work and thought I’d give it a try. It is very much in development, lacks documentation, and clustering support for those looking to scale.

I’ll replace Openfire in the web chat setup I did in Web chat using Strophe and Openfire. You’ll need a more feature-rich client than trophyim to be able to add users to the roster and such. I used Jitsi.

## Setup Vysper

Grab a copy of Vysper version 0.7. Extract it to any folder. You’ll need a JVM to run the server. Let us configure a few things by editing file spring-config.xml located in the config folder.

Locate the following lines and change the domain name - your machine name should do fine or localhost

<!-- TODO change domain name to your domain -->
<constructor-arg value="localhost"/>

Locate the following lines and change the admin user domain and password. Add more users if you wish.

<bean id="addUsers" class="org.apache.vysper.spring.AddUserHelper">
<constructor-arg index="0">
<map>
<entry key="friend@localhost" value="passw0rd" />

Uncomment the following line - thus enabling BOSH

<ref bean="boshEndpoint"/>

Uncomment the BOSH endpoint configuration

<bean id="boshEndpoint" class="org.apache.vysper.xmpp.extension.xep0124.BoshEndpoint">
<property name="accessControlAllowOrigin">
<list><value>*</value></list>
</property>
<property name="port" value="8080" />
<property name="contextPath" value="/bosh" />
</bean>

## Start Vysper

Head to the command line and execute run.bat or run.sh from the bin folder. If all goes well, you should be able to access http://localhost:8080/bosh/ from the browser.

## Execute trophyim

You’ll need to change the variable TROPHYIM_BOSH_SERVICE in trophyim.js file. Assign it the value http://localhost:8080/bosh/. Launch trophyim by opening index.html in the browser using the file:// url scheme. You can use a client like Jitsi to setup contacts, and try chatting with them using trophyim.

We do not require an HTTP server and proxy. I suspect Vysper supports CORS out of the box. That is good news indeed.


text:
41 questions linked to/from Famous statistical quotations
169 views

### What really happens when we transform the data using $f(x) = \sin(\sqrt{x})$?

I need to perform a two-way ANOVA on my data ($Y$: sleeping hours). My data is quite normal $p$-value = $0.07$ with Shapiro-Wilk test but when I run the normality test for my residual, $p$-value is ...
1k views

### Comparing patient and control group results of a survey

I have data from a survey given to a patient group and control group. Both groups completed the same exact survey (Likert scale). One group has an n of only 5 or 6, the other n was about 15. What ...
561 views

### Using MLE to determine parameters for QQ plot

I just started playing around with a credit fraud dataset that I found online. I noticed that one of the variables looked something like this: Hey, that looks like a 3 parameter log-normal ...
8k views

### Why do my p-values differ between logistic regression output, chi-squared test, and the confidence interval for the OR?

I have built a logistic regression where the outcome variable is being cured after receiving treatment (Cure vs. No Cure). All ...
2k views

139 views

### If my normality test is non-significant, am I safe to use the t-test?

I took a 30 unit sample from a population. The sample distribution resulted to be normal. Can I state that the population distribution is normal too? If so, with what level of confidence?
1k views

### Intuition for Gamma-Poisson / Negative Binomial

I have a data set which intuitively seems Poisson-like, but it's overdispered. So I'm investigating negative binomial. From this question and this page I understand one way of viewing this is to ...
88 views

### how to choose a transformation for left heavy tailed data due to arbitrary upper limit imposed by experimenter?

I have two vectors that look like this: I would like to make a significance test on the paired differences between the two vectors, as well as measure association. The process of data generation is "...
91 views

### Hypothesis test of mean between groups with dependencies and pairing

I have two groups with small number of n (less than 10) where some observations are replicates for each other, some are paired difference observations, and some are completely independent. For example:...

format: plain


text:
Article Search
닫기

## Original Article

Split Viewer

International Journal of Fuzzy Logic and Intelligent Systems 2021; 21(3): 213-221

Published online September 25, 2021

https://doi.org/10.5391/IJFIS.2021.21.3.213

© The Korean Institute of Intelligent Systems

## Post Triangular Rewiring Method for Shorter RRT Robot Path Planning

Jin-Gu Kang and Jin-Woo Jung

Department of Computer Science and Engineering, Dongguk University, Seoul, Korea

Correspondence to :
Jin-Woo Jung (jwjung@dongguk.edu)

Received: July 2, 2021; Revised: July 2, 2021; Accepted: September 9, 2021

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

This paper proposed the “post triangular rewiring” method that minimizes the sacrifice of planning time and overcomes the limit of optimality of sampling-based algorithms such as the rapidly exploring random tree (RRT) algorithm. The proposed “post triangular rewiring” method creates a path closer to the optimal path than the RRT algorithm before application, using the triangular inequality principle. Experiments were conducted to verify the performance of the proposed method. When the proposed method is applied to the RRT algorithm, the optimality efficiency increases compared to the planning time.

Keywords: Robot path planning, RRT, Rewiring, Triangular inequality

Path planning [13] creates or plans a path for a mobile robot to efficiently move from a starting point to a destination point in Euclidean space, avoiding obstacles, with optimality, clearance, and completeness. Optimality implies always ensuring the planning of a path with the optimal path length. Clearance indicates how low the probability of collision between obstacles and the mobile robot is. Completeness indicates whether a path can always be planned in the presence of a solution (that is, whether a path can be created from the starting point to the destination point without colliding with obstacles).

This paper proposed a treatment method for a sampling-based rapidly exploring random tree (RRT) algorithm [4] that does not guarantee optimality. The RRT algorithm can be summarized as a method of planning a path by repeating the act of inserting a randomly sampled position as a child node in a tree with the starting point as the root node until the destination point is reached. With this algorithm, the tree extends in the shape of a stochastic fractal and has a process of determining the destination point.

The sampling-based algorithms [510], including the RRT algorithm, have the advantage of being able to plan a path in less time with less computation than the classical path planning algorithms, such as visibility graph-based [11], cell decomposition-based [12], and potential field-based [13] algorithms. However, they do not guarantee optimality, and have the disadvantage that completeness is guaranteed probabilistically. The latter is also called probabilistic completeness [14], which implies that completeness is guaranteed when the number of random samples is infinite, but may not be guaranteed when the number of random samples is finite. The purpose of this study is to analyze the path planning of the RRT algorithm, which guarantees completeness and shows performance closer to optimality than related works.

The proposed “post triangular rewiring” method is effective in path planning algorithms that do not guarantee optimality, such as the RRT algorithm, and show locally piecewise linear shape and can be applied as a post-processing method after a path is planned using such an algorithm.

Indeed, because the proposed method has the greatest advantage of the sampling-based path planning algorithm, that is, the fast planning speed owing to the small amount of computation compared to the classical path planning algorithms [5], the amount of computation added by the proposed method should not be large compared to that of the RRT algorithm.

The performance of the proposed method was verified through mathematical modeling. The planning time and path length of the first complete path (the path that first reaches a destination point from a starting point) were compared and analyzed through simulation when the method proposed in various environments was applied to the RRT algorithm and related works and when the method was not applied.

### 2. Rapidly Exploring Random Tree

The RRT algorithm is a representative algorithm of the sampling-based path planning algorithm proposed by LaValle in 1998 [4]. It is useful for planning a path considering the conditions of non-holonomic constraints and is designed to have high degrees of freedom.

When a random sample is generated in the configuration space, as shown in Figure 1, the nearest node to the position of the random sample is determined among the nodes constituting the tree with the starting point as the root node. A new node is created at a position away from the node by a step length in the direction of the random sample position and inserted into the tree. If the random sample position is closer than the step length, a new node is created at the random sample position and inserted into the tree. This tree extension process is repeated until the destination point is reached.

### 3. Proposed Post Triangular Rewiring Method

The proposed “post triangular rewiring” method can be applied to path planning algorithms that do not guarantee optimality, such as RRT, and rewired based on the triangular inequality principle [6].

It is a post-processing method that is applied after a path is planned using such an algorithm. As shown in Figure 2(a), when there is no obstacle between the current focusing node and its grandparent node (collision-free), a shorter path can be created based on the triangular inequality, as shown in Figure 2(b). The focusing node and the grandparent node of the node are connected as a parent node and rewired, such as deleting the parent node. Therefore, when the proposed post triangular rewiring method is applied, it is possible to modify the path closer to the optimum than the original path of the RRT algorithm.

Figures 3(a) and 3(b) illustrate an example of rewiring [6], which can be expressed as Eq. (1).

$qancestor=ξ (qparent)=ξ2 (qchild).$

Here, ξ() represents a function that receives the node as a variable and returns the parent node of that node. The n-squared (n ≥ 0) of the ξ() function can be expressed as $ξn(qi)=(ξ∘ξ∘⋯∘ξ︷ )n (qi)$, and if n is 0, ξ0 (qi) = qi holds. That is, mF (qi, k) (k > 0) becomes the midpoint between mF (qi, k − 1) and ξ(qi). At this time, d is (dk − 1)/2.

In addition, by substituting into the triangular inequality in (1), it can be expressed as shown in Figure 3(c) and Equation (2).

$α+β≥γ.$

Equation (3) provides the distance relation between ancestor nodes based on qchild.

$D (qchild,ξ (qchild))+D (ξ (qchild), ξ2 (qchild))≥D (qchild,ξ2 (qchild)).$

Equation (3) is the distance D() expressed in (1) between the n-th ancestor nodes based on qchild in (2), which represents the distance between each node as a triangular inequality, and then substituted. Here, D() represents the distance between two points, that is, Equations (1)(3) locally show that the path becomes shorter when rewired.

Algorithms 1 and 2 present the pseudocode of the proposed post triangular rewiring method.

The input value of the post triangular rewiring method includes path R planned using the path planning algorithm, such as the RRT algorithm, obstacle area information C, and threshold value ɛ of the minimum clearance.

fmodify is a variable that determines whether input path R has been modified by this method, and if the path is modified even once, the entire process is repeated. If path modification does not occur in the repeated process, the algorithm is terminated. t refers to the index of the waypoint of R, which is currently the focus. If t is 0, it indicates the starting point, which is the first point of R.

In R, when the first focusing point is qchild, its next point is qparent, whose next point is qancestor, it is determined whether the distance between qchild and qancestor is free from obstacle collision (isT rapped() function). If it is free from collisions, it calls rewire(). rewire() connects qchild and qancestor, and the qparent between them is deleted from the path. If R and t are updated owing to rewire(), update qchild (the t-th waypoint of R), qparent, and qancestor accordingly. If qparent is the last point in R, then check fmodify. Otherwise, repeat the above process again for the updated qchild and qancestor.

Here, path modification by rewire() deletes the waypoints and creates a path closer to the optimal path. The input value of rewire() of the post triangular rewiring method includes path R, focusing point index t, and path modification fmodify. Rewiring is performed on the t-th waypoint qchild of R, next point qparent, and next point qancestor of that point. First, the path between qchild and qparent and the path between qparent and qancestor are deleted. Then, the path between qchild and qancestor is inserted. Finally, fmodify returns “true” because the path has been modified.

Figure 4 presents the overall flow chart of the proposed post triangular rewiring method. Here, ξt(qgoal) denotes the t-th next waypoint from the starting point qgoal of path R, and ξt+n(qgoal) denotes the n-th next waypoint in ξt(qgoal). That is, there are n waypoints between ξt(qgoal) and ξt+n(qgoal).

To verify the performance of the proposed post triangular rewiring method, the path between an RRT in various environments through simulation and the RRT algorithm to which the proposed method is applied, path planning results were compared.

The compared performance measures were the average of all trials when each algorithm was repeated 100 times (the sampling position was changed for each trial), path length (pixel), and planning time (ms) of the first complete path (from the starting point to the destination point until the first path is planned).

Figure 8 depicts the four environmental maps used in the experiment. Here, the green circle (S) indicates the starting point, and the purple circle (G) indicates the destination point. A black polygon with a yellow border (blue in the experimental results) represents an obstacle. The size of all environmental maps was 600 × 600 pixels, and the step length was 30 pixels.

In the related works of the path planning algorithm, various environmental maps were considered and utilized to confirm the performance of the proposed method. It is important to determine the environmental map to use because the efficiency of the performance measures expected during the experiment is slightly different depending on the composition, such as the number, arrangement, or shape of obstacles. In this study, the four environmental maps shown in Figures 58 were used to verify the performance of the proposed method. These maps are a part of the experimental environment proposed by Han and Seo [15] in 2017, and the efficiency of the following characteristics and performance measures is expected for each map.

Map 1 of Figure 5 appears to be an environment that is efficient to verify optimality and completeness, and it is an environment unfavorable to sampling-based path planning algorithms such as the RRT algorithm. Because the probability of determining a solution is low, several samplings are required. Map 2 of Figure 6 is an environment that is efficient to verify the optimality and completeness of the path planning algorithm. Map 3 of Figure 7 is an environment that is efficient to verify the optimality of the path planning algorithm and the planning time because it comprises obstacles (50 squares) that are close to curved. The expensive classical path planning algorithm is unfavorable. Map 4 of Figure 8 is an environment that is efficient to verify the completeness and planning time of the path planning algorithm, and is an environment unfavorable to sampling-based path planning algorithms such as the RRT algorithm. Because the sampling-based path planning algorithm depends on probabilistic completeness, the number of samples and planning time required becomes extremely large and long, respectively, as there are narrow or few entrances in the direction to the destination point.

Table 1 lists the performance of the computer used in the simulation. The simulator used for the simulation [6] was developed based on C# WPF (Microsoft Visual Studio Community 2019 Version 16.1.6 Microsoft .NET Framework Version 4.8.03752), and only a single thread was used for the calculations, except for the visual part. Indeed, there might be differences in the planning time during simulation depending on the computer performance. Therefore, in this study, the planning time was not compared absolutely, but relatively, based on the RRT algorithm.

The experimental results (path length and planning time) were analyzed when the “post triangular rewiring” method was applied to the RRT algorithm, and its path planning results in the four environmental maps were presented in the experimental environment.

In each map, a figure of the path planning (in the case of a single trial) result for each algorithm is shown, and the results of the experiment (when it is repeated) on the performance measures are presented as numerical values in each table (the figure for each algorithm is not the result of repeated trials). As for the repeated trials, there might be a large difference between the performance observed visually and the numerical results shown in the table. The figure illustrated the shape of the planned path for each algorithm. In addition, it was determined whether there was a section in which the piecewise linear shape path was smoothed by the proposed “post triangular rewiring” method.

Figure 5 shows the path planning results for Map 1 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appears to be the shortest.

Table 2 presents the path planning results for Map 1 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 72% (1403/1932) compared to that of the RRT, which was the shortest, and the planning time was similar.

Figure 6 shows the path planning results for Map 2 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appears to be the shortest.

Table 3 presents the path planning results for Map 2 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 82% (799/969) compared to that of the RRT, which was the shortest, and the planning time was similar.

Figure 7 depicts the path planning results for Map 3 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appears to be the shortest.

Table 4 presents the path planning results for Map 3 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 89% (529/591) compared to that of the RRT, which was the shortest, and the planning time was similar.

Figure 8 depicts the path planning results for Map 4 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appeared to be the shortest.

Table 5 presents the path planning results for Map 4 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 85% (1304/1533) compared to that of the RRT, which was the shortest, and the planning time was similar.

Overall, the application of the “post triangular rewiring” method exhibited a good performance in the path length for all maps, indicating that the proposed method is effective in terms of optimality.

In this paper, we proposed a “post triangular rewiring” method that could minimize the sacrifice of planning time and overcome the limitations of the optimization of the sampling derivation algorithm. The proposed “post triangular rewiring” method creates a more optimal path. In addition, as a post-processing method, it has the advantage of being applicable to all path planning algorithms that plan a locally piecewise linear path. Simulations were performed to verify the performance of the RRT algorithm, to which the post triangular rewiring method was applied. It was verified that the path length was shortened by 11–28% (average 18%) when applied to the RRT algorithm in the four different environmental maps. Consequently, the RRT algorithm applying the proposed “post triangular rewiring” method exhibited a more optimal path.

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (No. 2020R1F1A1074974), the Ministry of Trade, Industry and Energy (MOTIE), and Korea Institute for Advancement of Technology (KIAT) through the International Cooperative R&D program (Project No. P0016096) and the Korea Association of University, Research Institute, and Industry (AURI) grant funded by the Korean Government (MSS: Ministry of SMEs and Startups) (No. S3041234, HRD program for Enterprise linkages R&D) and the Ministry of Science and ICT (MSIT), Korea, under the Information Technology Research Center (ITRC) support program (No. IITP-2021-2020-0-01789) supervised by the Institute for Information & Communications Technology Planning & Evaluation (IITP).

Fig. 1.

Process of the RRT algorithm: In the case of creating new node qnew at a position separated by step length λ in the direction of the random sample position(qrand) based on the qnear node (position) nearest to the random sample position (qrand) in tree T with starting point qstart as the root node.

Fig. 2.

Summary of the post triangular rewiring method: (a) When line segment γ with node q0 and its grandparent node q2 in tree R is free from obstacle collision (Distance: γ < α+ β), (b) Grandparent node q2 of node q0 is connected as the parent node of node q0, and parent node q1 is deleted from the tree.

Fig. 3.

(a) Part of a tree consisting of node qchild, its parent node qparent, and node qancestor, the parent node of qparent. (b) If there is no obstacle between qchild and qancestor, delete the edge connecting to qparent in each node. (c) Edge α connecting qchild and qparent, edge β connecting qparent and qancestor, and edge γ connecting qchild and qancestor.

Fig. 4.

Flow chart of the proposed post triangular rewiring method.

Fig. 5.

Experimental results of Map 1: (a) RRT and (b) proposed.

Fig. 6.

Experimental results of Map 2: (a) RRT and (b) proposed.

Fig. 7.

Experimental results of Map 3: (a) RRT and (b) proposed.

Fig. 8.

Experimental results of Map 4: (a) RRT and (b) proposed.

Table. 1.

Table 1. Computer performance for simulation.

H/WSpecification
CPUIntel Core i7-6700K 4.00 GHz (8 CPUs)
RAM32768 MB (32 GB DDR4)

Table. 2.

Table 2. Experimental results of Map 1.

PerformanceRRTProposal
Path length (pixel)1932 (100%)1403 (72%)
Planning time (ms)687 (100%)688 (100%)

The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..

Table. 3.

Table 3. Experimental results of Map 2.

PerformanceRRTProposal
Path length (pixel)969 (100%)799 (82%)
Planning time (ms)10 (100%)11 (100%)

The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..

Table. 4.

Table 4. Experimental results of Map 3.

PerformanceRRTProposal
Path length (pixel)591 (100%)529 (89%)
Planning time (ms)6 (100%)7 (100%)

The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..

Table. 5.

Table 5. Experimental results of Map 4.

PerformanceRRTProposal
Path length (pixel)1533 (100%)1304 (85%)
Planning time (ms)1526 (100%)1527 (100%)

The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..

Table. 6.

Algorithm 1. Pseudocode of the proposed “post triangular rewiring” method.

 Input: R ← path from {RRT/...} C ← position set of all (measured) boundary points in all (known) obstacles ɛ ← threshold value of minimum Clearance Output: R ← modified path R Initialize: fmodify ← true ProcedurepostT riangularRewire Begin 1 WhilefmodifyDo 2 fmodify ← false// is the path modified 3 t ← 0 // index of the currently focused point 4 qchild ← first point in R 5 qparent ← next point of qchild in R 6 While not [qparent is last point in R] Do 7 qancestor ← next point of qparent in R 8 If notisT rapped(qchild, qancestor, C) Then 9 R ← rewire(R, ɛ, t, fmodify) 10 Else 11 t ← t + 1 12 qchild ← t-th point in R 13 qparent ← next point of qchild in R End

Table. 7.

Algorithm 2. Pseudocode of the “rewire” function from the proposed method.

 Input: R ← path R from postT riangularRewire t ← point index t from postT riangularRewire fmodify ← boolean fmodify from postT riangularRewire Output: R ← modified path R fmodify ← result of boolean fmodify // return by reference Procedure rewire FrompostT riangularRewire Begin 1 qchild ← t-th point in R 2 qparent ← next point of qchild in R 3 qancestor ← next point of qparent in R 4 R ← Delete path< qchild, qparent > and path< qparent, qancestor > from R 5 R ← Insert path< qchild, qancestor > to R 6 fmodify ← true End

1. Schwab, K (2016). The Fourth Industrial Revolution. Geneva, Switzerland: World Economic Forum
2. Choi, YI, Cho, JH, and Kim, YT (2020). Collision avoidance algorithm of mobile robots at grid map intersection point. International Journal of Fuzzy Logic and Intelligent Systems. 20, 96-104. https://doi.org/10.5391/IJFIS.2020.20.2.96
3. Jung, JH, and Kim, DH (2020). Local path planning of a mobile robot using a novel grid-based potential method. International Journal of Fuzzy Logic and Intelligent Systems. 20, 26-34. https://doi.org/10.5391/IJFIS.2020.20.1.26
4. LaValle, SM, and Kuffner, JJ (2001). Randomized kinodynamic planning. The International Journal of Robotics Research. 20, 378-400. https://doi.org/10.1177/02783640122067453
5. Kuffner, JJ, and LaValle, SM (). RRT-connect: an efficient approach to single-query path planning, 995-1001. https://doi.org/10.1109/ROBOT.2000.844730
6. Kang, JG, Lim, DW, Choi, YS, Jang, WJ, and Jung, JW (). Improved RRT-connect algorithm based on triangular inequality for robot path planning. Sensors. 21, 2021. article no. 333
7. Karaman, S, and Frazzoli, E (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research. 30, 846-894. https://doi.org/10.1177/0278364911406761
8. Gammell, JD, Srinivasa, SS, and Barfoot, TD (). Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic, 2997-3004. https://doi.org/10.1109/IROS.2014.6942976
9. Klemm, S, Oberlander, J, Hermann, A, Roennau, A, Schamm, T, Zollner, JM, and Dillmann, R (). RRT*-Connect: faster, asymptotically optimal motion planning, 1670-1677. https://doi.org/10.1109/ROBIO.2015.7419012
10. Islam, F, Nasir, J, Malik, U, Ayaz, Y, and Hasan, O (). RRT*-Smart: rapid convergence implementation of RRT* towards optimal solution, 1651-1656. https://doi.org/10.1109/ICMA.2012.6284384
11. Roy, D (2019). Visibility graph-based spatial path planning of robots using configuration space algorithms. International Journal of Robotics & Automation. 24. article no. 2853
12. Katevas, NI, Tzafestas, SG, and Pnevmatikatos, CG (1998). The approximate cell decomposition with local node refinement global path planning method: path nodes refinement and curve parametric interpolation. Journal of Intelligent and Robotic Systems. 22, 289-314. https://doi.org/10.1023/A:1008034314006
13. Warren, CW (). Global path planning using artificial potential fields, 316-317. https://doi.org/10.1109/ROBOT.1989.100007
14. LaValle, SM (1998). Rapidly-exploring random trees: A new tool for path planning. Ames, IA: Department of Computer Science, Iowa State University
15. Han, J, and Seo, Y (2017). Mobile robot path planning with surrounding point set and path improvement. Applied Soft Computing. 57, 35-47. https://doi.org/10.1016/j.asoc.2017.03.035

Jin-Gu Kang received the B.S. and LL.B. degrees from Dongguk University at Seoul, Korea in 2019, and received the M.S. degree in Computer Science and Engineering from Dongguk University at Seoul, Korea in 2021. His research areas include robot path planning, wireless MAC protocols and deep learning-based image processing.

E-mail: kanggu12@dongguk.edu

Jin-Woo Jung received the B.S. and M.S. degrees in Electrical Engineering from Korea Advanced Institute of Science and Technology (KAIST), Korea, in 1997 and 1999, respectively and received the Ph.D. degree in Electrical Engineering and Computer Science from KAIST, Korea in 2004. Since 2006, he has been with the Department of Computer Science and Engineering at Dongguk University at Seoul, Korea, where he is currently a professor. His current research interests include human behavior recognition, mobile robot and intelligent human-robot interaction.

E-mail: jwjung@dongguk.edu

### Article

#### Original Article

International Journal of Fuzzy Logic and Intelligent Systems 2021; 21(3): 213-221

Published online September 25, 2021 https://doi.org/10.5391/IJFIS.2021.21.3.213

## Post Triangular Rewiring Method for Shorter RRT Robot Path Planning

Jin-Gu Kang and Jin-Woo Jung

Department of Computer Science and Engineering, Dongguk University, Seoul, Korea

Correspondence to:Jin-Woo Jung (jwjung@dongguk.edu)

Received: July 2, 2021; Revised: July 2, 2021; Accepted: September 9, 2021

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

### Abstract

This paper proposed the “post triangular rewiring” method that minimizes the sacrifice of planning time and overcomes the limit of optimality of sampling-based algorithms such as the rapidly exploring random tree (RRT) algorithm. The proposed “post triangular rewiring” method creates a path closer to the optimal path than the RRT algorithm before application, using the triangular inequality principle. Experiments were conducted to verify the performance of the proposed method. When the proposed method is applied to the RRT algorithm, the optimality efficiency increases compared to the planning time.

Keywords: Robot path planning, RRT, Rewiring, Triangular inequality

### 1. Introduction

Path planning [13] creates or plans a path for a mobile robot to efficiently move from a starting point to a destination point in Euclidean space, avoiding obstacles, with optimality, clearance, and completeness. Optimality implies always ensuring the planning of a path with the optimal path length. Clearance indicates how low the probability of collision between obstacles and the mobile robot is. Completeness indicates whether a path can always be planned in the presence of a solution (that is, whether a path can be created from the starting point to the destination point without colliding with obstacles).

This paper proposed a treatment method for a sampling-based rapidly exploring random tree (RRT) algorithm [4] that does not guarantee optimality. The RRT algorithm can be summarized as a method of planning a path by repeating the act of inserting a randomly sampled position as a child node in a tree with the starting point as the root node until the destination point is reached. With this algorithm, the tree extends in the shape of a stochastic fractal and has a process of determining the destination point.

The sampling-based algorithms [510], including the RRT algorithm, have the advantage of being able to plan a path in less time with less computation than the classical path planning algorithms, such as visibility graph-based [11], cell decomposition-based [12], and potential field-based [13] algorithms. However, they do not guarantee optimality, and have the disadvantage that completeness is guaranteed probabilistically. The latter is also called probabilistic completeness [14], which implies that completeness is guaranteed when the number of random samples is infinite, but may not be guaranteed when the number of random samples is finite. The purpose of this study is to analyze the path planning of the RRT algorithm, which guarantees completeness and shows performance closer to optimality than related works.

The proposed “post triangular rewiring” method is effective in path planning algorithms that do not guarantee optimality, such as the RRT algorithm, and show locally piecewise linear shape and can be applied as a post-processing method after a path is planned using such an algorithm.

Indeed, because the proposed method has the greatest advantage of the sampling-based path planning algorithm, that is, the fast planning speed owing to the small amount of computation compared to the classical path planning algorithms [5], the amount of computation added by the proposed method should not be large compared to that of the RRT algorithm.

The performance of the proposed method was verified through mathematical modeling. The planning time and path length of the first complete path (the path that first reaches a destination point from a starting point) were compared and analyzed through simulation when the method proposed in various environments was applied to the RRT algorithm and related works and when the method was not applied.

### 2. Rapidly Exploring Random Tree

The RRT algorithm is a representative algorithm of the sampling-based path planning algorithm proposed by LaValle in 1998 [4]. It is useful for planning a path considering the conditions of non-holonomic constraints and is designed to have high degrees of freedom.

When a random sample is generated in the configuration space, as shown in Figure 1, the nearest node to the position of the random sample is determined among the nodes constituting the tree with the starting point as the root node. A new node is created at a position away from the node by a step length in the direction of the random sample position and inserted into the tree. If the random sample position is closer than the step length, a new node is created at the random sample position and inserted into the tree. This tree extension process is repeated until the destination point is reached.

### 3. Proposed Post Triangular Rewiring Method

The proposed “post triangular rewiring” method can be applied to path planning algorithms that do not guarantee optimality, such as RRT, and rewired based on the triangular inequality principle [6].

It is a post-processing method that is applied after a path is planned using such an algorithm. As shown in Figure 2(a), when there is no obstacle between the current focusing node and its grandparent node (collision-free), a shorter path can be created based on the triangular inequality, as shown in Figure 2(b). The focusing node and the grandparent node of the node are connected as a parent node and rewired, such as deleting the parent node. Therefore, when the proposed post triangular rewiring method is applied, it is possible to modify the path closer to the optimum than the original path of the RRT algorithm.

Figures 3(a) and 3(b) illustrate an example of rewiring [6], which can be expressed as Eq. (1).

$qancestor=ξ (qparent)=ξ2 (qchild).$

Here, ξ() represents a function that receives the node as a variable and returns the parent node of that node. The n-squared (n ≥ 0) of the ξ() function can be expressed as $ξn(qi)=(ξ∘ξ∘⋯∘ξ︷ )n (qi)$, and if n is 0, ξ0 (qi) = qi holds. That is, mF (qi, k) (k > 0) becomes the midpoint between mF (qi, k − 1) and ξ(qi). At this time, d is (dk − 1)/2.

In addition, by substituting into the triangular inequality in (1), it can be expressed as shown in Figure 3(c) and Equation (2).

$α+β≥γ.$

Equation (3) provides the distance relation between ancestor nodes based on qchild.

$D (qchild,ξ (qchild))+D (ξ (qchild), ξ2 (qchild))≥D (qchild,ξ2 (qchild)).$

Equation (3) is the distance D() expressed in (1) between the n-th ancestor nodes based on qchild in (2), which represents the distance between each node as a triangular inequality, and then substituted. Here, D() represents the distance between two points, that is, Equations (1)(3) locally show that the path becomes shorter when rewired.

Algorithms 1 and 2 present the pseudocode of the proposed post triangular rewiring method.

The input value of the post triangular rewiring method includes path R planned using the path planning algorithm, such as the RRT algorithm, obstacle area information C, and threshold value ɛ of the minimum clearance.

fmodify is a variable that determines whether input path R has been modified by this method, and if the path is modified even once, the entire process is repeated. If path modification does not occur in the repeated process, the algorithm is terminated. t refers to the index of the waypoint of R, which is currently the focus. If t is 0, it indicates the starting point, which is the first point of R.

In R, when the first focusing point is qchild, its next point is qparent, whose next point is qancestor, it is determined whether the distance between qchild and qancestor is free from obstacle collision (isT rapped() function). If it is free from collisions, it calls rewire(). rewire() connects qchild and qancestor, and the qparent between them is deleted from the path. If R and t are updated owing to rewire(), update qchild (the t-th waypoint of R), qparent, and qancestor accordingly. If qparent is the last point in R, then check fmodify. Otherwise, repeat the above process again for the updated qchild and qancestor.

Here, path modification by rewire() deletes the waypoints and creates a path closer to the optimal path. The input value of rewire() of the post triangular rewiring method includes path R, focusing point index t, and path modification fmodify. Rewiring is performed on the t-th waypoint qchild of R, next point qparent, and next point qancestor of that point. First, the path between qchild and qparent and the path between qparent and qancestor are deleted. Then, the path between qchild and qancestor is inserted. Finally, fmodify returns “true” because the path has been modified.

Figure 4 presents the overall flow chart of the proposed post triangular rewiring method. Here, ξt(qgoal) denotes the t-th next waypoint from the starting point qgoal of path R, and ξt+n(qgoal) denotes the n-th next waypoint in ξt(qgoal). That is, there are n waypoints between ξt(qgoal) and ξt+n(qgoal).

### 4. Experimental Results

To verify the performance of the proposed post triangular rewiring method, the path between an RRT in various environments through simulation and the RRT algorithm to which the proposed method is applied, path planning results were compared.

The compared performance measures were the average of all trials when each algorithm was repeated 100 times (the sampling position was changed for each trial), path length (pixel), and planning time (ms) of the first complete path (from the starting point to the destination point until the first path is planned).

Figure 8 depicts the four environmental maps used in the experiment. Here, the green circle (S) indicates the starting point, and the purple circle (G) indicates the destination point. A black polygon with a yellow border (blue in the experimental results) represents an obstacle. The size of all environmental maps was 600 × 600 pixels, and the step length was 30 pixels.

In the related works of the path planning algorithm, various environmental maps were considered and utilized to confirm the performance of the proposed method. It is important to determine the environmental map to use because the efficiency of the performance measures expected during the experiment is slightly different depending on the composition, such as the number, arrangement, or shape of obstacles. In this study, the four environmental maps shown in Figures 58 were used to verify the performance of the proposed method. These maps are a part of the experimental environment proposed by Han and Seo [15] in 2017, and the efficiency of the following characteristics and performance measures is expected for each map.

Map 1 of Figure 5 appears to be an environment that is efficient to verify optimality and completeness, and it is an environment unfavorable to sampling-based path planning algorithms such as the RRT algorithm. Because the probability of determining a solution is low, several samplings are required. Map 2 of Figure 6 is an environment that is efficient to verify the optimality and completeness of the path planning algorithm. Map 3 of Figure 7 is an environment that is efficient to verify the optimality of the path planning algorithm and the planning time because it comprises obstacles (50 squares) that are close to curved. The expensive classical path planning algorithm is unfavorable. Map 4 of Figure 8 is an environment that is efficient to verify the completeness and planning time of the path planning algorithm, and is an environment unfavorable to sampling-based path planning algorithms such as the RRT algorithm. Because the sampling-based path planning algorithm depends on probabilistic completeness, the number of samples and planning time required becomes extremely large and long, respectively, as there are narrow or few entrances in the direction to the destination point.

Table 1 lists the performance of the computer used in the simulation. The simulator used for the simulation [6] was developed based on C# WPF (Microsoft Visual Studio Community 2019 Version 16.1.6 Microsoft .NET Framework Version 4.8.03752), and only a single thread was used for the calculations, except for the visual part. Indeed, there might be differences in the planning time during simulation depending on the computer performance. Therefore, in this study, the planning time was not compared absolutely, but relatively, based on the RRT algorithm.

The experimental results (path length and planning time) were analyzed when the “post triangular rewiring” method was applied to the RRT algorithm, and its path planning results in the four environmental maps were presented in the experimental environment.

In each map, a figure of the path planning (in the case of a single trial) result for each algorithm is shown, and the results of the experiment (when it is repeated) on the performance measures are presented as numerical values in each table (the figure for each algorithm is not the result of repeated trials). As for the repeated trials, there might be a large difference between the performance observed visually and the numerical results shown in the table. The figure illustrated the shape of the planned path for each algorithm. In addition, it was determined whether there was a section in which the piecewise linear shape path was smoothed by the proposed “post triangular rewiring” method.

Figure 5 shows the path planning results for Map 1 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appears to be the shortest.

Table 2 presents the path planning results for Map 1 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 72% (1403/1932) compared to that of the RRT, which was the shortest, and the planning time was similar.

Figure 6 shows the path planning results for Map 2 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appears to be the shortest.

Table 3 presents the path planning results for Map 2 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 82% (799/969) compared to that of the RRT, which was the shortest, and the planning time was similar.

Figure 7 depicts the path planning results for Map 3 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appears to be the shortest.

Table 4 presents the path planning results for Map 3 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 89% (529/591) compared to that of the RRT, which was the shortest, and the planning time was similar.

Figure 8 depicts the path planning results for Map 4 among the presented environmental maps for each algorithm. Visually, the path of the “post triangular rewiring” method appeared to be the shortest.

Table 5 presents the path planning results for Map 4 (average when repeated 100 times) among the presented environmental maps for each algorithm. The path length after applying the post triangular rewiring method was 85% (1304/1533) compared to that of the RRT, which was the shortest, and the planning time was similar.

Overall, the application of the “post triangular rewiring” method exhibited a good performance in the path length for all maps, indicating that the proposed method is effective in terms of optimality.

### 5. Conclusion

In this paper, we proposed a “post triangular rewiring” method that could minimize the sacrifice of planning time and overcome the limitations of the optimization of the sampling derivation algorithm. The proposed “post triangular rewiring” method creates a more optimal path. In addition, as a post-processing method, it has the advantage of being applicable to all path planning algorithms that plan a locally piecewise linear path. Simulations were performed to verify the performance of the RRT algorithm, to which the post triangular rewiring method was applied. It was verified that the path length was shortened by 11–28% (average 18%) when applied to the RRT algorithm in the four different environmental maps. Consequently, the RRT algorithm applying the proposed “post triangular rewiring” method exhibited a more optimal path.

### Fig 1.

Figure 1.

Process of the RRT algorithm: In the case of creating new node qnew at a position separated by step length λ in the direction of the random sample position(qrand) based on the qnear node (position) nearest to the random sample position (qrand) in tree T with starting point qstart as the root node.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

### Fig 2.

Figure 2.

Summary of the post triangular rewiring method: (a) When line segment γ with node q0 and its grandparent node q2 in tree R is free from obstacle collision (Distance: γ < α+ β), (b) Grandparent node q2 of node q0 is connected as the parent node of node q0, and parent node q1 is deleted from the tree.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

### Fig 3.

Figure 3.

(a) Part of a tree consisting of node qchild, its parent node qparent, and node qancestor, the parent node of qparent. (b) If there is no obstacle between qchild and qancestor, delete the edge connecting to qparent in each node. (c) Edge α connecting qchild and qparent, edge β connecting qparent and qancestor, and edge γ connecting qchild and qancestor.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

### Fig 4.

Figure 4.

Flow chart of the proposed post triangular rewiring method.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

### Fig 5.

Figure 5.

Experimental results of Map 1: (a) RRT and (b) proposed.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

### Fig 6.

Figure 6.

Experimental results of Map 2: (a) RRT and (b) proposed.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

### Fig 7.

Figure 7.

Experimental results of Map 3: (a) RRT and (b) proposed.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

### Fig 8.

Figure 8.

Experimental results of Map 4: (a) RRT and (b) proposed.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 213-221https://doi.org/10.5391/IJFIS.2021.21.3.213

Computer performance for simulation.

H/WSpecification
CPUIntel Core i7-6700K 4.00 GHz (8 CPUs)
RAM32768 MB (32 GB DDR4)

Experimental results of Map 1.

PerformanceRRTProposal
Path length (pixel)1932 (100%)1403 (72%)
Planning time (ms)687 (100%)688 (100%)

The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..

Experimental results of Map 2.

PerformanceRRTProposal
Path length (pixel)969 (100%)799 (82%)
Planning time (ms)10 (100%)11 (100%)

The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..

Experimental results of Map 3.

PerformanceRRTProposal
Path length (pixel)591 (100%)529 (89%)
Planning time (ms)6 (100%)7 (100%)

The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..

Experimental results of Map 4.

PerformanceRRTProposal
Path length (pixel)1533 (100%)1304 (85%)
Planning time (ms)1526 (100%)1527 (100%)

The parentheses on the right of each number (average of repeated 100 times) are relative ratios based on 100% RRT (values less than 1 are counted as 1)..

Algorithm 1. Pseudocode of the proposed “post triangular rewiring” method.

 Input: R ← path from {RRT/...} C ← position set of all (measured) boundary points in all (known) obstacles ɛ ← threshold value of minimum Clearance Output: R ← modified path R Initialize: fmodify ← true ProcedurepostT riangularRewire Begin 1 WhilefmodifyDo 2 fmodify ← false// is the path modified 3 t ← 0 // index of the currently focused point 4 qchild ← first point in R 5 qparent ← next point of qchild in R 6 While not [qparent is last point in R] Do 7 qancestor ← next point of qparent in R 8 If notisT rapped(qchild, qancestor, C) Then 9 R ← rewire(R, ɛ, t, fmodify) 10 Else 11 t ← t + 1 12 qchild ← t-th point in R 13 qparent ← next point of qchild in R End

Algorithm 2. Pseudocode of the “rewire” function from the proposed method.

 Input: R ← path R from postT riangularRewire t ← point index t from postT riangularRewire fmodify ← boolean fmodify from postT riangularRewire Output: R ← modified path R fmodify ← result of boolean fmodify // return by reference Procedure rewire FrompostT riangularRewire Begin 1 qchild ← t-th point in R 2 qparent ← next point of qchild in R 3 qancestor ← next point of qparent in R 4 R ← Delete path< qchild, qparent > and path< qparent, qancestor > from R 5 R ← Insert path< qchild, qancestor > to R 6 fmodify ← true End

### References

1. Schwab, K (2016). The Fourth Industrial Revolution. Geneva, Switzerland: World Economic Forum
2. Choi, YI, Cho, JH, and Kim, YT (2020). Collision avoidance algorithm of mobile robots at grid map intersection point. International Journal of Fuzzy Logic and Intelligent Systems. 20, 96-104. https://doi.org/10.5391/IJFIS.2020.20.2.96
3. Jung, JH, and Kim, DH (2020). Local path planning of a mobile robot using a novel grid-based potential method. International Journal of Fuzzy Logic and Intelligent Systems. 20, 26-34. https://doi.org/10.5391/IJFIS.2020.20.1.26
4. LaValle, SM, and Kuffner, JJ (2001). Randomized kinodynamic planning. The International Journal of Robotics Research. 20, 378-400. https://doi.org/10.1177/02783640122067453
5. Kuffner, JJ, and LaValle, SM (). RRT-connect: an efficient approach to single-query path planning, 995-1001. https://doi.org/10.1109/ROBOT.2000.844730
6. Kang, JG, Lim, DW, Choi, YS, Jang, WJ, and Jung, JW (). Improved RRT-connect algorithm based on triangular inequality for robot path planning. Sensors. 21, 2021. article no. 333
7. Karaman, S, and Frazzoli, E (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research. 30, 846-894. https://doi.org/10.1177/0278364911406761
8. Gammell, JD, Srinivasa, SS, and Barfoot, TD (). Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic, 2997-3004. https://doi.org/10.1109/IROS.2014.6942976
9. Klemm, S, Oberlander, J, Hermann, A, Roennau, A, Schamm, T, Zollner, JM, and Dillmann, R (). RRT*-Connect: faster, asymptotically optimal motion planning, 1670-1677. https://doi.org/10.1109/ROBIO.2015.7419012
10. Islam, F, Nasir, J, Malik, U, Ayaz, Y, and Hasan, O (). RRT*-Smart: rapid convergence implementation of RRT* towards optimal solution, 1651-1656. https://doi.org/10.1109/ICMA.2012.6284384
11. Roy, D (2019). Visibility graph-based spatial path planning of robots using configuration space algorithms. International Journal of Robotics & Automation. 24. article no. 2853
12. Katevas, NI, Tzafestas, SG, and Pnevmatikatos, CG (1998). The approximate cell decomposition with local node refinement global path planning method: path nodes refinement and curve parametric interpolation. Journal of Intelligent and Robotic Systems. 22, 289-314. https://doi.org/10.1023/A:1008034314006
13. Warren, CW (). Global path planning using artificial potential fields, 316-317. https://doi.org/10.1109/ROBOT.1989.100007
14. LaValle, SM (1998). Rapidly-exploring random trees: A new tool for path planning. Ames, IA: Department of Computer Science, Iowa State University
15. Han, J, and Seo, Y (2017). Mobile robot path planning with surrounding point set and path improvement. Applied Soft Computing. 57, 35-47. https://doi.org/10.1016/j.asoc.2017.03.035


text:
## 8.73 (a) [ENDORSED]

Merzia Subhan 1L
Posts: 33
Joined: Thu Jul 13, 2017 3:00 am

### 8.73 (a)

I am having some trouble with 8.73(a). The question is "Use the bond enthalpies in Table 8.6 and 8.7 to estimate the reaction enthalpy for a) 3C2H2 --> C6H6"
I looked up the molecular structure for both molecules. C2H2 has two carbons bonded with a triple bond and hydrogens attached to the other side. The bond enthalpy is 837 kJ. C6H6 is a hexagon of carbons with alternating double and single bonds between the ring, 3 of each, with a hydrogen on each. It seems like 3 triple bonds between two Cs were broken and 3 double bonds (enthalpy is 612kJ) and 3 single bonds (348kJ) are formed. I did 3(847kJ) - 3(612) -3(348) and I got -339kJ which is the wrong answer. the correct answer is -597 kJ/mol. Why is that? What am I doing wrong?

Chem_Mod
Posts: 18400
Joined: Thu Aug 04, 2011 1:53 pm
Has upvoted: 435 times

### Re: 8.73 (a)  [ENDORSED]

Your procedure was correct. The issue is that C6H6 is benzene which has resonance. Therefore, its bonds are better described by the value 518 kJ/mol as written with an asterisk in Table 8.7 (pg. 300) since this specifically refers to mean bond enthalpy for $\textup{C-C} \leftrightarrow \textup{C=C}$ resonance such as found in benzene.

Return to “Reaction Enthalpies (e.g., Using Hess’s Law, Bond Enthalpies, Standard Enthalpies of Formation)”

### Who is online

Users browsing this forum: No registered users and 2 guests


text:
Geometry

Pi

Pi, or $\pi$, is commonly used in the context of circles in geometry. In particular, […]

Pythagoras Theorem

What is the Pythagoras theorem? It is $a^2 + b^2 = c^2$. Here, $a$, […]


text:
## Bernoulli

• Bernoulli
• Volume 24, Number 3 (2018), 2401-2428.

### On the Poisson equation for Metropolis–Hastings chains

#### Abstract

This paper defines an approximation scheme for a solution of the Poisson equation of a geometrically ergodic Metropolis–Hastings chain $\Phi$. The scheme is based on the idea of weak approximation and gives rise to a natural sequence of control variates for the ergodic average $S_{k}(F)=(1/k)\sum_{i=1}^{k}F(\Phi_{i})$, where $F$ is the force function in the Poisson equation. The main results show that the sequence of the asymptotic variances (in the CLTs for the control-variate estimators) converges to zero and give a rate of this convergence. Numerical examples in the case of a double-well potential are discussed.

#### Article information

Source
Bernoulli, Volume 24, Number 3 (2018), 2401-2428.

Dates
Received: August 2016
Revised: October 2016
First available in Project Euclid: 2 February 2018

Permanent link to this document
https://projecteuclid.org/euclid.bj/1517540478

Digital Object Identifier
doi:10.3150/17-BEJ932

Mathematical Reviews number (MathSciNet)
MR3757533

Zentralblatt MATH identifier
06839270

#### Citation

Mijatović, Aleksandar; Vogrinc, Jure. On the Poisson equation for Metropolis–Hastings chains. Bernoulli 24 (2018), no. 3, 2401--2428. doi:10.3150/17-BEJ932. https://projecteuclid.org/euclid.bj/1517540478

#### References

• [1] Andradóttir, S., Heyman, D.P. and Ott, T.J. (1993). Variance reduction through smoothing and control variates for Markov chain simulations. ACM Trans. Model. Comput. Simul. 3 167–189.
• [2] Baxendale, P.H. (2005). Renewal theory and computable convergence rates for geometrically ergodic Markov chains. Ann. Appl. Probab. 15 700–738.
• [3] Dellaportas, P. and Kontoyiannis, I. (2012). Control variates for estimation based on reversible Markov chain Monte Carlo samplers. J. R. Stat. Soc. Ser. B. Stat. Methodol. 74 133–161.
• [4] Devraj, A. and Meyn, S. (2016). Differential TD learning for value function approximation. Available at arXiv:1604.01828v1.
• [5] Geyer, C.J. (1992). Practical Markov chain Monte Carlo. Statist. Sci. 473–483.
• [6] Glynn, P.W. and Meyn, S.P. (1996). A Liapounov bound for solutions of the Poisson equation. Ann. Probab. 24 916–931.
• [7] Hastings, W.K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57 97–109.
• [8] Henderson, S.G. (1997). Variance Reduction Via an Approximating Markov Process. Ph.D. thesis, Department of Operations Research, Stanford University.
• [9] Henderson, S.G. and Glynn, P.W. (2002). Approximating martingales for variance reduction in Markov process simulation. Math. Oper. Res. 27 253–271.
• [10] Henderson, S.G., Meyn, S.P. and Tadić, V.B. (2003). Performance evaluation and policy selection in multiclass networks. Discrete Event Dyn. Syst. 13 149–189.
• [11] Hernández-Lerma, O. and Bernard Lasserre, J. (1999). Further Topics on Discrete-Time Markov Control Processes. Applications of Mathematics (New York) 42. New York: Springer.
• [12] Hoekstra, A.H. and Steutel, F.W. (1984). Limit theorems for Markov chains of finite rank. Linear Algebra Appl. 60 65–77.
• [13] Jarner, S.F. and Hansen, E. (2000). Geometric ergodicity of Metropolis algorithms. Stochastic Process. Appl. 85 341–361.
• [14] Kipnis, C. and Varadhan, S.R.S. (1986). Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions. Comm. Math. Phys. 104 1–19.
• [15] Madras, N. and Randall, D. (2002). Markov chain decomposition for convergence rate analysis. Ann. Appl. Probab. 12 581–606.
• [16] Makowski, A.M. and Shwartz, A. (2002). The Poisson equation for countable Markov chains: Probabilistic methods and interpretations. In Handbook of Markov Decision Processes. Internat. Ser. Oper. Res. Management Sci. 40 269–303. Boston, MA: Kluwer Academic.
• [17] Mengersen, K.L. and Tweedie, R.L. (1996). Rates of convergence of the Hastings and Metropolis algorithms. Ann. Statist. 24 101–121.
• [18] Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. and Teller, E. (1953). Equation of state calculations by fast computing machines. J. Chem. Phys. 21 1087–1092.
• [19] Meyn, S. (2008). Control Techniques for Complex Networks. Cambridge: Cambridge Univ. Press.
• [20] Meyn, S. and Tweedie, R.L. (2009). Markov Chains and Stochastic Stability, 2nd ed. Cambridge: Cambridge Univ. Press.
• [21] Meyn, S.P. and Tweedie, R.L. (1994). Computable bounds for geometric convergence rates of Markov chains. Ann. Appl. Probab. 4 981–1011.
• [22] Mijatović, A. (2007). Spectral properties of trinomial trees. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 463 1681–1696.
• [23] Mijatović, A. and Pistorius, M. (2013). Continuously monitored barrier options under Markov processes. Math. Finance 23 1–38.
• [24] Mijatović, A., Vidmar, M. and Jacka, S. (2014). Markov chain approximations for transition densities of Lévy processes. Electron. J. Probab. 19 no. 7, 37.
• [25] Roberts, G.O. and Rosenthal, J.S. (1997). Geometric ergodicity and hybrid Markov chains. Electron. Commun. Probab. 2 13–25.
• [26] Roberts, G.O. and Rosenthal, J.S. (2004). General state space Markov chains and MCMC algorithms. Probab. Surv. 1 20–71.
• [27] Roberts, G.O. and Tweedie, R.L. (1996). Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms. Biometrika 83 95–110.
• [28] Roberts, G.O. and Tweedie, R.L. (1996). Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli 2 341–363.
• [29] Rosenthal, J.S. (1992). Convergence of pseudo-finite markov chains. Unpublished manuscript.
• [30] Runnenburg, J.T. and Steutel, F.W. (1962). On Markov chains, the transition function of which is a finite sum of products of functions on one variable: Preliminary report. Stichting Mathematisch Centrum. Statistische Afdeling S304 1–22.
• [31] Tierney, L. (1994). Markov chains for exploring posterior distributions. Ann. Statist. 22 1701–1762.


text:
# ISRO-2013-28

2.3k views

The most simplified form of the Boolean function

$x (A, B, C, D) = \sum (7, 8, 9, 10, 11, 12, 13, 14, 15)$

(expressed in sum of minterms) is?

1. A + A'BCD
2. AB + CD
3. A + BCD
4. ABC + D
0
i think it should be A also in un simplified form. correct me if i am wrong

Option C

selected by
0
option C is correct.

Ans: C

1 vote

Option (C)

Following is the solution for the boolean function:

option C is correct

## Related questions

1
2k views
The binary equivalent of the decimal number $42.75$ is $101010 . 110$ $100110 . 101$ $101010 . 101$ $100110 . 110$
In a three stage counter, using $RS$ flip flops what will be the value of the counter after giving $9$ pulses to its input ? Assume that the value of counter before giving any pulses is $1$ : $1$ $2$ $9$ $10$
How many programmable fuses are required in a PLA which takes $16$ inputs and gives $8$ outputs? It has to use $8$ OR gates and $32$ AND gates. $1032$ $776$ $1284$ $1536$
Two eight bit bytes $1100 0011$ and $0100 1100$ are added. What are the values of the overflow, carry and zero flags respectively, if the arithmetic unit of the CPU uses $2$'s complement form? $0, 1, 1'$ $1, 1, 0$ $1, 0, 1$ $0, 1, 0$


text:
New Zealand
Level 8 - NCEA Level 3

# Applications of sine and cosine functions

## Interactive practice questions

The population (in thousands) of two different types of insects on an island can be modelled by the following functions: Butterflies: $f\left(t\right)=a+b\sin\left(mt\right)$f(t)=a+bsin(mt), Crickets: $g\left(t\right)=c-d\sin\left(kt\right)$g(t)=cdsin(kt)

$t$t is the number of years from when the populations started being measured, and $a$a,$b$b,$c$c,$d$d,$m$m, and $k$k are positive constants. The graphs of $f$f and $g$g for the first $2$2 years are shown below.

a

State the function $f\left(t\right)$f(t) that models the population of Butterflies over $t$t years.

b

State the function $g\left(t\right)$g(t) that models the population of Crickets over $t$t years.

c

How many times over a $18$18 year period will the population of Crickets reach its maximum value?

d

How many years after the population of Crickets first starts to increase, does it reach the same population as the Butterflies?

e

Solve for $t$t, the number of years it takes for the population of Butterflies to first reach $200000$200000.

Easy
Approx 19 minutes

Three objects, $X$X, $Y$Y and $Z$Z are placed in a magnetic field such that object $X$X is $2$2 cm from object $Y$Y and $4$4 cm from object $Z$Z. As object $X$X is moved closer to line $YZ$YZ, object $Y$Y and $Z$Z move in such a way that the lengths $XY$XY and $XZ$XZ remain fixed.

Let $\theta$θ be the angle between sides $XY$XY and $XZ$XZ, and let the area of triangle $XYZ$XYZ be represented by $A$A.

A circular Ferris wheel that is $40$40 meters in diameter contains several carriages. Hannah and Michael enter a carriage at the bottom of the Ferris wheel, and get off $6$6 minutes later after having gone around completely $3$3 times. When a carriage is at the bottom of the wheel, it is $1$1 meter above the ground.

The tide rises and falls in a periodic manner, and Brad needs to chart tide levels to determine when he can sail his ship into a bay. He begins measuring at low tide at $8$8am, and sees the marking that the bay is $7$7 metres deep. He measures high tide at $2$2pm, when the bay is $15$15metres deep.

### Outcomes

#### M8-2

Display and interpret the graphs of functions with the graphs of their inverse and/or reciprocal functions


text:
# Changeset 692afbb

Ignore:
Timestamp:
Mar 14, 2018, 6:36:44 PM (4 years ago)
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, with_gc
Children:
13f5a70
Parents:
7c2a7b6
Message:

update description of fallthrough

File:
1 edited

### Legend:

Unmodified
 r7c2a7b6 \author[1]{Robert Schluntz} \author[1]{Peter A. Buhr*} \authormark{Aaron Moss \textsc{et al}} \address[1]{\orgdiv{David R. Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Ontario}, \country{Canada}}} Love it or hate it, C is extremely popular, highly used, and one of the few systems languages. In many cases, \CC is often used solely as a better C. Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. Nevertheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. \CFA (pronounced C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that aims to add modern language features to C while maintaining both source compatibility with C and a familiar programming model for programmers. \lstMakeShortInline@% \end{cquote} for a contiguous list:\footnote{gcc has the same mechanism but awkward syntax, \lstinline@2 ...42@, because a space is required after a number, otherwise the period is a decimal point.} for a contiguous list:\footnote{gcc has the same mechanism but awkward syntax, \lstinline@2 ...42@, as a space is required after a number, otherwise the first period is a decimal point.} \begin{cquote} \lstDeleteShortInline@% Finally, Figure~\ref{f:FallthroughStatement} shows @fallthrough@ may appear in contexts other than terminating a @case@ clause, and have an explicit transfer label allowing separate cases but common final-code for a set of cases. The target label must be below the @fallthrough@, \ie @fallthrough@ cannot form a loop, and the label may not be nested in a control structure, \ie it must be at the same level as the @case@ clauses; the target label may be case @default@. The target label must be below the @fallthrough@ and may not be nested in a control structure, \ie @fallthrough@ cannot form a loop, and the target label must be at the same or higher level as the containing @case@ clause and located at the same level as a @case@ clause; the target label may be case @default@, but only associated with the current @switch@/@choose@ statement. \begin{figure} \label{f:FallthroughStatement} \end{figure} Collectively, these control-structure enhancements reduce programmer burden and increase readability and safety. } \end{cfa} Collectively, these control-structure enhancements reduce programmer burden and increase readability and safety.


text:
jp7103165_si_002.pdf (45.87 kB)

# Stability of N18C6H6:  Triangular versus Hexagonal Structure

journal contribution
posted on 07.02.2008, 00:00 by Anthony Pinkston, DeAna McAdory, Jacqueline Jones, Danielle Shields, Ramola Langham, Kasha Casey, Douglas L. Strout
Large nitrogen cage molecules Nx have been previously shown to prefer elongated, cylindrical structures with triangular caps versus more spherical structures composed entirely of pentagons and hexagons. It was argued that this preference derived from the electronic properties of the nitrogen atoms, including the lone pairs. In the current study, the same structural comparison is carried out, with the substitution of C−H-bonding groups for six of the nitrogens. Various substitution patterns on the cylindrical (triangular) and spherical (hexagonal) frameworks are examined. Isomers of N18C6H6 are studied by theoretical calculations to determine the relative stability of triangular versus hexagonal structures, as well as the stability effects of the substitution patterns on each framework. Hartree−Fock theory, density functional theory (PBE1PBE), and perturbation theory (MP2) are employed, in conjunction with the correlation-consistent basis sets of Dunning. Stability trends within each class of molecules and between the two classes of molecules are calculated and discussed.


text:
# Equivalence relation to make a group commutative

A while ago I was wondering if there is a "natural" way to make a commutative group out of an arbitrary one. I played with the idea a bit and here is what I came up with.

Define a binary relation $\sim$ on a group $G$ such that $x \sim y$ if $\exists a, b \in G$ such that $ab=x$ and $ba=y$.

It's fairly easy to show this is an equivalence relation:

• Reflexivity: $xe = ex = x$, so $x\sim x$.
• Symmetry: obvious.
• Transitivity: Suppose $x \sim y$ and $y \sim z$. Then $\exists a,b,c,d$ such that $ab=x$, $ba=cd=y$, and $dc=z$. Let $e = ad^{-1}$ and $f=db$. Then $ef = ad^{-1}db = ab = x$, and $fe = dbad^{-1} = dyd^{-1} = dcdd^{-1} = dc = z$. So $x \sim z$. $\square$

Question: Let $[x]$ denote the equivalence class of $G/\mathord\sim$ containing $x$. Suppose we let $[x][y] = [xy]$. Is this operation well-defined?

If so, then $G/\mathord\sim$ is clearly a group under this operation. Furthermore, it is commutative, since $[x][y] = [xy] = [yx] = [y][x]$ (where the middle equality is by definition of $\sim$).

-
A natural way to make commutative groups out of arbitrary groups is with the commutator subgroup (abelianization). See here. – Mikko Korhonen Apr 23 '14 at 6:52

## 2 Answers

No, it is not (except in trivial cases). Note that the only element equivalent to $e$ is $e$ itself.
So if $y \in [x]$ but $y \ne x$, $y x^{-1} \in [x] [x^{-1}]$ but is not in $[x x^{-1}] = \{e\}$.

-
Oh, shoot. In fact, these "trivial cases" are precisely those where $G$ is already commutative and $\sim$ is the equality relation. – augurar Apr 23 '14 at 6:41

Note that the equivalence relation is identical to conjugacy classes. If

$$\exists a: axa^{-1}=y$$ then $$a^{-1}axa^{-1}a=x,\;(a)(a^{-1}axa^{-1})=axa^{-1}=y$$ or on a better day just $$a^{-1}(ax)=x,\;(ax)a^{-1}=y$$ and conversely $$\exists a,b: ab=x,\;ba=y\implies aya^{-1}=x$$

-
Interesting. You can simplify the first part by using $(xa^{-1})(a)=x$, $(a)(xa^{-1})=y$. – augurar Apr 23 '14 at 6:48
@augurar Haha that's great... this is what abstract algebra does to my brain... – NotNotLogical Apr 23 '14 at 6:49


text:
# [OS X TeX] crashing

Fri Jul 21 14:06:18 EDT 2006

On Jul 21, 2006, at 1:49 PM, George Gratzer wrote:

> Interesting, it seems to go up about a 1 MB per typesetting.

Seems to vary by the job.

w/ a minimal document:

\documentclass{minimal}
\begin{document}
$6 \times 9$
\end{document}

I see it go up by ~.05MB per typesetting for that.

Another job (that journal I've been working on) gains ~10MB per
typesetting run.

> So I should quit before it is too high? What is too high?

Yes to the first (I don't get to work in TeX for extended periods of
time which is probably why my crash rate is so low). Probably too
high'' is some value relative to available memory --- what that
relation would be is a good question.

William

--
senior graphic designer
Fry Communications

This email message and any files transmitted with it contain information
which is confidential and intended only for the addressee(s). If you are
not the intended recipient(s), any usage,  dissemination, disclosure, or
action taken in  reliance on it is prohibited.  The reliability of  this
method of communication cannot be guaranteed.  Email can be intercepted,
corrupted, delayed, incompletely transmitted, virus-laden,  or otherwise
affected during transmission. Reasonable steps have been taken to reduce
the risk of viruses, but we cannot accept liability for damage sustained
as a result of this message. If you have received this message in error,
please immediately delete it and all copies of it and notify the sender.
------------------------- Info --------------------------
Mac-TeX Website: http://www.esm.psu.edu/mac-tex/
& FAQ: http://latex.yauh.de/faq/
TeX FAQ: http://www.tex.ac.uk/faq
List Archive: http://tug.org/pipermail/macostex-archives/


text:
# Members & Guests

KIT Karlsruhe

## Project

15Spaces and Moduli Spaces of Riemannian Metrics with Curvature Bounds on compact and non-compact Manifolds

## Publications

In this paper we study spaces of Riemannian metrics with lower bounds on intermedi- ate curvatures. We show that the spaces of metrics of positive p-curvature and k-positive Ricci curvature on a given high-dimensional Spin-manifold have many non-trivial homotopy groups provided that the manifold admits such a metric.


text:
# If sides A and B of a triangle have lengths of 3 and 5 respectively, and the angle between them is (pi)/3, then what is the area of the triangle?

The area of the triangle is $\frac{15 \cdot \sqrt{3}}{4}$
The area of a triangle is equal to $\frac{1}{2} b c \sin a$ where $b$ and $c$ are the lengths of sides, and $a$ is the angle in between.


text:
# Converting deserts into more hospitable places by inducing rain through the ocean?

I want to know if this is scientifically possible in the real world.

When you take vast expanses of deserts (the sandy hot ones, not the icy ones) like the Sahara, life in general is restricted to near whatever small rivers or oasis/lakes there are or close to the oceans. But these places can become vastly different with just a bit of steady rain. Take India or mainland southeast Asia/ southern China for example which is on the same level as the Sahara from top to bottom on the map but is much greener and can sustain high population and produce lots of food and even rainforests similar to the amazon thanks to monsoons and tropical rainstorms.

The only way to make it rain is to get cloud systems to make their way into the Sahara, but as is evident this doesn't happen. So maybe a way to fix this is to bring massive quantites of water inland where they can evaporate away and then rain down somewhere else in the Sahara (which is HUGE so the rain clouds won't make it far enough to escape the desert).

This could be achieved by making massive, deep canals (dimensions can vary) that run through much of the interior of the Sahara (like the veins of a leaf) bringing Atlantic and Mediterranean water inland which evaporates in vast quantities and bringing more water in. Dams could be built to control flow and generate power. Endoheric basins could be expanded on or completely built from scratch to create inland seas like the Aral or Caspian. Rivers like the Congo which already have a high elevation and is second only to the amazon in the water it produces could be diverted easily from higher to lower elevations in the Sahara. Dams again could generate power for new settlements along the new river banks.

The salt which collects at the bottom could be a problem and block the canals but they could be mined away or made into building materials and coated to prevent water from dissolving them and this could be used to make at least a few small scale houses. Other industrial uses escape me but must exist. The threat of rising sea levels is non existent as these canals could be made deeper and narrower to prevent flooding. if built on a large enough scale it may even lower the sea levels worldwide. The lake chad basin alone is bigger than a quarter of the US and is mostly desert. Mining could make it deeper. The Massive amounts of materials generated could be used to reclaim new land from the ocean or build flood barriers like the Netherlands is doing.

Could this turn the Sahara green? Or at least make it more inhabitable?

• Apart from the destruction of a unique ecosystem just for fun, why would you want to do that? That doesn't seem economically feasible, no matter if it could be done in theory. There are currently massive operations to prevent the African deserts from spreading further by planting trees. Water is one part of the equation, but time and time again, planting trees is step one to increasing the usability of the land. If you're building a world like that, read up on how it's actually done. Feb 21 at 13:59
• @Raditz_35: More practical than trees would be grasslands. Much of the area that's now the Sahara desert was actually grasslands in pre-Roman times. Overgrazing destroyed the soil. (Actually a complex layer held in place by the roots of grasses and other plants, which retained moisture.) Much the same thing happened in a lot of the US west, due to cattle grazing. Feb 21 at 18:15
• (1) Plenty of clouds pass over the Sahara; they just don't have any incentive to rain down. (2) We are lucky in that mother Nature already made the experiment for us. Look at a map of Arabia, and notice the two biggg canals to the north-east (= the Persian Gulf) and the south-west (= the Red Sea). Do those very large inlets of the ocean help with generating rain? Nope, they don't. So why would your puny man-made canals help when Nature's enourmous canals don't? Feb 21 at 19:06
• Does this answer your question? Ultimate Australian Canal Feb 21 at 19:07
• Just for completeness: the Sahara is emphatically not at sea level; it is a vast tableland, dotted with mountain ranges. Its average altitude is some 450 meters (about 1300 feet) above sea level. Water is heavy: lifting enormous amounts of water 450 meters up is a daunting project. Feb 21 at 19:11

You have rediscovered the Sahara Sea idea.

Its a good 150 years old, so you can sea that people have been thinking about this sort of idea for quite some time now. Proponents of the plan think it has all the good points that you mentioned. What doesn't seem so obvious is any consideration of the bad effects of having a non-draining hypersaline lake. They also didn't worry about the opinions of the locals, because colonial types with grandiose ideas seldom worry about that sort of thing. It is worth remembering that the people who live there will have strong opinions about such a project, have their own economical and political woes, and a significant amount of suspicion for anything coming from former colonial powers.

Maybe have a read of this XKCD What If? about flooding death valley, which talks about the Salton Sea, not very enthusiatically. Of course, the Salton sea is never refilled in the way that a new body of water connected to the ocean would be, but some of the underlying issues will be shared.

Dealing with the salinity is unlikely to be as easy as mining a bit of salt and building some pyramids with it, alas, especially when you consider the sheer scale of the enterprise.

It may be that the local climatic changes caused by this new body of water might be beneficial enough to warrant the risks of the creation of the sea, and the huge amount of destruction it would cause. I wouldn't want to bet on it, though.

Backfire

Although moisture is one of the important building blocks of life, you can't just throw water on it repeatedly and hope for the best. To make something green, you also need the following:

• Water needs to be retained.
• Good soil must be available.

A desert often misses one or both of these things. Good examples are temperate and arid deserts. Few things grow, as there isn't enough to retain the water that has fallen. In addition, without plants and trees the nutrient rich soil is washed awayby rain, the very thing that should help. There is erosion.

More rain in the sahara specifically will not work directly. Left alone it might grow fully green with enough rain, but it would take a long time. And I say 'might', as I don't know how much soil is washed away and how easily the sand holds the water. You can still increase the speed and range of this process though. In China they've experimented with planting diamond shapes throughout the desert. Thise are just plants on the edges of the diamonds, while the inside is untouched. The plants start holding both the soil, the water and cool down their surroundings thanks to vaporising water. This will increase the chances of rain and vegetation to grow in the diamond shapes. In a year it looks green. In three years it looks like a wild young patch of forest. To my knowledge this isn't location specific, although I do fully expect you need to have a basic amount of rainfall.

Your idea to evaporate more water and in closer proximity will help with more rainfall and cooling, although the saline properties can be difficult close to the water source as well as building up salt levels like the red sea, potentially stoppimg water flow. It has many other possible problems as Starfish Prime is stating. But in essence, you can increase the rainfall. Still, more vegetation would be a great help.

The whole idea is not particularly practical. However some progress could be made. I suggest that salt water canals into the interior of the Sahara would be a very bad idea. It would cost a fortune and they would contaminate the existing deep water aquifers making them unusable. To make matters worse the salt would soon start to crystallize on the surface and sides of the canals and some would be blown across the land. Operations to remove salt would undoubtedly also spill salt water onto the land increasing the problem further.

It would be far better to pump fresh water into specific areas of the desert than salt water. Also it would be beneficial to ensure that what little rain does fall is utilized to the maximum extent possible, either captured and stored for use in cisterns underground or directed through a series of overflow channels into areas where plants and trees are being grown.

The cost would be huge you might want to try getting some top end multi billionaire like Elon Musk to redirect their energies into greening the desert (fat chance). But assuming sufficient funds were available it would be possible to build a lot of water purification plant on the coast and pipe the water inland. With the high temperatures and large scale of operations some sort of massive solar plant could be built. I doubt it would be possible to green more than a small fraction of the Sahara in this way but it depends on how much time and money is involved.

Note the practical problems would also include a myriad of political issues. Once a few hundred square miles or more of greenery had been established fighting would likely start over ownership and water rights (regardless of who agreed what initially).

### There's a 21st century solution to this

So as pointed out by Both Willik and Starfish Prime, we've been planning to build a channel into the saharah for nearly 2 centuries. The issues are:

• It'll accumulate salt. Salt is very bad when you want to grow things.
• It'll accumulate agricultural run off, so it'll become poisonous.
• It'll probably stink real bad, ala Salton Sea.
• You'll need to dredge the channel and lake constantly.

The Sahara desert is 9.2 trillian square meters, to water it with 250mm of yearly rainfall (A common definition of a desert) you'll need 2.3 * 10^15 liters of water per year. That water needs to be salt free and pumped into the Sahara.

This desal plant can produces 1 * 10^11 liters of water per annum, so you'd need to scale this up by 23,000. It cost \$1.83 billion for 1 plant, so you're looking at back of envelope \$42 trillion for the upfront desalination plants.

Desalination is pretty expensive; You're looking at about 3.5KWH per KL, so 8.05 * 10^15 Watts of power per year. 8 PetaWattHours of power per year, or 920 GW of average power throughput. This is 92 times larger than the worlds largest solar/battery power plant, but not entirely impossible. Looking at about \$1.2 trillion for power, which would include 2.7TWH of battery storage allowing it to run overnight. You'd probably want to spent that much again on wind turbines too to avoid draining the batteries every night, which is bad for their longevity. The total of the project is looking at about \$45 trillion, lets round it up to \\$50 to include piping, pumps, buying land from people who are going to be flooded, and everything else I'm forgetting.

Earths GDP is about 80 trillion, so funding this would be hard, but not impossible. I'd suggest a global 30% wealth tax on anyone with over 3 million USD in wealth, and a 99% wealth tax on anyone with over 1 billion USD in wealth. The tax is so small relative to their fortunes they won't even notice - they'll all still be multi-millionaires at the end.


text:
# Cyclic-Order Graph Algorithm

Cyclic-Order Graph Algorithm was introduced in the article: Š. Berežný, J. Buša Jr., and M. Staš, “Software solution of the algorithm of the cyclic-order graph,” Acta Electrotechnica et Informatica, vol. 18, no. 1, pp. 3–10, 2018.


text:
# Math Help - Using a double integral to find the area of a circle.

1. ## Using a double integral to find the area of a circle.

I have scanned the question I am working on and attached it as an image to this thread. A hint on this question would be good enough.

2. Originally Posted by Undefdisfigure
I have scanned the question I am working on and attached it as an image to this thread. A hint on this question would be good enough.
Is this a unit circle?

3. Originally Posted by Undefdisfigure
I have scanned the question I am working on and attached it as an image to this thread. A hint on this question would be good enough.
Note that $r=\cos\theta$ is a circle with center at $\left(\frac{1}{2},0)$ and radius $r=\frac{1}{2}$.

Similarly, $r=\sin\theta$ is a circle with center at $\left(0,\frac{1}{2})$ and radius $r=\frac{1}{2}$.

Now these circles will overlap at some point. So my hint is this:

When considering the region of intersection, split it up into two separate regions. Due to how we find limits of integration in polar coordinates, each region will be defined over different ranges for $\theta$. So your integrals will look something like:

$\displaystyle\int_{\theta_0}^{\theta_1} \int_0^{\cos\theta} r\,dr\,d\theta+\int_{\theta_0^{\prime}}^{\theta_1^ {\prime}}\int_0^{\sin\theta}r\,dr\,d\theta$

where $\theta_0\leq \theta\leq\theta_1$ is the range you consider for the $r=\cos\theta$ part, and $\theta_0^{\prime}\leq \theta\leq\theta_1^{\prime}$ is the range you consider for the $r=\sin\theta$ part.

Can you proceed? If you still have issues, post back!

4. Oops, I didn't see somebody else posted.

5. Originally Posted by Undefdisfigure
Yeah but what kind of limits of integration would I use?
To figure out the limits of integration for $\theta$, its best to look at a graph showing the intersection of the two circles. The only additional hint I'll supply for now is that $\theta=\frac{\pi}{4}$ is a value worth considering.


text:
# Question #2c112

Nov 3, 2017

One.

#### Explanation:

The trick here is to remember that a complete set of quantum numbers can only describe a single electron in a given atom.

In other words, every time you have values for all the four quantum numbers that we use to describe the location and spin of an electron in an atom, you can say that the set can describe a single electron, not more.

In this case, you have

$n = 4 , l = 2 , {m}_{l} = - 2 , {m}_{s} = + \frac{1}{2}$

This set tells you that the electron is located on the fourth energy level, hence why $n = 4$, in the $d$ subshell, hence why $l = 2$, in one of the five $4 d$ orbitals, let's say $4 {d}_{x y}$, hence why ${m}_{l} = - 2$, and has spin-up, hence why ${m}_{s} = + \frac{1}{2}$.

This is the only electron that can have these particular values for the four quantum numbers in the given atom.


text:
Outlook: DatChat Inc. Common Stock is assigned short-term Ba1 & long-term Ba1 estimated rating.
Dominant Strategy : Wait until speculative trend diminishes
Time series to forecast n: 11 Feb 2023 for (n+6 month)
Methodology : Deductive Inference (ML)

## Abstract

DatChat Inc. Common Stock prediction model is evaluated with Deductive Inference (ML) and Ridge Regression1,2,3,4 and it is concluded that the DATS stock is predictable in the short/long term. According to price forecasts for (n+6 month) period, the dominant strategy among neural network is: Wait until speculative trend diminishes

## Key Points

1. What are the most successful trading algorithms?
2. What is prediction in deep learning?
3. How useful are statistical predictions?

## DATS Target Price Prediction Modeling Methodology

We consider DatChat Inc. Common Stock Decision Process with Deductive Inference (ML) where A is the set of discrete actions of DATS stock holders, F is the set of discrete states, P : S × F × S → R is the transition probability distribution, R : S × F → R is the reaction function, and γ ∈ [0, 1] is a move factor for expectation.1,2,3,4

F(Ridge Regression)5,6,7= $\begin{array}{cccc}{p}_{a1}& {p}_{a2}& \dots & {p}_{1n}\\ & ⋮\\ {p}_{j1}& {p}_{j2}& \dots & {p}_{jn}\\ & ⋮\\ {p}_{k1}& {p}_{k2}& \dots & {p}_{kn}\\ & ⋮\\ {p}_{n1}& {p}_{n2}& \dots & {p}_{nn}\end{array}$ X R(Deductive Inference (ML)) X S(n):→ (n+6 month) $\stackrel{\to }{S}=\left({s}_{1},{s}_{2},{s}_{3}\right)$

n:Time series to forecast

p:Price signals of DATS stock

j:Nash equilibria (Neural Network)

k:Dominated move

a:Best response for target price

For further technical information as per how our model work we invite you to visit the article below:

How do AC Investment Research machine learning (predictive) algorithms actually work?

## DATS Stock Forecast (Buy or Sell) for (n+6 month)

Sample Set: Neural Network
Stock/Index: DATS DatChat Inc. Common Stock
Time series to forecast n: 11 Feb 2023 for (n+6 month)

According to price forecasts for (n+6 month) period, the dominant strategy among neural network is: Wait until speculative trend diminishes

X axis: *Likelihood% (The higher the percentage value, the more likely the event will occur.)

Y axis: *Potential Impact% (The higher the percentage value, the more likely the price will deviate.)

Z axis (Grey to Black): *Technical Analysis%

## IFRS Reconciliation Adjustments for DatChat Inc. Common Stock

1. The fair value of a financial instrument at initial recognition is normally the transaction price (ie the fair value of the consideration given or received, see also paragraph B5.1.2A and IFRS 13). However, if part of the consideration given or received is for something other than the financial instrument, an entity shall measure the fair value of the financial instrument. For example, the fair value of a long-term loan or receivable that carries no interest can be measured as the present value of all future cash receipts discounted using the prevailing market rate(s) of interest for a similar instrument (similar as to currency, term, type of interest rate and other factors) with a similar credit rating. Any additional amount lent is an expense or a reduction of income unless it qualifies for recognition as some other type of asset.
2. The accounting for the forward element of forward contracts in accordance with paragraph 6.5.16 applies only to the extent that the forward element relates to the hedged item (aligned forward element). The forward element of a forward contract relates to the hedged item if the critical terms of the forward contract (such as the nominal amount, life and underlying) are aligned with the hedged item. Hence, if the critical terms of the forward contract and the hedged item are not fully aligned, an entity shall determine the aligned forward element, ie how much of the forward element included in the forward contract (actual forward element) relates to the hedged item (and therefore should be treated in accordance with paragraph 6.5.16). An entity determines the aligned forward element using the valuation of the forward contract that would have critical terms that perfectly match the hedged item.
3. At the date of initial application, an entity shall assess whether a financial asset meets the condition in paragraphs 4.1.2(a) or 4.1.2A(a) on the basis of the facts and circumstances that exist at that date. The resulting classification shall be applied retrospectively irrespective of the entity's business model in prior reporting periods.
4. Annual Improvements to IFRS Standards 2018–2020, issued in May 2020, added paragraphs 7.2.35 and B3.3.6A and amended paragraph B3.3.6. An entity shall apply that amendment for annual reporting periods beginning on or after 1 January 2022. Earlier application is permitted. If an entity applies the amendment for an earlier period, it shall disclose that fact.

*International Financial Reporting Standards (IFRS) adjustment process involves reviewing the company's financial statements and identifying any differences between the company's current accounting practices and the requirements of the IFRS. If there are any such differences, neural network makes adjustments to financial statements to bring them into compliance with the IFRS.

## Conclusions

DatChat Inc. Common Stock is assigned short-term Ba1 & long-term Ba1 estimated rating. DatChat Inc. Common Stock prediction model is evaluated with Deductive Inference (ML) and Ridge Regression1,2,3,4 and it is concluded that the DATS stock is predictable in the short/long term. According to price forecasts for (n+6 month) period, the dominant strategy among neural network is: Wait until speculative trend diminishes

### DATS DatChat Inc. Common Stock Financial Analysis*

Rating Short-Term Long-Term Senior
Outlook*Ba1Ba1
Income StatementBa1B3
Balance SheetCCaa2
Leverage RatiosCaa2Baa2
Cash FlowB3B1
Rates of Return and ProfitabilityCBaa2

*Financial analysis is the process of evaluating a company's financial performance and position by neural network. It involves reviewing the company's financial statements, including the balance sheet, income statement, and cash flow statement, as well as other financial reports and documents.
How does neural network examine financial reports and understand financial state of the company?

### Prediction Confidence Score

Trust metric by Neural Network: 73 out of 100 with 836 signals.

## References

1. Breiman L. 1996. Bagging predictors. Mach. Learn. 24:123–40
2. LeCun Y, Bengio Y, Hinton G. 2015. Deep learning. Nature 521:436–44
3. Bengio Y, Schwenk H, Senécal JS, Morin F, Gauvain JL. 2006. Neural probabilistic language models. In Innovations in Machine Learning: Theory and Applications, ed. DE Holmes, pp. 137–86. Berlin: Springer
4. Thompson WR. 1933. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25:285–94
5. R. Sutton and A. Barto. Reinforcement Learning. The MIT Press, 1998
6. Hartigan JA, Wong MA. 1979. Algorithm as 136: a k-means clustering algorithm. J. R. Stat. Soc. Ser. C 28:100–8
7. S. Bhatnagar, R. Sutton, M. Ghavamzadeh, and M. Lee. Natural actor-critic algorithms. Automatica, 45(11): 2471–2482, 2009
Frequently Asked QuestionsQ: What is the prediction methodology for DATS stock?
A: DATS stock prediction methodology: We evaluate the prediction models Deductive Inference (ML) and Ridge Regression
Q: Is DATS stock a buy or sell?
A: The dominant strategy among neural network is to Wait until speculative trend diminishes DATS Stock.
Q: Is DatChat Inc. Common Stock stock a good investment?
A: The consensus rating for DatChat Inc. Common Stock is Wait until speculative trend diminishes and is assigned short-term Ba1 & long-term Ba1 estimated rating.
Q: What is the consensus rating of DATS stock?
A: The consensus rating for DATS is Wait until speculative trend diminishes.
Q: What is the prediction period for DATS stock?
A: The prediction period for DATS is (n+6 month)


text:
Finding Coefficient of Determination

1. Apr 23, 2017

Tchao

1. The problem statement, all variables and given/known data

If the slope of the regression line is negative and the correlation coefficient is -0.5, coefficient of determination is:

2. Relevant equations

coefficient of determination: r2 = 1 - SSE/SST

correlation coefficient: r = Sxy / (√Sxx * √Syy )

3. The attempt at a solution
r = -0.5
r2 = 0.25 but because slope of regression line is negative, then coefficient of determination would be also negative.
r2 = -0.25

I am not sure if my though process in determining the correct answer is right or not.

Attached Files:

File size:
19.1 KB
Views:
19
File size:
36.1 KB
Views:
17
2. Apr 24, 2017

I like Serena

Hi Tchao,

Indeed, the coefficient of determination is $r^2=0.25$.
And it is positive, since a square is always positive.
It means that the coefficient of determination doesn't tell us whether the slope is upward or downward, only that there is a correlation.


text:
# array_split.ShapeSplitter.calculate_split_by_indices_per_axis¶

ShapeSplitter.calculate_split_by_indices_per_axis()[source]

Returns split calculated using extents obtained from indices_per_axis.

Return type: numpy.ndarray A numpy structured array where each element is a tuple of slice objects.