[Home](../index.html) > Voxel Structures --- # Voxel Structures - Planning and Control ## Bill-e Swarm In this project, the study and implementation of Bill-e/multiple Bill-es' path planning and control will be conducted. The purpose will be to build/assemble voxel structures of different shapes on demand. I will be conducting a series of small studies exploring each of the variables in the voxel assembly process. ----- ###[Context](https://gitlab.cba.mit.edu/bej/relative_robot_automation/tree/master/background/prior_art/previous_studies) ---- ### Bill-e Simulation *(Click on titles/images for interactive simulations)* #### [IK Model](180418_IK/index.html)

As a first step, I created an inverse kinematic interactive model of Bill-e in Three.js where the input is a desired point and the output is the list of angles of each joint. The Model also has the option to change the Bille-s' dimensions and the fixed leg for Bill-e to be able to move the other leg. #### [Step](180426_virtual_bill-e/index.html)

In the second iteration I implemented the steps forward and backward steps. The legs follow points on a parabola that is drawn between the voxels. In this version the input is the target location and virtial Bill-e figures out the rest. #### [Complex Steps](180509_virtual_bill-e/index.html)

In this iteration I implemented a more complex IK model for concave and convex turns. Here still the input for each leg the new positions for both legs and the up vector of the vector. #### [Path Plan](180510_bill-e_path_planing/index.html)

Here, I tried to make Bill-e more intelligent by making him calculate the path from one voxel to another. The assumption is that Bill-e has the map of the existing voxels (in relation to his current position). The algorithm is as follows: > **while** *leg1 is not at target location * **then** >> **store** *x position*

>> **while** *leg1 x position is not same as target location x* **then**

>>> take step in target x direction

>>> count step

>>> **if** *looped back to stored x position* **then**

>>>> **continue** >> **end**

>> **store** *y position*

>> **while** *leg1 y position is not same as target location y* **then**

>>> take step in target y direction

>>> count step

>>> **if** *looped back to stored y position* **then**

>>>> **continue** >> **end**

>> **store** *z position*

>> **while** *leg1 z position is not same as target location z* **then**

>>> take step in target z direction

>>> count step

>>> **if** *looped back to stored z position* **then**

>>>> **continue** >> **end**

>> **if** *number of steps larger than maximum allowed steps (got stuck)* **then**

>>> **output** can't reach point

>>> **continue** > **end**

#### [Shortest Path](180518_bill-e_path_planing/index.html)

In the previous path planning algorithm, the found path wasn't necessarily the shortest as it tries to reach minimize the difference between the robot and the target location first in the x, y then z direction. I tried to optimize the former algorithm without adding too much complexity by implementing the previous algorithm using different orders and permutations of x,y,z (xyz, xzy, yxz, yzx, zxy, zyx). The path chosen is the one with smaller number of steps. #### [Frep Build](180521_frep/index.html)

The desired shape representation chosen was [frep](https://en.wikipedia.org/wiki/Function_representation) (functional representation).

- An object as a __point set__ in space is defined by a __function__ of point coordinates f(x_{1},x_{2},...,x_{n}) which is evaluated at the given point by a procedure traversing a tree structure with **primitives in the leaves** and **operations in the nodes** of the tree. - The points with f(x_{1},x_{2},...,x_{n}) ≥ 0 belong to the object. - The points with f(x_{1},x_{2},...,x_{n})<0 are outside of the object. - The point set with f(x_{1},x_{2},...,x_{n})=0 is called an *isosurface*.

In the next section I will explain the order by which the voxels were built. #### [Building Sequence](180521_order/index.html)

The building sequence of the voxels is very important in order to avoid deadlocks which will result in incomplete shapes. The voxel building order is as follows: > **Given** *an frep* >>**for** each *Z slice* >>> find voxel with largest frep value

>>> **for** *all voxels in this Z level* >>>> divide them into different ranks based on distance of the voxel with the largest frep value >>> **end** >> **end** > **end** This insures that all built voxels will be neighboring to already built ones.

For a single robot, the construction logic is as follows: > start with z value equals 0 and rank equals 0

> **while** not all voxels are built >> **if** *robot is at start location and loaded* >>> **for** *all voxel with current rank and z value* >>>> find closest one >>> **end** >>> go build voxel there

>>> update current rank and/or z slice

>>> return to home location

>> **end** > **end** #### [Bill-e Swarm](180521_frep_building_multiple_robots/index.html)

For multiple robots, the construction logic is similar to one robot construction. However, to avoid collision, at each step the robots check if there isn't another robot standing at the step. If there is then wait and try again. #### Underlying Assumptions It is important though to mention the underlying assumptions for the robot construction.

>- The voxels are passive inert voxels and send no data to the robot

- The frep calculation and division of voxel based on rank is done on a central

- Each robot is initially given the following information

* its legs positions and up vector

* its start/home location (where it can reload)

* the desired shape to be built in the following structure:

- A 3d array of vectors a[i][j][k]: where i is the Z slice, j is the voxel rank based on the frep and k is index of voxel in an array (k isn't important as the order for building voxels with same rank isn't important) * the legs' location of each of the other robots * an empty 3d binary grid of voxel space which will be later filled by built voxels * the current Z and rank (now 0) - After each built voxel the robot broadcasts the following information to the rest of the robots * the updated voxel grid with the built voxel * the updated Z slice and rank (this can be later removed but will cause more computation for the robots) - At each step * it updates its legs position and up vector * the robot broadcasts its location for other robots to update it #### Points to Change Improve/Explore - Do not make the start/loading location for each robot set from the beginning, change it so once the robot builds a voxels then just goes to the nearest loading point - Currently, each robot plans its path and steps which will require for the robots to have high computational power, try to find a more sophisticated path planing algorithm with minimum calculation maybe by trying to have a set path or have the calculations centralized ----- ### Prior Work #### Assembly Sequence The first variable explored was the sequence in which the voxels will be assembled. In this simulation, a functional representation (frep) of a hollow cube was given as an input as well as the starting point. Getting the optimum construction sequence could be based on multiple parameters like the voxel storage location and structural stability.

An extra optimization layer should be added afterwards based on Bill-e/multiple Bill-es' movements. Ideally, having a __Arep__ algorithm that describe the geometry would make more use to the assembly sequence. #### Starting Points In order to speed-up and parallelize the process, the box of robots and storage are deployed in multiple locations around the structure and based on the distance the shape assembly is divided between multiple robots.

The method will eventually nt be used as with the accumulation of error which might make it hard for the parts to register together at the end. #### Path Planning The next step I am working on is, based on a given assembly sequence, the path planning of one or multiple Bill-e's around the structure. The algorithm for finding the shortest path is complete and I am the movement of multiple robots with successful obstacle avoidance. #### Voxels Storage Location The optimization of the voxels' storage location is very important to decrease, the traveling time. Here I am gonna study the effeciency of different storage strategies either central, localized, hierarchical... ------- ### Bill-e 1.5 ### Design The redesign and fabrication of Bill-e using the Jake's [newly designed small rotary axis](https://gitlab.cba.mit.edu/jakeread/smallrotary).

### Communication ### Communication and Obstacle Avoidance Having an closeup animation of Bill-e's movement, different communication strategies (passive, implicit, explicit) will be studied to find and a matrix of different stragies with pros and cons will be generated. ### Communication and Task Allocation The next steps will be exploring the communication strategies of multiple Bill-es, as well as the task allocation of the robot (Centralized, Hierarchal, Decentralized, hybrid,..). ### Controlling Bill-e through Mods The last step would be to do a demo of controlling/sending tasks to two three Bill-es and seeing them in action. -----