RRT – Rapidly Exploring Random Tree 

RRT is a searching algorithm  applied by building a space filling tree  from samples drawn randomly of high-dimensional search spaces .

import networkx as nx
import numpy as np
from sklearn.neighbors import KDTree
class RRT:
      def __init__(self,x_init):
          self.tree = nx.DiGraph()
          self.tree.add_node(x_init)
def nearest_neighbour(x_rand,rrr):
    dist=1000
    x_rand = np.array(x_rand)
    for node in rrt.tree.nodes:
        d = np.linalg.norm(x_rand - np.array(node))
        if d < dist:
           dist = d
           vertex = node
    return vertex
def rand_conf():
    return np.random.uniform(0,100),np.random.uniform(0,100)
def build_rrt(init_configuration, num_vertices_k, delta_distance):
    rrt = RRT(init_configuration)
    for k in num_vertices_k:
        x_rand = rand_conf() 
        x_near = nearest__neighbour(x_rand,rrt)
        x_new = new_conf(x_near,x_rand,delta_distance)
        rtt.tree.add_node(x_new)
        rrt.tree.add_edge(tuple(x_near),tuple(x_new))
    return rrt

rrt = build_rrt((10,10),100,1)

Comments are closed, but trackbacks and pingbacks are open.