2.1. Body and motors

Mechanical components of the Arachne Bots were obtained from the commercially available Spider toy robot by HEXBUG [46]. The HEXBUG’s Spiders are six-legged arthropods that are powered using two DC motors. The Arachne Bots’ controlled DC motors control forward motion and heading. Figure 1 shows the front view of an Arachne Bot. HEXBUG is a consumer robotics line developed by Innovation First International to complement the VEX Robotics Design System [47]. In January 2023, Spin Master Corp. acquired the HEXBUG brand, expanding its portfolio of creative robotic technology.

Figure 1.

Front view of the arachne bot. The main body is obtained from HEXBUG’s toy robot, spider. A protoboard with a small footprint is placed on top of the robot’s chassis. The protoboard mounts the wireless microcontroller. The latter generates the control signals that operate the robot’s motion.

The frame of the HEXBUG Spider was selected due to its engaging bio-inspired appearance with the objective of stimulating the interest of younger audiences. The robot’s hexapedal locomotion can accommodate mildly uneven terrains, exceeding many other centimeter-scaled, hard-wheeled, mobile robots. However, the system is versatile enough to support different types of drive systems, such as differential wheels or steering configurations. An alternative commercially available differential drive robotic chassis, that was used for the system, can be seen in Fig 2.

Figure 2.

The wireless microcontroller of the arachne bot is attached to a differential drive chassis.

2.2. Wireless microcontroller

Each Arachne Bot is remotely controlled by the panStamp low-power wireless microcontroller [48]. The panStamp was selected due to its low cost, small footprint, and radio capabilities. It is programmed from the Arduino open-source Integrated Development Environment (IDE), which incorporates numerous libraries that can accommodate low-level operations. A significant volume of documentation and code is accessible online for the Arduino, which has been produced by the large community that supports this platform.

Adruino’s easy-to-use tools and programming language significantly reduce the development time of the Arachne System, making it accessible to users with limited experience in computer engineering. The second significant advantage of the panStamp is its ability to function as a transceiver rather than only a transmitter or receiver. To this end, the control algorithms can be executed from a central supervisory controller or distributively between the wireless mobile nodes. The ability of the Panstamps to function as either simple transmitter-receiver pairs, or as a more complex network, is an essential strength of the Arachne System. These varied capabilities make the platform accessible for researchers or students with limited communication experience, while still allowing for complex communication networks.

Central to the panStamp is an $8\,{\textrm{MHz}}$ Atmel Atmega 28P MCU. RF communication (frequency: $868/915\,{\textrm{MHz}}$ , baud rate: $38400$ ) is integrated using a Texas Instruments CC1101 RF interface with a line-of-sight range of up to $200\,{\textrm m}$ .

2.3. Webcam-based agent tracking

Each Arachne Bot is tracked using Roborealm [49], a commercially available visual software application. The overhead camera captures the top view of the planar workspace containing the Arachne Bots. The software is able to track predetermined markers known as fiducials. The fiducial marker is placed on top of the rigid bodies (Arachne Bots or objects), parallel to the plane, in order to be fully visible by the overhead camera. The visual tracking system serves as a virtual Global Positioning System (GPS), localizing each Arachne Bot in the workspace (arena). The rate at which the pose (position and heading) measurements are captured ranges between $20$ to $30\,{\textrm{fps}}$ . These data are then further broadcasted to each Arachne Bot at a rate of $100\:\,{\textrm{Hz}}$ . The area Roborealm scans is approximately $3{\textrm m}\times 1{\textrm m}$ . However, the size of the viewed area can be controlled by changing the camera’s vertical position. The testing setup, including the camera and the robots, is shown in Fig. 3.

Figure 3.

Camera apparatus and testing area. In the existing system, the overhead camera is placed approximately $1.6\;{\textrm m}$ from the floor resulting in a $3\,{\textrm m}\times 1\,{\textrm m}$ visible arena.

In the Arachne System, Roborealm transmits the pose measurements to each agent individually through a Python script that is executed to a central panStamp transmitter. The overhead video sensor used in the experiments was an inexpensive Logitech Photo ID webcam. A personal license for Roborealm costs $\$49.95$ , and an academic license is even less costly with a price of $\$39.95$ . The Roborealm software, overhead camera, and central panStamp transmitter were connected to a laptop computer. The central computer collects the pose data of each robot and transmits this information to each robot. In a centralized configuration (mission, scenario, or experiment), the central computer executes the supervisory controller controlling the individual agents.

2.3.1. Electronics

A Texas Instruments DRV8833 motor driver commands the motion of the Arachne Bots. This PWM-based motor driver is ideal due to the integrated over-current and over-temperature protection circuit, and its wide range of operational voltages. The motor driver controls both DC motors with a voltage range between $2.7\,{\textrm V}$ and $10.8\,{\textrm V}$ . The PWM inputs to the DRV8833 motor driver control the motor speed and direction. The Arachne Bots are powered by lithium-ion polymer (LiPo) batteries that incorporate an onboard charging station. The charging station also includes an LED power indicator light and a power switch.

The LiPo batteries used with the Arachne Bots output $3.7\,{\textrm V}$ from a supply of $850\,{\textrm{mAh}}$ , which offers approximately three to four hours of battery life. The battery chargers can accept power via a micro-USB port at either $3.3\,{\textrm V}$ or $5\,{\textrm V}$ . The batteries themselves can plug into the chargers using a JST and receive a maximum current of $100\,{\textrm{mA}}$ . If on-board charging is unnecessary for a particular project, this circuit could be removed to reduce cost. Table I outlines the individual parts and their cost for a single Arachne Bot. The schematic for the standard Arachne Bot board is illustrated in Fig. 4.

Table I.

Electronic components and their cost for a single Arachne Bot.

Figure 4.

Schematic of the standard Arachne Bot board. The main components are the panStamp wireless microcontroller, the DRV8833 motor driver, and the voltage regulator.

Unlike the vast majority of existing small-scale multi-robot systems, the entire manufacturing process of the Arachne Bots is performed on a simple through-hole protoboard. Therefore, there is no need for machine assembly or extensive soldering experience. Any home user with access to a basic soldering kit could easily assemble an Arachne Bot without any additional training. This not only helps reduce the cost of construction but it also allows complete beginners to assemble Arachne Bots with ease.

3.1. Hardware overview

The IRB board consists of eight emitter-receiver pairs operating at a wavelength of $940\,nm$ arranged on top of, and below the board, at $45^{\circ }$ intervals as shown in Fig. 5. The SEN-00241 receivers are straight-facing and have an operational field-of-view of approximately $45^{\circ }$ . This allows for the beacons to detect $360^{\circ }$ of infrared light (separated to eight sectors). When an infrared source is in range, exactly one receiver will detect the signal with little to no dead zones or overlap.

Figure 5.

Representation of the IR Beacon Board. In our design, the board acts as an interface shield, connecting the microcontroller to the power source and the two motors.

The 7OED-EL-1L2 emitters are high-powered infrared LEDs chosen due to their high intensity and low power consumption. With the microcontroller output of $3.3\,{\textrm V}$ , the receivers can detect the emitters at distances of up to $15\,{\textrm{cm}}$ , which is an ample range for a $3\,{\textrm{cm}}$ by $3\,{\textrm{cm}}$ robot. The emitters are installed under the beacon facing outwards. Since the receivers and emitters are placed on top of, and under the board, respectively, each pair can be mounted at the same orientation on the beacon without the risk of an agent detecting itself. This setup also allows the boards to detect collisions with reflective walls and surfaces, as well as the imminent occurrence of other agents.

The emitters are connected in parallel to one digital output pin of the microcontroller. Using the built-in analog voltage sensing capabilities of the unit, the sensor readings can range from $0$ to $1023$ with a sampling rate of $10\,{\textrm{kHz}}$ . These measured values correspond to a voltage interval from $0\,{\textrm V}$ to $5\,{\textrm V}$ , meaning that each point is equivalent to approximately $4.9\,{\textrm{mV}}$ . Low and high readings correspond to high and low-intensity signals, respectively.

The board is powered by two lithium-polymer batteries with terminal voltages of $3.7\,{\textrm V}$ . The full $7.4\,{\textrm V}$ supply is used to power the infrared receivers and motor driver which both require at least $5\,{\textrm V}$ to operate accurately. The board also contains a voltage regulator which reduces the voltage to $3.3\,{\textrm V}$ in order to power the microcontroller. The full wiring schematic for the IRB can be found in Fig. 6.

Figure 6.

Wiring schematic for the Arachne Bot IRB board. This extension module is equipped with emitter-receiver pairs that provide each Arachne Bot on-board perception capabilities. Each bot can detect adjacent obstacles and agents.

Even though printed electronics were used for the IRB board, the same circuit can be easily assembled with a simple through-hole protoboard (much like the standard Arachne Bot board) without sacrificing size or usability. Table II shows a price breakdown of each individual component of the Arachne Bots IRB.

Table II.

Electronic components and their cost of an arachne bot with the IRB board.

3.2. Measurements

Three tests were performed to ensure the accuracy and usability of the IRB hardware. The first two tests investigate the localization capabilities of the IRB boards. The use of a local coordinate system requires two types of measurements: range and bearing. Range determines how far away a neighboring agent is located, and bearing determines its relative heading. A third test was also performed to determine the amount of noise or interference detected by the infrared receivers.

Each test was performed using two IRB boards on a flat surface. In order to measure range, an emitter beacon was kept stationary while a receiver beacon was moved apart from the emitter incrementally. The range measurements were performed at a constant bearing with the two North emitters of the two beacons facing each other. The receiving beacon was then moved back from $0\,{\textrm{cm}}$ to $18\,{\textrm{cm}}$ at increments of $1\,{\textrm{cm}}$ . Figure 7 illustrates the experiment with corresponding results presented in Fig. 8. All graphical data are inverted for ease of viewing, meaning that a low reading corresponds to a low-intensity signal. The microprocessor uses a nonlinear quantized scale to determine the range in centimeters. Figure 9 shows the quantized values that the microprocessor uses along with the raw analog voltage reading attained.

Figure 7.

Diagram of range test. The receiver beacon (white) is moving apart from the emitter beacon (grey), in increments of $1\,{\textrm{cm}}$ while retaining constant heading.

Figure 8.

Range measurements from the receivers of the IRB board.

Figure 9.

Range map of the IRB board. The distance readings are not linear. In the chart, the dark line represents the analog voltage readings on the north pin, while the shaded areas mark the quantized distances which the microprocessor translates these readings from.

The verification of the direction bearing was performed at a distance of $6\,{\textrm{cm}}$ with the emitting board kept stationary, while the receiving board was rotated in $10^{\circ }$ increments through a full rotation. The experiment procedure is illustrated in Fig. 10, and the receiver readings can be found in Fig. 11.

Figure 10.

Diagram of bearing test. The receiver board (white) is rotated in increments of $10^{\circ }$ relative to the emitter board (gray). The relative range between the two boards is kept constant to $6\,{\textrm{cm}}$ .

Figure 11.

Bearing measurements from the receivers of the IRB board.

The final experiment was performed using a method that was very similar to the range test. The boards were placed on a level surface facing one another and starting at a distance of $1\,{\textrm{cm}}$ . From there, they were gradually separated in intervals of $3\,{\textrm{cm}}$ . At each of these distances, the analog voltage reading was recorded about $1500$ times over a period of around $3$ min. The results of this experiment prove that there is very little noise or interference. In fact, not even one point of deviation was measured over distances up to $13\,{\textrm{cm}}$ . These results indicate that the beacons detect very little noise, removing the need to filter the infrared sensor signals.

4.1. Arachne Bot kinematics

The legs of the Arachne Bot are equivalent to a nonslipping driving wheel. Its steerability is controlled by the rotation of its torso. The Arachne Bot maneuverability is similar to a differential-drive or unicycle-like robots. The robot’s kinematics constitute a nonholonomic system that has a first-order, non-integrable constraint [Reference Kanayama, Kimura, Miyazaki and Noguchi50]. As a result, the Arachne Bots’ motion cannot be described as omnidirectional.

Two reference frames are introduced to illustrate the Arachne Bots’ planar kinematic equations. The reference frames are defined using the center and two orthogonal unit vectors. First, the fixed inertial (global) reference frame is $\mathcal{F}_{I}=\left \{ O_{I},\vec {i}_{I},\vec {j}_{I}\right \}$ . The second reference frame is a moving body-fixed reference frame, defined as $\mathcal{F}_{B}=\left \{ O_{B},\vec {i}_{B},\vec {j}_{B}\right \}$ . This reference frame origin, $O_{B}$ , is the center of gravity body (CG) of the Arachne Bot. A traditional right-handed Cartesian coordinate system $\left \{ \vec {i}_{B},\vec {j}_{B}\right \}$ is constructed using a vector, $\vec {i}_{B}$ , which points forward and a vector $\vec {j}_{B}$ which points to the left aft side as shown in Fig. 12.

Figure 12.

The polar coordinate system, inertial and body-fixed reference frames, and the heading angles defined from cartesian to polar coordinate transformation. The angle $\sigma$ represents the LOS of the robot.

The posture vector, $p=\left [x;y;\psi \right ]$ , fully defines the robot’s planar 2-D motion. Here, $x$ , $y$ represent the inertial frame Cartesian coordinates, and the robot’s heading is $\psi$ . By definition, the two frames $\mathcal{F}_{I}$ and $\mathcal{F}_{B}$ are aligned when $\psi =0$ . The combination of angular velocity, $\omega$ , and linear velocity, $v$ , controls the robot’s locomotion. The standard unicycle-like robot kinematics are

(1) \begin{align} \dot {x} & =v\cos \psi ,\nonumber \\ \dot {y} & =v\sin \psi ,\nonumber\\ \dot {\psi } & =\omega . \end{align}

The linear and angular velocities are controlled by regulating the voltage of the two DC motors on board the Arachne Bot. For simplicity, we assume a static map between the velocities of the robots and its motors, that is,

(2) \begin{align}&\, v =K_{v}V_{{{legs}}}, \end{align}

(3) \begin{align}& \omega =K_{\omega }V_{{{torso}}}, \end{align}

where $K_{v}$ and $K_{\omega }$ are positive gains, and $V_{{{legs}}}$ and $V_{{{torso}}}$ are the voltages that regulate the motion of the legs and the torso of the Arachne Bot, respectively.

4.2. Set-point control (move to a target location)

The stabilization challenge of non-omindirectional robots has been thoroughly investigated [Reference Kanayama, Kimura, Miyazaki and Noguchi50–Reference Samson and Ait-Abderrahim53]. The goal is to move the robot to the null posture $[0;0;2n\pi ]$ with $n\in \mathbb{Z}$ . Robot stabilization with non-holonomic constraints is presented in Kolmanovsky’s survey paper [Reference Kolmanovsky and McClamroch54].

In the context of the Arachne System, set-point control is considered a less analytically complex modulation of the stabilization law. Hereafter, we only need the inertial reference frame, $\mathcal{F}_{I}$ , to define coordinates. The goal is to have the robot navigate to a reference target location $\left (x_{t},y_{t}\right )\in \mathbb{R}^{2}$ in the 2-D plane, referred to as the set-point or waypoint. The robot is not required to have a certain heading when it reaches the target set-point.

Our subsequent algorithms for collision avoidance and object manipulation use a high-level paradigm that calculates reference waypoints for robotsFootnote ² in a discrete-time or -event manner. This method is standard for the “task” or “mission” control layer, generating commands that define a velocity profile or waypoint. The subordinate set-point control algorithm ensures the robot converges on these waypoints within a practical timeframe by adjusting its linear and angular velocities. The lower-level motor and steering control layer, as delineated in (2) and (3) for the Arachne System, maps linear and angular velocity profiles into voltage signals for the robot’s motor(s) and steering mechanism. This foundational layer aligns with the robot’s electromechanical configuration that defines its maneuverability [Reference Siegwart and Nourbakhsh55]. This hierarchical control architecture enables the high-level algorithms, specifically those for collision avoidance and object manipulation, to be not only applicable to the Arachne System but also adaptable and hardware-agnostic with respect to the mobile robot platforms on which they are implemented.

We adopt a modified version of the set-point control law presented in ref. [Reference Lee, Cho, Hwang-Bo, You and Oh56]. Essentially, the algorithm is a formal version of the intuitive principle of “turn and move-towards-the-target” approach. The controller is expressed with respect to the polar coordinates, instead of the standard Cartesian form:

(4) \begin{alignat} {2} \rho & =\sqrt {\left (x-x_{t}\right )^{2}+\left (y-y_{t}\right )^{2}} & \;\;\; & \psi _{t}=\textrm {atan2}\left (y_{t}-y,x_{t}-x\right ). \end{alignat}

Here, the coordinates $\rho$ and $\psi _{t}$ represent the relative distance and heading, respectively, between the Arachne Bot and the target. The error between the robot’s current heading and the target is $\alpha =\psi _{t}-\psi$ . The three coordinate systems are illustrated in Fig. 12.

The set-point control problem requires that the coordinates $\left (\alpha ,\rho \right )$ will asymptotically converge to one of the equilibrium points $\left (0,2n\pi \right )$ with $n\in {{\mathbb{Z}}}$ as $t\rightarrow \infty$ . This requires that the target is aligned with the heading of the robot ( $\alpha \rightarrow 2n\pi$ ), and that the robot converges to the target ( $\rho \rightarrow 0$ ). After the coordinates change (from $x$ , $y$ to $\rho$ , $\alpha$ ), the robot’s kinematics become

(5) \begin{align}&\,\,\, \dot {\rho } =-\cos \alpha \cdot v, \end{align}

(6) \begin{align}& \dot {\alpha } =\sin \alpha \cdot \frac {v}{\rho }-\omega . \end{align}

A quick inspection of the kinematics illustrates that a singularity occurs when $\rho =0$ . This incidence takes place due to the ambiguity introduced by the definition of $\texttt {atan2}({\cdot },{\cdot })$ when $\left (x,y\right )=\left (x_{t},y_{t}\right )$ . When the control law is implemented, this singularity is eliminated. Furthermore, in practical, real-world implementations, algorithm execution is terminated once the robot enters a circular disk of the set-point of radius $R_{t}$ . The feedback control law is similar to that presented in ref. [Reference Wilson, Glotfelter, Wang, Mayya, Notomista, Mote and Egerstedt35]:

(7) \begin{align} v & =K_{\rho }\cos \alpha \cdot \rho ,\nonumber \\ \omega & =K_{\rho }\cos \alpha \cdot \sin \alpha +K_{\alpha }\sin \alpha , \end{align}

where $K_{\rho }$ and $K_{\alpha }$ the positive valued gains. This differs from [Reference Wilson, Glotfelter, Wang, Mayya, Notomista, Mote and Egerstedt35] because $K_{\alpha }\sin \alpha$ is used rather than the simpler proportional term $K_{\alpha }\alpha$ . In our approach, all angles are channeled through trigonometric functions to eliminate the discontinuous jumps that take place by the definition of $\psi _{t}$ and the measurement range of $\psi$ .

The stability of the control law is established using the following Lyapunov function:

\begin{equation*} V(\rho ,\alpha )=\frac {1}{2}\rho ^{2}+\left (1-\cos \alpha \right ) \end{equation*}

which is positive definite for $\rho \neq 0$ and $\alpha \neq 2n\pi$ where $n\in \mathbb{Z}$ . Taking the derivative of $V(\rho ,\alpha )$ with respect to time along the system trajectories yields:

\begin{align*} \dot {V} & =-\cos \alpha \cdot \rho \cdot v+\sin \alpha \cdot \left (\sin \alpha \cdot \frac {v}{\rho }-\omega \right )\\ & \stackrel {\text{(7)}}{=}-K_{\rho }\cos ^{2}\alpha \cdot \rho ^{2}-K_{\alpha }\sin ^{2}\alpha \lt 0\\ &\text{ for }\rho \neq 0\text{ and }\alpha \neq 2n\pi \text{, }n\in \mathbb{Z}. \end{align*}

The derivative of $V(\rho ,\alpha )$ is negative definite. The resulting equilibrium points $\left (0,2n\pi \right )$ , with $n\in \mathbb{Z}$ , are asymptotically stable.

When the heading error equals $2n\pi$ , the robot aligns with the target. According to the control law in (7), the advancement $v$ turns negative if $\cos \alpha \lt 0$ . When that happens, the Arachne Bot reverses until its heading aligns with the target. To ensure forward movement only, conditional logic is applied, enabling positive advancement when the target falls within the robot’s line-of-sight (LOS), represented by the angle $\sigma \in \left (0,\;\frac {\pi }{2}\right ]$ . In this case, pure rotation without advancement occurs if $\left |\alpha \right |\gt \sigma$ or $\cos (\alpha )\gt \cos (\sigma )$ , with control velocities as follows:

\begin{equation*} v=0; \quad \omega =\begin{cases} -\omega _{0}, & \sin \alpha \geq 0,\\ \omega _{0}, & \text{otherwise}, \end{cases} \end{equation*}

where $\omega _{0}\gt 0$ denotes a constant angular velocity. When $|\alpha |\lt \sigma$ , the feedback control law reverts to (7), ensuring a positive (forward) advancement $v$ as $\cos \alpha \gt 0$ in this heading error, $\alpha$ range. The pseudocode for this set-point control law is detailed in Algorithm 1.

4.3. Collision avoidance

Collision avoidance is frequently encountered in real-world multi-robot applications. Deconfliction algorithms should be used by each robot on the team to guarantee collision-free missions. These collision avoidance algorithms can take many forms including optimization and force fields [Reference Kuchar and Yang57]. We present an intuitive, distributed deconfliction algorithm to validate the collaborative behavior and group constraints of Arachne Bots.

Consider a workspace containing $n$ mobile robots (Arachne Bots), mathematically represented as the index set $\mathcal{N}=\left \{ i=1,\ldots ,n\right \}$ . A target location $\left (x_{t}^{i},y_{t}^{i}\right )\in \mathbb{R}^{2}$ , $i\in \mathcal{N}$ , is prescribed to each robot. When two robots, $i$ and $j$ , are separated by a distance that is less than some critical value, $R_{c}$ , a conflict has occurred:

\begin{equation*} \rho _{i,j}\leq R_{c}\textrm{, where}\quad \rho _{i,j}=\sqrt {\left (x^{i}-x^{j}\right )^{2}+\left (y^{i}-y^{j}\right )^{2}}. \end{equation*}

An intermediate, reference location for each robot, $\left (x_{r}^{i},y_{r}^{i}\right )\in \mathbb{R}^{2}$ , $i\in \mathcal{N}$ , is defined within the collision avoidance algorithm. The following equality $\left (x_{r}^{i},y_{r}^{i}\right )=\left (x_{t}^{i},y_{t}^{i}\right )$ , holds true when no conflict occurs. At each execution instant, robot $i$ determines the set of conflicting robots, which is defined as $\mathcal{D}_{i}=\left \{ j\in \mathcal{N}-\left \{ i\right \} :\rho _{i,j}\leq R_{c}\right \}$ . In a real-world application, the set $\mathcal{D}_{i}$ can be identified by an onboard proximity sensor on robot $i$ , such as the infrared beacon described in Section 3. If a single sensor measures the absolute position of each robot, the set $\mathcal{D}_{i}$ is determined by calculating the relative distance between each robot $i$ and the remaining $n - 1$ robots in the swarm.

Robot $i$ ’s relative heading angles with respect to (conflicting) robots belonging to $\mathcal{D}_{i}$ are

(8) \begin{equation} \psi _{i,j}=\textrm{atan}2\left (y^{j}-y^{i},x^{j}-x^{i}\right ). \end{equation}

The above definition yields $\psi _{j,i}=\psi _{i,j}-\pi$ . Note that robot $i$ ’s reference heading to the target (4) is by definition

(9) \begin{equation} \psi _{t}^{i}=\textrm{atan}2\left (y_{t}^{i}-y^{i},x_{t}^{i}-x^{i}\right ). \end{equation}

The algorithm partitions the radius $R_{c}$ circular disk with origin at robot $i$ , denoted by $A_{i}$ , into $S$ equal circular sectors, $S_{i}^{k}$ , $k=1,\ldots ,S$ , with central angles $s=2\pi /S$ . When a conflict arises, indicated by a nonempty set $\mathcal{D}_{i}$ , the $S$ circular sectors are sequentially scanned to locate the first one that is empty, meaning it does not contain any conflicting robots. The first sector, $S_{1}$ , is defined such that its bisection is aligned with the line that connects robot $i$ with its target location, and the reference location is set equal to the target location, i.e., $\left (x_{r}^{i},y_{r}^{i}\right )=\left (x_{t}^{i},y_{t}^{i}\right )$ . Assuming that the first sector is empty of conflicting robots, robot $i$ moves toward the target location. Otherwise, the second sector is scanned, and if, in turn, this sector is empty, the reference location becomes the point where the bisection of $S_{2}$ intersects the margin of $A_{i}$ .

Overall, the scanning sequence continues until a sector $S_{i}^{k}$ is found free of conflicting robots in $\mathcal{D}_{i}$ . When this is the case, the reference point of robot $i$ , $\left (x_{r}^{i},y_{r}^{i}\right )$ , is set equal to the intersection point of the bisection of the sector $S_{i}^{k}$ with the circular margin of $A_{i}$ , such that we have

(10) \begin{align} x_{r}^{i} & =x^{i}+R_{c}\cos \left [\psi _{k}^{i}\right ]\: & y_{r}^{i}=y^{i}+R_{c}\sin \left [\psi _{k}^{i}\right ], \end{align}

where

(11) \begin{equation} \psi _{k}^{i}=\psi _{t}^{i}+\left (k-1\right )\frac {2\pi }{S}\text{ for }k\in \mathcal{N} . \end{equation}

Figure 13 shows schematically the sector partitions of $A_{i}$ . Segment $S_{k}^{i}$ is deemed collision free when for $j\in \mathcal{D}_{i}$ we have

(12) \begin{equation} \cos \left (\psi _{i,j}-\psi ^{i}\right )\lt \cos \left (\pi /S\right ). \end{equation}

Figure 13.

The conflict disk, $A_{i}$ , characterized by a radius $R_{c}$ , is segmented into $S$ circular sectors. During each iteration of the algorithm, these sectors are examined in sequence to locate a sector devoid of collisions. The sector identified as collision-free, denoted as $S_{i}^{k}$ , where $k\in \{1,\ldots ,S\}$ , is designated to include the reference location $(x_{r}^{i},y_{r}^{i})$ .

When a robot finds itself encircled by conflicting agents, meaning all circular sectors are occupied, it opts to remain stationary by setting its coordinates $(x_{r}^{i},y_{r}^{i})$ to its current location $(x^{i},y^{i})$ . The choice of how many partitions $S$ to divide the disk $A_{i}$ into is a critical design parameter that influences the algorithm’s behavior and performance. A higher number of partitions enhances the probability of identifying an unoccupied sector for the robot to move toward, yet it concurrently escalates the algorithm’s computational load and run time.

Our approach delineates a specific movement strategy for the robots: each seeks the earliest unoccupied “corridor” to its right for navigation. This prescribed movement pattern induces a collective, macroscopic behavior akin to the counterclockwise flow observed in a cyclone, leading the swarm, when observed as a whole, to exhibit rotational motion. Robots situated on the perimeter of this cyclonic formation are thus able to locate a clear path toward their designated targets. The pseudocode detailing this collision avoidance mechanism is presented in Algorithm 2.

The algorithm can be executed either centrally, in a supervisory controller, or distributively, on each robot. In the central execution, the supervisory controller receives the coordinates of all robots and determines the reference coordinates for each robot to ensure collision-free motion. In the distributed execution, each robot independently uses its global coordinates and sensory data, such as from a proximity sensor (e.g., the IRB board), to compute its desired reference coordinates.

In terms of complexity, the central execution has a time and space complexity of $O(nS)$ , where $n$ is the number of robots and $S$ is the number of sectors. Conversely, the distributed execution reduces the complexity to $O(S)$ .

4.4. Object manipulation

Incorporating object interaction capabilities into mobile robots significantly enhances their functionality and adaptability in diverse environments. We describe an algorithmic procedure that enables Arachne Bot to perform a form of object manipulation. Specifically, the algorithm allows a planar mobile robot to push a round object from any initial position to a designated target position, $\mathcal{T}:\left (x_{t},y_{t}\right )\in \mathbb{R}^{2}$ .

During object manipulation, the robot persistently re-positions itself so that the object lies between the robot and the target. It then walks toward the target, pushing the object as it goes. Let $\mathcal{O}:\left (x_{o},y_{o}\right )\in \mathbb{R}^{2}$ denote the geometric center of the object and its coordinates. The contact point is determined by a position vector from the object to the target. This position vector, along with its unit vector, is given by

\begin{equation*} N_{o}=\left [\begin{array}{cc} x_{o}-x_{t}; & y_{o}-y_{t}\end{array}\right ]\quad \textrm {and}\quad \hat {n}=\left [\begin{array}{cc} n_{x}; & n_{y}\end{array}\right ], \end{equation*}

where $\hat {n}=N_{o}/\left \Vert N_{o}\right \Vert$ . The point of contact, $\mathcal{C}$ , between the object and the robot is determined by the unity vector $\hat {n}$ as well as a positive coefficient $\mu _{o}$ , representative of the radius (or size) of the object. The position of $\mathcal{C}$ , in the inertial reference frame is given by

\begin{equation*} \mathcal{C}:\left (C_{x},C_{y}\right )=\left (x_{o}+\mu _{o}\cdot n_{x},y_{o}+\mu _{o}\cdot n_{y}\right ). \end{equation*}

To circumvent an untimely collision with the object before reaching point $\mathcal{C}$ , the robot’s reference point is adjusted to first direct it toward an inline point, $\mathcal{I}$ , prior to proceeding to $\mathcal{C}$ . Similar to $\mathcal{C}$ , $\mathcal{I}$ is located along the line that connects the target with the object. However, $\mathcal{I}$ is positioned further from the target compared to $\mathcal{C}$ . The position of $\mathcal{I}$ is determined analogous to $\mathcal{C}$ . The location of $\mathcal{I}$ is defined as

\begin{equation*} \mathcal{I}:\left (I_{x},I_{y}\right )=\left (x_{o}+\mu _{I}\cdot n_{x},y_{o}+\mu _{I}\cdot n_{y}\right ), \end{equation*}

where the coefficient $\mu _{I}$ , which is largest than $\mu _{o}$ , specifies its distance from the object.

When the robot commences the manipulation procedure from a position between the target and the object, it is instructed to execute a sidestep maneuver to one of two auxiliary reference points, $\mathcal{A}$ or $\mathcal{B}$ , situated in the aft vicinity of the object. This maneuver is a precursor to the previously outlined procedure. Points $\mathcal{A}$ and $\mathcal{B}$ are defined with the same safe distance $\mu _{I}$ of $\mathcal{I}$ such that no premature collisions occur when the robot approaches the object. The waypoints $\mathcal{A}$ and $\mathcal{B}$ are given by

\begin{align*} \mathcal{A}:\left (A_{x},A_{y}\right ) & =\left (x_{o}-\mu _{I}\cdot n_{x},y_{o}+\mu _{I}\cdot n_{y}\right )\\ \mathcal{B}:(B_{x},B_{y}) & =\left (x_{o}+\mu _{I}\cdot n_{x},y_{o}-\mu _{I}\cdot n_{y}\right ) \end{align*}

Figure 14 illustrates all the waypoints described so far. The sequence of waypoints that the Arachne Bot moves through is governed by the angle, $\beta _o$ , which is determined by the difference between the line segment connecting the robot to the object and the one connecting the target to the object. This angle $\beta _o$ is calculated as the difference between the relative angle of the object with respect to the robot, $\phi _o$ , and the relative angle of the object with respect to the target, $\theta _o$ . These angles are computed as follows:

\begin{align*} \theta _{o}&=\textrm {atan2}\left (y_{o}-y_{t},x_{o}-x_{t}\right ),\\ \phi _{o}&=\textrm {atan2}\left (y_{o}-y,x_{o}-x\right ), \end{align*}

and

\begin{equation*} \beta _{o}=\phi _{o}-\theta _{o}. \end{equation*}

Figure 14.

Representation of waypoints and relative angles involved in the object manipulation algorithm.

The choice of the waypoint sequence – either ( $\mathcal{I}$ , $\mathcal{C}$ ) or ( $\mathcal{A}$ or $\mathcal{B}$ , $\mathcal{I}$ , $\mathcal{C}$ ) – depends on the robot’s initial position relative to the quadrants defined by the line through points $\mathcal{A}$ and $\mathcal{B}$ and the line connecting the target with the robot, as depicted in Fig. 15.

Figure 15.

Halfplanes and their corresponding conditions determining the sequence of waypoints for the object manipulation algorithm. The selection between waypoints $\mathcal{A}$ or $\mathcal{B}$ is dictated by the sign of $\sin \beta _o$ .

If the robot starts in the half-plane opposite the target, demarcated by $\mathcal{A}$ and $\mathcal{B}$ , the condition $\cos \beta _{o}\lt 0$ applies, and the robot adheres to the sequence ( $\mathcal{I}$ , $\mathcal{C}$ ). Otherwise, it follows the sequence ( $\mathcal{A}$ or $\mathcal{B}$ , $\mathcal{I}$ , $\mathcal{C}$ ). The choice between $\mathcal{A}$ and $\mathcal{B}$ as the initial waypoint hinges on the sign of $\sin \beta _o$ ; $\mathcal{A}$ is chosen if $\sin \beta _o\gt 0$ ; otherwise, the sequence starts with $\mathcal{B}$ . The task is deemed completed when the relative distance between the object, $\mathcal{O}$ , and the target, $\mathcal{T}$ , falls below a tolerance threshold, $\epsilon _{t}$ .

The pseudo-code for this procedure is shown in Algorithm 3. At each step of the pseudo-code, a waypoint is generated. The set-point control algorithm, detailed in Section 4.2, is then utilized to guide the robot toward these waypoints.

4.5. Group object manipulation

Advancing from single-robot to multi-robot manipulation, this section presents an algorithm for a team of four Arachne Bots to transport a rectangular box with known dimensions. This algorithm enables the coordinated effort required for the robots to push the box to a specified target location and orientation, represented as $\mathfrak{T}:\left [\mathcal{T},\theta _{t}\right ] \in \mathbb{R}^{2} \times \left [0,2\pi \right )$ where $\mathcal{T}:\left (x_{t},y_{t}\right )\in \mathbb{R}^{2}$ , from any initial configuration of the robots and the box.

The specified challenge merges swarm robotics [Reference Wang and Schwager58] with the classical computational challenge known as the “piano movers” problem [Reference Canny59, Reference Schwartz and Sharir60], which involves moving an object from one point to another within a plane containing geometric constraints, such as walls.

The core strategy involves the robots encircling the box in a calculated, equiangular arrangement to ensure effective caging and transportation. Caging, a method where robots form a perimeter around an object to control its movement, is fundamental for achieving the desired position and orientation [Reference Brown and Jennings61–Reference Yamada and Saito65]. In our approach, the movement toward the target is facilitated through waypoints, which guide the robots through three main phases: pathing (initial positioning), translation (moving towards the target location), and rotation (adjusting to the target orientation). In the subsequent analysis, it is necessary to define an object-fixed frame, denoted as $\mathcal{F}_{B}=\{\mathcal{O},\vec {i}_{B},\vec {j}_{B}\}$ .

The origin of the frame, $\mathcal{O}$ , is positioned at the geometric center of a rectangular box. The basis vectors $ \{\vec {i}_{B}, \vec {j}_{B}\}$ are aligned with the symmetry axes of the box, with $ \vec {j}_{B}$ preferably oriented along the symmetry axis corresponding to the length or longer side of the rectangular object.

Pathing

The pathing phase entails the determination of the robots’ initial approach waypoints in relation to the object, contingent upon the object’s orientation. Initially, we define the orientation angle of the object, $\theta _{b}$ , within the inertial reference frame, leading to the segmentation of the plane into quadrants based on this angle. Subsequently, approach points are delineated at a fixed distance, $\rho _{a}$ , from the object. These points are evenly distributed, with angular increments of $\frac {\pi }{2}$ radians commencing from $\theta _b$ . Figure 16 depicts the four waypoints used to position the robots around the box (object). The approach distance, $\rho _{a}$ , is required to exceed half of the box’s larger dimension – whether width or length – by a factor of at least two.

Figure 16.

Approaching robot waypoints, $\mathcal{L}^{i}$ with $i\in \{1,2,3,4\}$ , around the object during the pathing phase of the algorithm. The robots are distributed around the object in $\pi /2$ increments starting from the object’s orientation $\theta _b$ in the reference frame.

This configuration facilitates the robots’ arrangement around the object, mitigating premature collisions and setting the stage for the initiation of the pushing phase. The calculation of the caging angles is articulated as follows:

\begin{align*} \theta _{s}^{i}&=\text{atan2}(y_{s}^{i}-y_{o},x_{s}^{i}-x_{o})\\ \phi _{s}^{i}&=\theta _{s}^{i}-\theta _{b}\text{, }i\in \{1,2,3,4\}, \end{align*}

where $\theta ^{i}_s$ and $\phi ^{i}_s$ represent the relative angles of the robots with respect to the inertial and object-fixed frames, respectively. The graphical representation of these angles is depicted in Fig. 17.

Figure 17.

Relevant angles for the calculation of the relative angles $\phi ^i_{s}$ of the robots with respect to the box.

The ensuing task of pathing is to allocate the designated approach points among the four robots, considering their initial locations, with the aim of preventing collisions. Toward this end, Algorithm 4 presents the pseudocode of a sorting algorithm designed to achieve this objective. This procedure systematically assigns waypoints to each robot according to its relative orientation, $\phi ^{i}_{s}$ , in relation to the other robots and the object.

Let $\mathcal{O}:\left (\mathcal{O}_{x},\mathcal{O}_{y}\right )\in \mathbb{R}^{2}$ represent the coordinates of the box’s geometric center, and let $\mathcal{L}^{i}:\left (\mathcal{L}^{i}_{x},\mathcal{L}^{i}_{y}\right )\in \mathbb{R}^{2}$ , for $i\in \{1,\ldots ,4\}$ , denote the coordinates of the four approach points to the box, all expressed in the inertia frame. Employing straightforward geometrical principles, the coordinates of the waypoints for approaching the box are determined as follows:

\begin{align*} \mathcal{L}^{i}:\left (\mathcal{L}^{i}_{x};\mathcal{L}^{i}_{y}\right )&=\left [\begin{array}{c} \mathcal{O}_{x}\\ \mathcal{O}_{y} \end{array}\right ]+\left [\begin{array}{c} \rho _{a}\cos \left (\theta _{b}+\frac {\pi }{2}(i-1)\right )\\ \rho _{a}\sin \left (\theta _{b}+\frac {\pi }{2}(i-1)\right ) \end{array}\right ],\;i\in \{1,\ldots ,4\}. \end{align*}

The pathing waypoints $ \mathcal{L}^{i}$ position the robots safely along the symmetry axes of the object, at a distance $ \rho _{a}$ from its geometric center $ \mathcal{O}$ .

Translation

Upon all robots reaching their designated initial approach points, the algorithm progresses to its second phase, focusing on generating waypoints to facilitate the object’s translation by the robots.

The translation phase is bifurcated into two parts: caging and pushing. In the caging part, robots surround the box to form a cross-shaped enclosure, positioning themselves at distances $\rho _{L}$ and $\rho _{W}$ along the box’s length and width symmetry axes, respectively. The caging waypoints, during translation, are

\begin{align*} \mathcal{N}^{i}:\left (\mathcal{N}_{x}^{i},\mathcal{N}_{y}^{i}\right ) & =\left [\begin{array}{c} \mathcal{O}_{x}\\ \mathcal{O}_{y} \end{array}\right ]+\left [\begin{array}{c} \rho _{L}\cos \left (\theta _{b}+\frac {\pi }{2}(i-1)\right )\\ \rho _{L}\sin \left (\theta _{b}+\frac {\pi }{2}(i-1)\right ) \end{array}\right ],\;\text{for }i\in \{1,3\};\\ \mathcal{N}^{i}:\left (\mathcal{N}_{x}^{i},\mathcal{N}_{y}^{i}\right ) & =\left [\begin{array}{c} \mathcal{O}_{x}\\ \mathcal{O}_{y} \end{array}\right ]+\left [\begin{array}{c} \rho _{W}\cos \left (\theta _{b}+\frac {\pi }{2}(i-1)\right )\\ \rho _{W}\sin \left (\theta _{b}+\frac {\pi }{2}(i-1)\right ) \end{array}\right ],\;\text{for }i\in \{2,4\}. \end{align*}

After the caging formation is established, the robots initiate a uniform, parallel motion, moving in unison toward the same direction, to advance the box toward its designated target location $\left (x_{t},y_{t}\right )$ . This movement is facilitated by waypoints generated from a consistent directional vector and the caging waypoints. Adherence to these pushing waypoints by the robots orchestrates the collective movement of the object toward its goal.

The directional vector has a magnitude $\rho _{M}$ and an angle $\theta _{M}$ , which is determined by the bearing from the object’s center to the target location, calculated as follows:

(13) \begin{equation} \theta _{M} = \text{atan2}(y_{o} - y_{t}, x_{o} - x_{t}). \end{equation}

The pushing waypoints, denoted as $\mathcal{M}^{i}$ , are derived by applying the directional vector to the corresponding caging waypoints $\mathcal{N}^i$ as

(14) \begin{equation} \mathcal{M}^{i}:\left (\mathcal{M}_{x}^{i},\mathcal{M}_{y}^{i}\right )=\left [\begin{array}{c} \mathcal{N}_{x}^{i}\\ \mathcal{N}_{y}^{i} \end{array}\right ]-\left [\begin{array}{c} \rho _{M}\cos \theta _{M}\\ \rho _{M}\sin \theta _{M} \end{array}\right ],\text{ for }i\in \{1,\ldots ,4\}. \end{equation}

The depiction of the caging and pushing waypoints, along with the characteristics (magnitude and bearing) of the directional vector that delineates the pushing waypoints, is presented in Fig. 18. The translation phase, encompassing both caging and pushing, persists until the object arrives at its target location. This condition is mathematically satisfied when the distance $\rho _{t}$ between the object and the target is reduced to less than a threshold value $\epsilon _{t}$ , which signifies the permissible distance error tolerance from the target. Once this condition is satisfied, the algorithm advances to its final phase: rotation.

Figure 18.

Geometric configuration elements of the group object manipulation algorithm during the translation phase.

Rotation

In the rotation phase, only two robots, lying in the opposing halfplanes defined by the box’s length symmetry axis, participate in the object manipulation process, while the other two step back and track the box’s orientation.

Assume that indexed units 2 and 4 are designated to the “long” sides of the box; they will be responsible for rotating the box. In this case, robots 1 and 3 do not participate in the manipulation process and observe the proceedings by adhering to the approaching waypoints $\mathcal{L}^1$ and $\mathcal{L}^3$ .

The “wrenching” robots – 2 and 4 – are assigned waypoints, $\mathcal{W}^{2}$ and $\mathcal{W}^{4}$ , located within the box’s footprint (see Fig. 19). The waypoints are arranged along a line segment angularly displaced from the box’s length symmetry axis by an angle $\theta _r$ , with their distance from the box’s center denoted by $\rho _{r}$ . To simplify, $\mathcal{W}^{2}$ and $\mathcal{W}^{4}$ are positioned on one of the box’s diagonals. As a result, $\theta _{r}$ takes on values of either $-\pi /4$ or $\pi /4$ , while $\rho _{r}$ must remain below half the length of the main diagonal. This arrangement ensures that, as the robots follow these waypoints, their movement will enable a rotation aimed at minimizing the box’s orientation error.

Figure 19.

Waypoint generation in the rotation phase. Two of the robots, 2 and 4, execute the box’s turning maneuver, whereas robots 1 and 3 retract to a “spectator” configuration, following the box’s manipulation. The wrenching waypoints lie within the area of the box.

The procedure of this phase involves comparing the angular error between the box’s current orientation and its target orientation represented by the difference $\theta _b - \theta _t$ . The sign of this error determines whether the box will be turned clockwise or counterclockwise. If it is positive, the offset angle $\theta _r$ is set to $\pi /4$ , inducing a clockwise rotation of the box. Conversely, if the angular error is negative, $\theta _r$ is set to $-\pi /4$ , resulting in a counterclockwise rotation of the box. The waypoints that enable the rotation are expressed as follows:

(15) \begin{align}&\,\, \mathcal{W}^{2}:\left (\mathcal{W}^{1}_{x},\mathcal{W}^{1}_{y}\right ) =\left [\begin{array}{c} \mathcal{O}_{x}\\ \mathcal{O}_{y} \end{array}\right ]+\left [\begin{array}{c} \rho _{r}\cos\theta _{r}\\ \rho _{r}\sin\theta _{r} \end{array}\right ] \end{align}

(16) \begin{align}& \mathcal{W}^{4}:\left (\mathcal{W}^{4}_{x},\mathcal{W}^{4}_{y}\right ) =\left [\begin{array}{c} \mathcal{O}_{x}\\ \mathcal{O}_{y} \end{array}\right ]+\left [\begin{array}{c} -\rho _{r}\cos\theta _{r}\\ -\rho _{r}\sin\theta _{r} \end{array}\right ] \end{align}

The waypoints are employed until the object achieves the desired angular orientation, specifically when the absolute angular error $|\theta _{b}-\theta _{t}|$ falls below a predetermined threshold $\epsilon _{r}$ . Should there remain a positional error following the rotation phase, the process iteratively cycles through the translation and rotation phases until errors in both phases are reduced to within their respective predefined tolerance thresholds.