Behaviour Data Relations Modeling Language



BDRML version 1.0

A simple foraging algorithm

A simple foraging algorithmA robot searches the environment as a "Scout" and becomes a "Worker" upon finding a worksite, where reward is located [1]. A Worker extracts reward from the worksite (for example, it performs an inspection task or helps a customer nearby), while broadcasting recruitment signals to Scouts that are close. Any Scout that is recruited becomes a Worker as well. A Worker resumes scouting when its worksite is depleted.

A bee-inspired foraging algorithm

A bee-inspired foraging algorithmRobots drop off resource and recruit each other in the base [2]. As in the previous example, a "Scout" can find worksites in the environment with a probability p(F), after which it starts working by loading resources from a worksite, dropping them in the base and returning to the worksite until it is depleted. After resource has been dropped off in the base, the robot recruits "Observers" that are present in the base for a certain amount of recruitment time, TR. Any Scout that cannot find worksites within a certain scouting time, TS, returns to the base and becomes an Observer. When an Observer is recruited, it becomes a Worker. Alternatively, an Observer transitions back to being a Scout with a scouting probability, p(S).

Note how all relevant data structures are represented in BDRML but could not be directly expressed in a statechart. In BDRML, an explicit relationship between "Recruit in the base" and "Worksite location" exists, as well as an explicit condition of transitioning from "Observe in the base" to "Work" behaviour, that involves existence of "Worksite location" in the Observer’s memory.

An ant-inspired foraging algorithm

An ant-inspired foraging algorithmRobots utilise "beacons" in the environment in order to build a gradient of virtual pheromone from the base to a worksite and back [3], [4]. While performing the "Travel to Worksite" behaviour, a robot updates the "Base pheromone" that is stored in a beacon nearby, so that its value increases by one each time a new beacon is visited. In order to do this, a robot needs to keep track of the "Last pheromone value" in an internal data structure. Because the robot travels towards the Worksite, a gradient of Base pheromone emerges that can be followed on the way back to the base. Gradient of the "Food pheromone" is built in a similar fashion while the robot travels back to the base. Any robot performing the "Scout" behaviour that encounters a beacon can follow the Food pheromone gradient in order to reach a worksite and start working. Values of both pheromones decrease over time in each beacon according to some evaporation function, eN.

A statechart of the same algorithm would not be able to clearly represent when pheromone values are read and updated, or that values of pheromones, which are stored outside of the robots, decrease over time. Similar problems would be encountered when using a sequence chart. Since arrows in a sequence chart can only represent active communication, i.e., data transfer from robot 1 to robot 2, it would not be possible to show how robots read data from the environment, i.e., how information is acquired by a robot from a passive beacon.

[1] M. O. F. Sarker and T. S. Dahl, "Bio-Inspired communication for self-regulated multi-robot systems," in Multi-Robot Systems, Trends and Development, T. Yasuda, Ed. InTech, 2011, pp. 367–392.

[2] L. Pitonakova, R. Crowder, and S. Bullock, "Information flow principles for plasticity in foraging robot swarms," Swarm Intelligence, vol. 10, no. 1, pp. 33–63, 2016.

[3] B. Hrolenok, S. Luke, K. Sullivan, and C. Vo, "Collaborative foraging using beacons," in Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), W. van der Hoek, G. A. Kaminka, Y. Lesperance, et al., Eds. Richland, SC: IFAAMAS, 2010, pp. 1197–1204.

[4] N. Hoff, A. Sagoff, R. J. Wood, and R. Nagpal, "Two foraging algorithms for robot swarms using only local communication," in Proceedings of the 2010 IEEE International Conference on Robotics and Biomimetics (ROBIO 2010). Piscataway, NJ: IEEE Press, 2010, pp. 123–130