PRE2017 3 Group15

Group members

Name	Student ID
Ruben Beumer	0967254
Niek Blankers	0935876
Kyle van Oosterhout	0936196
Martijn Schipper	0951375
Martijn Timmermans	0956838

Introduction

On this wiki page, the progress and design decisions of group 15 will be shown. Furthermore, a literature study can be found about the problem in question.

Problem statement

Litter is a big problem in our society. It has various negative effects on humanity. If litter is in abundance, it attracts pests like rats and flies, which can result in the transmission of human diseases. Furthermore, It can increase the use of fossil fuel instead of recycling and it can reduce the sense of safety. To prevent this, public places should remain clean. Luckily, the government recognizes this problem and does its best to keep the streets clean. In the U.S.A. for example, the government spends 11.5 billion dollars on litter clean up (https://www.kab.org/?pagename=focus_litter_prevention). Currently this is a hard human job, with a low profile. This job could be replaced by cleaning robots, which can clean more efficiently, cheaper and possibly more thoroughly.

For this project, it was decided to focus especially on the energy considerations that come to play when designing such a system and how to handle subperfect conditions in the search strategy to make up for the camera that will not be able to detect litter perfectly at long distances.

Approach, milestones, and deliverables

To be able to reach our goal to design a cleaning robot that is able to find litter on a beach and dispose of it, without annoying the people on the beach, first a literature study will be done to make sure the group is working on something that has never been done before, or more work than is necessary.

Afterwards, the requirements set for the robot will be converted into specifications and subsystems according to the V-model. When this is done, the different subsystems will be divided over the group members to work on individually or in pairs. The focus here will be on the energy consumption and deliverance of the system as a trade-off for functionality.

During the litter recognition and robot algorithm sections, a simulation will be made to show that the found algorithms and strategies are working and realistic.

During every stage, the wiki will be updated with the progress and design steps.

The first milestone that will be reached will be a complete literature study. This should be finished by the end of week 2.

The second milestone that will be reached will be a list of requirements, specifications and subsystems. This should be finished by the end of week 3.

The third milestone that will be reached will be when each of the individual subsystems are working and keeping itself to the set specifications. This should be finished by the end of week 5.

The fourth milestone that will be reached will be when the simulation of the algorithms and systems is working completely. This will be finished by the end of week 6.

The fourth milestone that will be reached will be the integration of the different subsystems into a budget diagram that shows the trade-off between power consumption and functionality. This should be reached by the end of week 6.

The fifth milestone that will be reached is a well written wiki page about the process of the design period and a manual on how to build the robot, its costs and other relevant information. This should be reached by the end of week 7.

The final deliverable of the project will be a budget diagram with the different trade-offs for energy consumption and the optimal positions for central hubs, and a simulation that can show the effectiveness of the algorithms and strategies that the robot will use.

State of the art: literature study

A beach being cleaned of washed up plastics

Motivating beach visitors to pick up litter

To find out what has already been done in the subject of litter robots, research has been done in the following areas:

• Litter and waste - Where is litter situated and what is sensed to be the most annoying?
• Path finding - How to move a litter robot in an unknown environment?
• Litter detection - How to find the position of litter autonomously?
• Robot movement - How does a robotic system that is designed for picking up litter move around?
• Litter collection - How to pick up the litter after it has been detected?
• Robot design - How to design a robotic system?

Litter and waste

We have identified the following issues around waste and litter:

• Gum on streets: research shows that >10% of litter is gum. This highly disturbs 74% of people.
• people should be motivated to segregate waste themselves. Possible solution: robot that visits each home and asks them for their plastic / general waste products to motivate them to segregate waste.
• People from India don't care about waste, as long as it is not in their homes.
• Trash washing up on beaches.
• Poor efficiency of street sweeping vehicles, dirt makes up 56% of what they gather.

Composition of litter

Litter can be decomposed into different groups which occur more or less in the streets. According to Rijkswaterstaat, out of big litter (excluding gum and sigaret buts), beverage packaging, take-away litter and paper are the biggest problems, accounting for 24%, 22% and 21% of the total litter respectively between 2008 and 2014. The total list can be found in the table below.

Type of litter	Percentage of total litter
Beverage packaging	24%
Take-away waste	22%
Paper	21%
Other packaging	17%
Candy	10%
Plastics	3%
Unidentifiable litter	2%
Food remains	1%

The same research also gives the absolute numbers of the different litter types, including small litter:

Type of litter	Number
Cigarette buts	18,794
Beverage packaging	16,379
Take-away litter	15,656
Paper	15,298
Other packaging	12,408
Gum	10,117
Candy	7,213
Plastics	1,850
Unidentifiable litter	1,737
Food remains	1,000

In Utrecht an analysis was done of materials collected by sweeping machines, which found that 88.5 ton out of the 156.8 ton collected was sand. This means that 56% of the effort of sweeping is wasted on sand.

Annoyances (caused by trash)

The list below shows the response of (Dutch) citizens when asked about their daily annoyances.

• Litter besides the road: 92% (62% very annoyed, 30% somewhat)
• Loud noise: 64% (28% very annoyed, 36% somewhat)
• Litter on beached: 95% (76% very annoyed, 19% somewhat)
• Full trashcan: 77% (40% very annoyed, 37% somewhat)
• Traffic jam: 26% very annoyed, 33% somewhat
• Paper/cigarette butts/chewing gum on streets: 64% very, 30% somewhat

Furthermore: when asked, citizens state that they see 27% of all litter in the shopping mall, 15% on the beach and 13% on parking lots.

Litter positions

According to EcoConsult in 2014, the following indication scores were given for big and small litter (a high indication score means a clean environment):

Area	Score big litter	Score small litter
Average	3.56	3.44
Recreational area	4.15	4.04
Water recreational area	3.91	3.86
Business area	3.35	3.60
Shopping area II	3.69	3.45
Shopping area I	3.37	3.19
Residential area III	4.01	4.04
Residential area II	3.85	3.80
Residential area I	3.53	3.48
Event/Sporting centers	3.46	3.40
Access road	3.47	3.68
School area	3.35	3.42
Parking lots	3.08	2.62
Public transport	3.25	2.85
Catering/Entertainment centers	3.59	3.14
Shopping malls	3.50	3.07

As a conclusion we can state that parking lots, public transport and Shopping areas in urban cities have the most litter.

At the parking lots, most of the litter is caused by take-away packages, sigaret buds and beverage packages. Citizens also believe these places are filthy as stated by Gemeente Schoon in 2010 and 2012. The most plausible reason to believe parking lots have so much litter is that people stay only for a limited time and therefore they have little bonding with the area. In addition, creating litter from inside a car can be done relatively anonimous.

Near public transport areas, litter is caused mostly by people that need to be quick to catch a bus or train, because they do not prioritize putting there litter into a bin over catching the train or bus, especially when the closest garbage bin is full. The litter consist mostly of packages of food or drinks bought at the station.

Shopping areas are one of the most important areas because people think that when the shopping area has much litter, the whole township is filthy. As expected, most of the litter in shopping areas are bags and packages of items bought in the shopping area. Most litter occurs during peak visiting hours because litter attracts more litter.

Encouraging dustbin designs

Several dustbins have been developed to encourage people to throw their trash into it by rewarding them when they do so. An example is the ‘WiFi Trash Bin’, invented by Raj Desai and Pratik Agarwal, the founders of the startup ThinkScream. When someone throws something in it, this plastic bin shows an access code for a WiFi-network on a LED screen, giving them access to the network for 15 minutes. It has been tested at the NH7 Weekender music festival in 2014, where six of these smart bins could be used by the visitors. After the festivals in Bangalore, Delhi and Kolkata, over ten thousand people had used the bin.

In the Netherlands, a well-known example of interactive dustbins are the ‘Holle Bolle Gijs’ bins (and variations of it), used in the Efteling. These bins ask people in the theme park to throw their waste in it and thank them afterwards or react in another way. Sometimes children even start to look for other waste to throw it away in the park due to this creative invention. Inspired by these bins, the cities Tilburg and Eindhoven organized a design contest for interactive dustbins in 2017. The contest was won by Francien Fleuren and Marcel Lamers with their ‘Trash Tree’ that works on solar energy, lights up in the dark and makes a bird sound when something is thrown in, referring to the positive effect on the environment. Before the contest, in the Henri Dunantpark in Eindhoven, there was already a pilot with an interactive dustbin, which according to alderman Yasin Torunoglu helps to achieve a cleaner environment. In September 2017, also in Bergen op Zoom, some garbage bins have been equipped with a built-in speaker to react to people in a funny way after throwing away their trash.

Another example is ‘The world’s deepest bin’, an experiment in the context of an initiative called ‘The Fun Theory’ by Volkswagen. A video on their website shows a trash bin in a park that makes a sound as if the trash that people throw in it falls very deep. During one day, 72 kg of rubbish was collected in this bin, which was 41 kg more than the normal bin just a small distance further. Some scientifically critical questions about results of this experiment could be asked, e.g.: Did the people throw in their trash in this bin instead of in the normal bin and not instead of throwing it on the ground, so that the total reduction of litter is less than the results suggest? Would the results still be so promising if the experiment was done for a longer period, or would the people start finding it less interesting in the long-term? However, when these bins would for example be used in touristic places, where are different people and a lot of children each day, these kind of interactive dustbins will probably significantly decrease the amount of litter, similar to the dustbins in the Efteling as described above.

General

RoboEarth

Thousands of robotic systems deal with and try to solve the same essential problems. This article is about a design and first implementation of a system for sharing knowledge between robots. The data, independent of specific robot hardware, is collected, stored shared and linked by RoboEarth, using existing standards. This enhances robot learning and adaption in complex tasks. Besides, robots using RoboEarth can execute tasks for which they were not explicitly designed for. The implementation is based on an architecture of three layers: a server, generic components and a robot specific layer. The server holds the database in which it stores a global world model with information on objects, environments and action recipes. It also provides basic reasoning Web services. The main purpose of generic components in the second layer is to allow robots to interpret the action recipes. The third layer provides a generic interface to a robot’s specific (hardware-dependent) functionalities via a skill abstraction layer. For our project, a RoboEarth-like system would in particular be very useful to recognize litter, both using the information about objects (what is litter and what not) as well as about the environments (to be more efficient in finding the litter). The information about actions could be useful for picking up the litter, depending on what system we will use.

Springer Handbook of Automation, chapter 70: Cleaning Automation

Especially in the domain of cleaning, service robots already provide many different options for relieving people of dangerous, stressful, and/or monotonous work and are penetrating both household and professional market sectors. Household systems have technically simple and low-cost designs and are already being sold in large numbers. Professional systems are technically complex, flexible, cost effective, efficient, and easy to operate. However, since they fail to fulfill the requisite criteria in many cases, they have not yet established themselves as mass products. Nevertheless, numerous individual solutions exist for special applications such as facade or pool cleaning.

To the extent that they do not fully navigate surfaces when geometries are more complex or environments are dynamic and generally can neither navigate themselves nor coordinate tools better than humans, professional cleaning robots’ sensory and cognitive capabilities continue to limit their universal and cost-effective use. Such cleaning robots will not become mass products until their cost effectiveness, performance, efficiency, and total attendant costs make them superior to manual cleaning. Further development of service robots’ cognitive capabilities, environment modeling sensor systems, and multimodal user interfaces is being pursued worldwide for other fields of application and is a fundamental prerequisite to establishing cleaning robots in the professional sector.

New Brooms Sweep Clean – An Autonomous Robotic Cleaning Assistant for Professional Office Cleaning

In this paper, a prototype autonomous robotic cleaning assistant, that can both clean floors and clear trash bins in offices, is presented. It was realized on a Care-O-bot 3 platform, a multi-purpose service robot. The arm was upgraded with a tool changing interface from Schunk, which enables switching between a three finger hand for clearing bins and a vacuum cleaner for cleaning floors. A tool trolley is used to carry containers for waste and fixtures for detached tools. In short, the robot first inspects all rooms to find the polluted locations and will directly clear all found trash bins into the waste container of the trolley. Then, it changes its three finger hand for a vacuum cleaner at the trolley and attempts to clean all spots from the polluted locations list. Afterwards, the robot verifies the cleanliness and stores the information so that the operator can clean the remaining spots and inform the system about false alarms to improve its behavior. The most important functional modules are:

• Map Segmentation: results in ‘room’-sizes between 15 and 80 m2 and allows for planning a good trajectory through the environment.
• Exploration Algorithm: optimizes the sequence of entered rooms as a traveling salesman problem (TSP), using a quite extensive algorithm, also taking the minimal amount of trolley positions and the time it costs to move to the trolley to clear a trash bin into account.
• Dirt Detection and Learning: A visual dirt detection method is applied which judges on a per image basis without any need for learning the patterns of the clean ground or the appearance of any pollution and can detect spots occupying an area of >5 mm diameter. This method is explained in the two articles above. It is extended to learn from the operator using the check for false alarms as described above.
• Trash Can Cleaning: The detection of attached markers on bins proved most reliable and computationally economical compared to other approaches for object recognition and can be used in the real world. The MoveIt framework is used for arm movement to grasp a bin.
• Tool Change: using an industrial interface combined with visual servoing methods for automization. The tool are connected mechanically by closing an inner rotational lock and electrically using a CAN bus interface.
• Vacuum Cleaning: The vacuum cleaner is placed on the ground and the robot drives back and forth or left and right to clean the spot. Within narrow areas, the arm itself is moved.

The test showed that although it was a first prototype, it already worked surprisingly well. Using the learning algorithm, the reported pollution precision was increased from 62% to 89%. In summary, 90% of the trash bins could be cleared and 86% of the dirt was removed, with a speed performance of approximately 120 m2 per hour (4 times less than a professional, but many improvements are suggested).

Path finding

Path Planning for Complete and Efficient Coverage Operation of Mobile Robots

The paper presents a method for mobile robots to perform area coverage tasks where completeness and efficiency of coverage are important. The method can be used for robotic de-mining, cleaning, painting, etc.

It is assumed that the robot is operated in an enclosed indoor environment and it knows its map in terms of occupancy grids.

A divide and conquer strategy is employed for efficiency. A cell decomposition algorithm divides the given area into cells (sets of grids):

1. Occupancy grid maps are rotated along their orientation invariant angle so that two identical maps with different rotation result in the same maps.
2. The given area is decomposed into cells based on the change in free space segments for each 'slice' of the map.
3. Noisy cells (created due to complex structures and sensor noise) are merged into larger neighbor cells.

Next, the path is generation for efficient area coverage.

1. Predefined template paths are generated for each cell (back and forth or spiral motion) to find an optimal path to cover them. Predefined templates are used to reduce computational complexity.
2. A path for the overall area is formed from the path that requires minimum time for each cell. A graph search algorithm is used for this purpose.

Coverage Path Planning for Mobile Cleaning Robots

There are different ways in which a robot can do path planning in any given environment. The first way is Random Path Planning, in which the robot will move in a random direction until it is obstructed and will then chose a new random direction. A spiraling bias can be added to make this approach more convenient. A more sophisticated way to cover the whole area, is by using Exact Cellular Decomposition. This method splits the room into parts which are easier to cover. Which also makes it more efficient in places with obstacles. A variance on the Exact Cellular Decomposition is the Boustrophedon Cellular Decomposition, which does the same, but makes the parts so that it can be cleaned with a simple back and forth motion. A fourth method is a Backtracking Spiral Algorithm. Which does the same as a random spiral, but takes into account possible blocking objects by moving around them and adding the information gained of the object to make the spiral change shape so that the same places are not cleaned twice. The solution proposed is an extended version of the BCD in 5 steps:

1. The robot moves to the outer boundary of the environment
2. The robot follows this boundary until it has completely circled it
3. A BCD of the environment is created
4. Create a list containing every cell. The first one is where the robot is
5. The cells are covered in sequential order

To make this also work in dynamic environments, the robot will continue scanning the room and adjusting the individual cells when detecting sensor or localization errors.

Simultaneous Localization and Mapping

Simultaneous Localization and Mapping (SLAM) is for a robot to be placed at an unknown location in an unknown environment and for the robot to build a consistent map of its environment while simultaneously determining its location within the map. The problem with SLAM is that the true locations are never known or measured directly.

The probabilistic version of SLAM checks the highest probability for a landmark to be and the robot to be given the history of vehicle locations, the history of control inputs and the set of all landmark observations. The problem with this is that much of the error comes from when the robot wrongly estimates its position with reference to a landmark only once.

To find a solution to SLAM, the programmer needs to find an appropriate representation for both the observation model and motion model that allows efficient and consistent computation of the prior and posterior distributions in the time update step and the measurement update step.

Complete Coverage Navigation of Cleaning Robots Using Triangular-Cell-Based Map

In this paper, a novel navigation method is presented for a cleaning robot, which can work well in a completely unknown workspace. First, a new triangular-cell-based map representation that enables a cleaning robot to have more navigation directions is presented. While the rectangular-cell-based map has eight navigation directions, the triangular-cell-based map increases the navigation directions to 12. This increase makes the navigation path shorter and more flexible. Second, a complete coverage navigation and map construction method is presented, which enables a cleaning robot to navigate the complete workspace without any information about the environment. To generate a complete coverage navigation path without prior information of the environment, the wall-following navigation was first performed. Through this procedure, a cleaning robot can obtain the information of the contour of the environment. Then, basic templates were introduced as means for local navigation. To find the uncovered region and determine the local direction, the distance-transform method was also adopted. With the use of simulations the effectiveness of the approach was verified.

Complete Coverage Path Planning and Guidance for Cleaning Robots

This paper describes a complete coverage path planning and guidance methodology for a mobile robot, having the automatic floor cleaning of large industrial areas as a target application. The proposed algorithms rely on the a priori knowledge of a 2D map of the environment and cope with un- expected obstacles not represented on the map. A template based approach is used to control the path execution, thus incorporating, in a natural way, the kinematic and the geometric model of the mobile robot on the path planning procedure. The novelty of the proposed approach is the capability of the path planner to deal with a priori mapped or unexpected obstacles in the middle of the working space. If unmapped obstacles permanently block the planned trajectory, the path tracking control avoids these obstacles. Tests with the mobile robot LABMATE show that satisfactory floor coverage can be obtained using a template approach even when there are mapped or unmapped obstacles present in the interior of the cleaning area.

Mobile Robot Positioning: Sensors and Techniques

This article presents an overview of existing sensors and techniques for mobile robot positioning. The foremost conclusion that was drawn from reviewing a vast body of literature was that for indoor mobile robot navigation no single, elegant solution exists. For outdoor navigation GPS is promising to become the universal navigation solution for almost all automated vehicle systems.

Litter detection

Vision-Based Coverage Navigation for Robot Trash Collection Task

This paper describes an algorithm to optimally find and pickup trash and benchmarks this against existing algorithms. The proposed algorithm consists of four distinct steps

1. Follow the wall to obtain the contour and size of the working space. By doing this the working space can be split up into rectangular cells.
2. Scan for garbage in the current cell
3. Find and move to an unvisited area. Repeat step 2 and 3 until all areas have been visited.
4. Deposit trash and move back to initial location

Step 3 is implemented using the 'Boustrophedon Path-Planner' algorithm and a random path planner. It turned out that the 'Boustrophedon Path-Planner' performed better.

A Visual Dirt Detection System for Mobile Service Robots

This article described a method to detect dirt on floors that are monochrome or have at least some repetitive pattern. The data from a RGB-D sensor (color camera with depth-sensor) is processed in four main steps (last two combined):

• Plane Segmentation: This step finds the part of the image in which the floor can be seen, using the depth-information from the sensor. It basically looks for a plane that contains the most points to satisfy a particular plane equation (ax + by + cz + d = 0).
• Spectral Residual Filtering: This step filters out the background of the floor image leaving only the innovation part, by finding the deviations from the statistical mean of the logarithmic amplitude spectrum (using the Fourier transform) of each channel (R, G and B) of the image.
• Rescaling and Thresholding: Artificial dirt is added to the floor (2 black and 2 white spots) causing extrema in the response, which are used to rescale the response of the whole image in order to prevent the normal patterns in the floor to be seen as dirt, in particular when there is no real dirt. The spots in the rescaled dirt image with an intensity above a certain threshold are selected as dirt.

Depending on the floor background structure, 52.6% to 92.5% of the dirt was detected, with a positive false rate of only a few percent. Depending on the surface, problems such as very dark and small objects not being recognized as dirt, or light reflection causing false positives could occur. Further, the algorithm proved to be able to cope with changing surface material and texture to some extent. However, large scale dirt stains (such as from coffee) are filtered as background with this approach. Remark: In this article I read “Tidying up larger objects was demonstrated at the Robocup@home challenge by the team of robot Eraser.” Finding more information about this could be useful for our project as well.

Autonomous Dirt Detection for Cleaning in Office Environments

Here, an extended/improved version of the dirt detection system from the previous article is explained. Two of these extensions are a large, publicly available database of dirty ground floors (65 different kinds of dirt recorded at 5 floor materials) and a testing framework to use this database. All data is recorded using the service robot Car-O-bot 3. The integrated laser scanners and RGB-D camera Microsoft Kinect were used to localize the robot and dirt, so that the detection could be integrated in a map. To enable this mapping and because the camera might not always operate in the same position above the ground, a perspective normalization is applied after the plane segmentation described in the previous article. To do this, a homography which transforms the ground plane as seen in the camera image into a plane seen from a (virtual) bird’s eye view is estimated. The steps ‘Spectral Residual Filtering’ and ‘Rescaling’ from the previous article remained the same, although they are here referred to as ‘Saliency Computation’ and ‘Saliency Normalization’. At the ‘Dirt Thresholding’-step, they now implemented an option to exclude the pixels that belong to strong lines from the thresholding operation, since these strong lines are often caused by transitions between bright and dark (background) surfaces and result in false detections. The advantages of dirt mapping are: (1) fusion of multiple observation to strengthen certainty, (2) option to temporally separate inspection and removal and (3) enable verification and feedback. Another threshold could now also be used to determine what is seen as dirt or not can be used: the amount of frames in which a spot is detected as dirt (possibly as a ratio of the total amount of frames in which the spot is captured). Depending on both threshold values, different detection and false positive rates can be achieved: for example about 90% detection and 45% false positives, or about 100% detection and 85% false positives (averaged over the different dirt and floor types). The performance could even be improved when for example different threshold values would be used for different floor types. The system however still does not take larger (3-dimensional) litter into account, and of course fails when dim lighting prevents dirt from becoming visible in the image at all, even for humans.

Robot movement

Autonomous Robotic Street Sweeping: Initial Attempt for Curbside Sweeping

Street cleaning can be a coverage or a tracking problem, which both require localization, coverage path planning and tracking control. Using two fisheye cameras and projective transformation, a top view was gained and edge filtering, a Hough transform and RANSAC line fitting was used to find the sidewalk along which the robot has to drive.

Principles of appendage design in robots and animals determining terradynamic performance on flowable ground

This paper shows an approach to control (and vary) the ground penetration resistance of a granular substrate using continuous upward airflow through a fluidized bed. This technique is used to investigate the influence of ground strength on the locomotion performance of robots (a bio-inspired hexapedal robot called SandBot and numerical simulations for the Xplorer robot) and animals (four lizard-like species and a crab). They found that locomotor performance was strongly correlated with the foot pressure. Generally, the experimental and simulated results followed the same trends: for small leg penetration ratios (foot pressure relative to penetration force per unit area per depth and leg length), the locomotion performances only decrease slightly, but for larger penetration ratios, the performance started to decrease substantially, probably due to drag of the ventral surface. This also provides an explanation to the fact that the performance of some animals was more sensitive to the ground penetration resistance differences in the investigated range than for other animals: graphs made with normalized average speed and leg penetration ratios showed very similar data points for all species. The data points for the robots also showed similar behavior, except that animals could still maintain ≥50% of their speed on fully fluidized ground, suggesting that they likely combine passive and active control to diminish the decrease of performance on low stiffness substrates. The most important conclusion from this article for our project is that we could use relatively large foot and a light body (i.e. smaller foot pressure) when possible, to minimize leg penetration ratio and stay within the ‘insensitive’ region to ground stiffness change, in particular when we use a legged robot. Of course, the body should not be too close to the ground to prevent extra friction for substrates with a low ground penetration resistance.

Robot design

System design of a litter collecting robot

Litter is a very big problem, because a broad study of annoyances of the Dutch public found that people rated litter to be more annoying than noise from neighbors and cigarette smoke. There is however a big difference between the places where most litter occurs, which are near sporting facilities and parking lots, and where people perceive it as annoying, which are mostly in shopping malls and on the beach. Furthermore, litter has more consequences than just annoyance. It can attract pests like rats and flies, which can result in human diseases. It can bring harm to animal life. It can increase the use of fossil fuel instead of recycling. It can reduce the sense of safety, and above all, can increase the amount of litter on the street, making this a negative spiral. To prevent this spiral, public places should remain clean.

Currently this is a hard human job with low profile. It is, however, important to keep humans involved in the job, because human cleaners in the streets have a social aspect. Using a robot that cleans most of the litter, and a human to show the robot where it missed certain litter or to help with cleaning up hard to clean litter, the human will have a physically easier job, and has more time for the social aspect of being in the area. It is also important to make the robot quiet and power efficient.

To find the litter efficiently, the robot has a Portable Operator Device, allowing the human cleaner to make a picture of a new type of litter and send it to the robot, so that the robot will recognize it next time. To make the robot power efficient and quiet, a circle of plastic fingers were used and a flap that could close when litter was found. The fingers would then push the can into the hopper. To know where the litter is, scanning laser range finder and a camera were used. The camera takes a picture when the SLRF finds an object, and this image is compared to the litter pictures in the memory of the robot.

United States Patent Mobile Robot for Cleaning

This patent describes multiple designs for a robotic cleaner. A robotic cleaner includes a cleaning assembly for cleaning a surface and a main robot body. The main robot body houses a drive system to cause movement of the robotic cleaner and a microcontroller to control the movement of the robotic cleaner.

Development of Outdoor Service Robot to Collect Trash on Streets OSR-01

This paper describes the design of an autonomous robot which is to be used to collect trash on the streets. The robot has two wheels to move but drives an already provided route. To avoid objects it uses four 2-D laser range finders. It is currently only able to pickup PET bottles using a hand with five degrees of freedom. It can detect objects using a omni-camera. To measure the distance to the object, it uses two additional cameras. The image recognition is done using a technique known as 'template matching'. This means that the robot has a large library of objects labelled as trash which it compares to the images received from the omni-camera. If the images are sufficiently similar, the robot will pick it up.

Development of Outdoor Service Robot to Collect Trash On Streets OSR-02

This is a follow up on the previous paper. For the new prototype, dubbed OSR-02, an extra hand is added. This allows one hand to hold a trash bin while the other can put the trash in it. Furthermore, the wheels are replaced with crawlers. The sensors and detection system was were kept the same. More detailed tests were also documented, showing that the OSR-02 is able to get over a ditch of 180 mm in width. The robot was also tested in public space, where it was able to successfully pickup plastic and glass bottles in the route and able to avoid pedestrians.

A Study on Development of Home Mess-Cleanup Robot McBot

This paper describes the design of an autonomous robot which is to be used to cleanup indoors. The robot has two arms to grasp the object and a lifting support. Objects are recognized by a RFID tag. After an object is picked up, it is able to place on for example a shelf. Self localization is done by placing RFID tags on the ground.

Educational Outdoor Mobile Robot for Trash Pickup

Inspired by the 'Push the Talking Trash Can' of Disney, an interactive low-cost outdoor mobile trash can is designed. With this robot, they aimed to raise environmental awareness, help clean up the environment and promote robotics education among children. The robot is also equipped with a low-cost air quality monitoring system. They purposely avoided autonomous robot because it minimizes control by children and they will find it more fun and have a sense of accomplishment by interacting with, and remotely controlling the robot. Also, autonomous is difficult because the roads in underdeveloped countries often have potholes, uneven construction etc making it difficult to navigate effectively. On the robot a LCD display is mounted to display the air quality and broadcast messages and animations. It can be controlled remotely using smart phone/tablet. The materials used in the construction costed less than 250 dollar.

A Multi-Robot System for Continuous Area Sweeping Tasks

A trash collecting robot performs a so-called 'continuous area sweeping' task. With this task, a robot must repeatedly visit all points in a fixed area. This paper extends this task to multi-robot scenarios.

The approach described in this paper is not to simply send the robots along the same routes again and again, but to sweep based on a task-dependent cost function. For example, when removing trash robots should prioritise heavily-trafficked areas.

The paper mostly focuses on dividing the overall area between multiple robots.

DustCart, an autonomous robot for door-to-door garbage collection: from DustBot project to the experimentation in the small town of Peccioli

DustCart is an autonomous garbage collecting robot. It can navigate urban environments with static and dynamic obstacles. Users can request a garbage removal after which the robot is dispatched, interacts with the user through a touchscreen interface, and receives a garbage bag. Next, it moves to a site where the garbage is deposited. DustCart monitors air quality, temperature, and humidity along the way.

Two DustCart robots were tested for three months in the small town of Peccioli, Italy.

Design process

Heuristics

In the conceptual phase, there are a few heuristics to the design process, namely:

• The choice between architectures may well depend upon which set of drawbacks the client can handle best.

• Extreme requirements should remain under challenge throughout system design, implementation and operation.

• Don't assume that the original statement of the problem is necessary the best or even the right one.

• No complex system can be optimum to all parties concerned, nor all functions optimized.

• A model is not reality.

• Complex systems will develop and evolve within an overall architecture much more rapidly if there are stable intermediate forms than if there are not.

• Build in and maintain options as long as possible.

• Don't make an architecture too smart for its own good.

The conclusions that can be taken from this are that the design will have to have intermediate forms of the design during the design, which will be interpreted in a robotic system as different sub systems that work on their own. Also the system should not be smarter than it should be, meaning in this context that the robot should only save the information that it needs and have the options to do things that make sense according to the designer rather than making it think about those options itself.

V-shaped design

V-shaped design

The heuristics of the conceptual design makes the use of V-shaped design very logical. According to the book The Design of High Performance Mechatronics, in time, first the functional requirents should be determined, which should move past the system design, subsystem design and detailed design (element design) by decomposition and defenition in the conceptual phase. Afterwards the opposite way should be taken for the implementation. This however is not relevant for the design phase.

Conclusion

From the two perspectives stated in the previous sections, it becomes clear, that first the functional requirements should be determined and converted into specifications, which should then be decomposed into subsystems which can be divided among the designers, who will in turn decompose the subsystems into elements that can be individually designed. Furthermore the behaviour of the robotic system will be needed to designed, making sure the robot is efficient and comply to the requirements.

Objective

In the previous section, it has become clear that extensive research has already been executed. The theoretical groundwork has been done regarding the development of a robot which is able to collect litter in well paved environments such as the mall. Do notice however that this is only theoretical, and that the research is far from practically implementable. Currently, no research has been done regarding the many practical and social problems that arise from putting a robot in an environment with many different agents. A quick example which is never mentioned in a research paper, is that the robot should be unable to hurt other agents in its environment. Furthermore, it has been shown in “Inzamel- en beloningsystemen ter vermindering van zwerfafval” that 76% of the people is very annoyed by the litter that lies on the beaches. No research is done on how a cleaning robot would operate on a beach. Operating a cleaning robot on sand is non-trivial, since the locomotion and collection of litter need to be specially designed to work in sandy environments.

This paper tries to bridge a part of the gap in the research. More specifically, this paper entails the design of the energy consumption and deliverance of the robot, including the high level software that could be run on the robot. When implemented, the robot is able to autonomously drive around while cleaning the beach. Of course there exist a great variety of beaches, and the robot might be more effective on some particular beaches than other. But as stated previously, we are interested in how the operate optimally when in a sandy environment. Furthermore, a relatively low density of litter (so not like in the picture) is expected. As already shown in the research, huge steps towards autonomously driving and identifying litter have already been taken. This paper proposes a practical design, contrary to the proof of concept designs that have been done previously. This means that this paper focuses on practical problems that arises when using such a robot in a sandy environment with many different agents. Part of the problem arises from the sand, which makes locomotion and collection of litter more difficult. The other part is the user interaction part. If the beachgoers are not happy with the robot, then they will forego going to the beach. This is not in the interest of anyone, therefore we will anticipate some of the problems and provide solutions to these problems.

Concept of operation

As soon as the robot has recognized litter it will move towards it. It does this using a specially designed locomotive system which is able to drive over the sand. While driving towards the litter, it will need to actively avoid other beachgoers and holes in the ground using its sensors. When it has arrived at the litter, it needs an system responsible for the collection of litter. Because the object is likely surrounded by a lot of sand, a sand filter might be needed to separate the litter from the sand. Upon collection of the litter, it should store it in its litter storage container. When the storage container is full, it should drive to a central hub where it is able to drop the litter off. To make sure the robot does not run out of energy, various energy related calculations need to be made to ensure that the battery of the robot is large enough and that it is possible to recharge the battery. To protect the robot against the elements, it has a well-designed hull. Since there might be other robots that are also collecting litter, there is a strategy for robot cooperation. Finally, human interaction is taken into account. To do the actions and make its decisions, it uses software/algorithms.

From this concept of operation, we can now derive the following subsystems:

• Litter recognition
• Locomotion
• Sensors to avoid beachgoers and holes
• System for the collection of litter
• Sand filter
• Litter storage container
• Central hub
• Energy related calculations
• Hull
• Robot cooperation
• Human interaction
• Robot software/algorithms

The users

The most important stakeholders are the (adult) beachgoers. They are the ones which have a problem with the litter on the beach and preferably want all of the litter to be removed. Multiple studies (ref1. Ref2) have reported that a reduction in litter leads to people feeling more safe. Also, families will prefer to go to clean beaches, so they have to worry less that their children will be harmed by for example glass which hides in the sand. Even though the beachgoers will like clean beaches, it is also very important to them that they can enjoy the beach. This means that the robot should not produce too much noise, as this will annoy the beachgoers greatly. Also, one can imagine that it will annoy the beachgoers greatly if the robot bumps into people. This however may not be enough for all beachgoers, as some would prefer the robot to keep its distance so it does not enter their ‘personal space’.

The children are also a very important stakeholder which will need to be taken into account. They will have a great interest in the robot and want to play with it. It is therefore important that this is safe for both the child as well as the robot. This means that the robot is unable to do harm to the child, but also that the child is unable to break the robot.

The citizens and the tourists are the most important users in this project. They will directly benefit from the reduction of litter on the street and would like to have them as clean as possible. As already described in the problem statement, the reduction of litter will lead to less pests and less danger of cutting themselves for children playing outside. Of course, wild life will benefit from this reduction of litter for the same reasons as humans do. Small animals can also get stuck in litter or strangle themselves. This will also be reduced with this project.

Enterprises, such as restaurants or ice cream stalls, will also benefit from the reduction of litter. As already stated, beachgoers prefer a clean beach over a littered one. This means that people that want to go to the beach are more likely to choose the clean beach, which leads to more customers for the enterprises. In addition, the robot will appeal greatly to the children, attracting many customers. The enterprises would like a robust robot, which is able to withstand great external forces. They also prefer it to be as cheap as possible, and keep the maintenance cost low. It should be easy to replace specific parts if they break down, so they do not need a dedicated engineer to fix the robot which will help keeping the maintenance costs down.

In addition, the local government will have great interest in the design of such a robot. As already stated, in the U.S.A. they have to spend 11.5 billion dollars on cleaning the litter. Therefore any help to decrease this cost be welcome to them. It might be even possible for the enterprises to ask for a subsidy for which in return the enterprises will keep the beaches clean. This makes the design of a cleaning robot even more interesting for the enterprises.

There might also be an operator required, but this can only be determined at a later stage of the design process. An operator might be required to control the robots, help them with cleaning where necessary and help resolve issues for example when the robot is attacked by teenagers or wrongly identifies a purse as litter. This mainly depends on how well the software is at autonomously controlling the robot, and how well the vision system is able to identify the litter. If an operator ends up being necessary, there should be a clear and intuitive interface to control and/or help the robots.

System requirements and specifications

Requirements

Before something can be said about the robots requirements and specifications a couple assumptions have to be made about the environment that the robot will work in. The following assumptions have been made:

• The robot will not be vandalized by people.

• The litter that is on the beach is not stuck to anything, for example a plastic bag caught under a beach chair.

• The litter does not weigh more than 1 Kilogram. (this gives us something to base the power of our engine of, can of course still be changed)

• The litter is smaller than the robots litter collecting mechanism. (can be specified when we know more about our collecting machenism)

• The terrain the robot works in will mostly consist of sand

• The temperature is between -10 and 40 °C.

• The robot will work in moderate to bright lighting conditions. (can be removed if we decide to give the robot headlights)

The obvious system requirements that can be taken from the problem statement are the following:

• The system must be able to recognize objects and determine what is litter and what not.

This is important because the robot should not pick up items dropped by for example kids and throw them away like litter, but the robot should still be able to distinguish enough litter to make the beach significantly cleaner.

• The system must be able to collect litter

It is very important that the robot is not only able to detect what is litter and what is not, but that it is also able to pick up the litter in order to make the beach a cleaner place.

Less obvious system requirements that can be added are:

• The robot should not carry too much sand

On a beach the chances are big that the robot will also pick up sand instead of litter. This however is inefficient, because it takes op storage place and it will weigh the robot down, making it less power efficient.

• Can not topple because of external forces

It would be highly unfortunate if the robot would fall over because of strong winds or waves. This is because the robot will likely be unable to stand up and humans will have to come and pick it up. This is not only highly inefficient, but it will also cause annoyance to beach visitors, because it will be an obstacle in both their view and their paths.

• The robot needs to be able to move reliably over sand and mud

Because the robot will be moving over the beach, it is highly necessary that the robot can move reliably over sand and mud, for the same reasons as the toppling. If the robot gets stuck in the sand this will be inefficient and annoying for the beach visitors.

• The robot should not float in water

Floating on water will likely cause the robot to topple over when a wave of water comes. Also, if the robot is floating, it will not be able to pick up any litter reliably anymore. Therefore it is easier for the robot to stay on the ground even when there is water on top of it, so that it can continue its job.

• The robot needs to be waterproof

On the beach the chances of a wave hitting the robot are large, therefore the robot needs to be waterproof in order to keep functioning after a wave hits the robot.

• The robot should be able to operate on battery power, optionally combined with renewable energy sources

Because the weather is an unknown factor, renewable energy sources on their own will make the robot too reliant on external factors. Therefore the robot should be able to work on a battery as well.

• The cost of a robot should not be too high

If the robots costs would be too high, it would never be bought to clean up beaches, therefore the costs have to be low.

• The robot should avoid large holes

Even though the robot can move over sand, it is possible that it will fall into a hole that it cannot get out of, therefore it is better to always avoid these holes.

• The robot should be able to pick up litter of varying size

Litter is never always the same size, a can is a different size than a bottle for example or a potato chip bag. Therefore, to pick up as much litter as possible, the robot needs to be able to handle more than one specific kind of litter.

• The robot should be able to carry enough litter with it

The robot will be highly inefficient if it would need to return to a central station everytime it picked up a single piece of litter. Therefore the robot will need to have enough storage room to carry litter.

• The robot should be able to deposit collected litter in a central location

As the storage room of the robot will be finite, the robot will need to dispose of the litter it collected in some way to continue gathering more litter afterwards.

Social requirements

Besides the technical requirements, there are also various social issues the robot will need to deal with. The designed robot needs to interact in an environment with many stochastic agents. One might imagine that such a robot will attract the attention of many young children. These children might for example want to stand on it, or try to hinder the operation of the robot. Therefore the robot should be very robust. Besides from other agents harming the robot, it should also be impossible that the robot harms other agents. This means that at the very least, sensors should be installed to avoid running in to people. Lastly, we should be aware of how the robot will change the people in its environment. One might postulate that the existence of such a robot means that the people will become lazy. In one study (find source again), a school placed an interactive bin inside the canteen which would give positive feedback if students threw their litter in. This resulted however in a huge mess around the bin because students were trying to threw their litter as hard as possible in the direction of the bin.

Being in such a rich environment with other agents brings however also some advantages. No system is perfect which means that the system will sometimes fail. It is for example very hard for a robot to classify what is junk, and what is not. If a robot is in doubt however, it could simply ask nearby agents or a human operator by for example sending a picture of it. In the case where somebody for example drops their bottle, it could be on accident. When the robot detects this, it could pick it up and give it back to the one that dropped it. The robot also should not clear away toys of children, and if possible try to avoid demolishing their sand castles when operating. Furthermore, it is possible to use the fact that most people want to relax on the beach. When the robot detects that it is in danger because for example children are hitting it, it could sound an alarm. This will annoy nearby people, and they can chase away the children to make the robot stop it's alarm. Lastly, it is possible that the robot gets stuck. Asking for the help of other agents or a human operator could be again a simple solution to this problem.

The requirements can be led back to Isaac Asimov's three laws of robotics:

1. A robot may not injure a human being or, through inaction, allow a human being to come to harm.
2. A robot must obey the orders given it by human beings except where such orders would conflict with the First Law.
3. A robot must protect its own existence as long as such protection does not conflict with the First or Second Laws.

Specifications

These requirements can be decomposed into the following specifications Please note: currently these are best-guess values to give an idea of the order of magnitudes.

• Pick up 9 out of 10 items defined as litter on a sandy environment

The robot needs to reliably pick up litter. 90% seems like a good number because there will always be litter that the robot will not see or will not be able to grab.

• Produce less than 50dB of sound

An average human conversation is between 40dB and 60dB. Therefore 50dB will be unlikely to annoy the people on the beach more than a conversation of a group of people next to them.

• Keep at least 1 meter distance from humans

Coming too close to humans might frighten them or harm them. A one meter distance is a safe distance which is not too close to harm the human, nor too far to ask the human for help if necessary.

• Do not pass humans more than 2 times in 10 minutes

People will get annoyed if the robot will pass them too often, as it still makes sound and blocks the view. It is estimated that 2 times in 10 minutes will be an acceptable amount of time which the robot will be in the sight of the people.

• Maximally 10% of the picked up weight is sand

In normal garbage cans, 56% of the weight is sand. In this project, the robot is supposed to actively get rid of this sand. This means about an 80% decrease from the average garbage bin. This seems like a reasonable number.

• Move at at least 2 m/s on sand

An average human walks at 1.4 m/s. The robot should be just a bit faster to be able to avoid getting closer than 1 meter to humans more easily, therefore 2 m/s seems like a good speed.

• Survive in water of the same height as the robot for 2 seconds

A wave crashing over the robot will put the robot underwater for about 1 second. To be safe, the robot should be able to survive two of those waves immediately after each other.

• Operation time of at least 1 hour without recharging, recharging within 30 minutes or a battery replacing system or another way to obtain energy such as solar cells

A one hour operation time is a good estimation for the robot to pick up the maximum amount of litter and returning, as it will need to pick up 25 pieces of litter in this hour and returning, which gives an average of about 2 minutes per piece of litter, which is a reasonable estimation.

• The maximum costs of one robot should be €5.000,-

5000 euros is a nice round number which will be roughly the amount of money a company would pay for a robot to clean up a part of the beach.

• The robot should be able to pick up objects of 1 - 200 grams

• The robot should be able to pick up objects of 1 - 1000 cm^3

It can be assumed that the smallest piece of litter is a sigaret but, which is about a gram in weight and a cm^3 in volume. It is also assumed that the heaviest litter will be 200 grams, this is roughly equal to a 1 Liter PET bottle filled with 160 mL of water. The volume of this PET bottle will be 1 L and this will be chosen as the maximum volume the robot should be able to pick up.

• The load capacity of one robot should be minimally 5 kg

• The load capacity of one robot should be minimally 25 L

The robot should able to pick up about 25 times the biggest possible litter to make the robot efficient enough. Therefore the minimum weight it should be able to carry should be 5kg and 25 Liter.

• Can't topple when wind blows with 9 m/s.

The maximum wind speed in Vlissingen in 2017 was 9 m/s . Therefore the robot will need to survive these wind speeds to make sure it is not dependend on weather conditions whether it can function.

General operation overview

TODO: large-scale overview of operation

Subsystems

• Locomotion
• Litter recognition
• Litter collection
• Sand filter
• Litter storage
• Central hub
• Structure/frame
• Energy management
• Human interaction
• Robot algorithm
• Robot cooperation

Subsystems: analysis and design

This chapter detials the analysis and design of the different subsystems involved in the robot design.

Locomotion

Sony's bipedal QRIO and quadrupedal AIBO robots.

First of all, the robot needs to be able to move around on the beach. This is a very hostile environment for robotics due to salt water, dirt, and corrosion. Due to these environmental factors the locomotion should not involve complex motion, and have as few moving axes as possible.

Many different designs for locomotion in similar environments have been published already, even including amphibious 'ninja legs', robotic sandfish, and slime slime robots. On account of that, we will not attempt to design a new locomotion system. Rather, we will consider several existing solutions on their feasibility and power consumption.

Overview

Walking

Walking robots are useful for walking over rough terrain and adapting to various environments. They can climb steps, cross gaps as large as their stride and walk on rough terrain where wheels are not feasible. For a legged robot at least two degrees of freedom (joints) are necessary, so a six-legged robot will need twelve actuated joints. Stability can also pose an issue, as a walking robot can only be statically stable (stable when paused at every moment of its motion) when it has at least four legs. However, four legs means that only one leg can be lifted at any time when remaining statically stable, reducing the walking speed..

Having to hold the whole weight of the body and a large number of actuators makes all walking robots less energetically efficient than wheeled machines on flat ground. . Additionally, the higher degree of freedom makes legged robots less suitable for a beach environment as the higher number of joints increases the chance of dirt or water ingress. Due to these disadvantages, walking will not be considered further as a method of locomotion for our robot design.

Rolling

The mobile robot Auriga-β with a mini-helicopter on its self-stabilized landing platform.

Wheeled

On a flat surface, wheeled robots are the most efficient. This is because a frictionless wheel does not need energy to keep rotating at the same velocity. Stability is a far less significant problem for rolling compared to walking, as a design with at least three wheels will always be statically stable. Additionally, wheels are the easiest form of robot locomotion to implement. They require low torque to start rolling and thus are suitable for high speeds.

Wheeled locomotion presents a few disadvantages, most noticeably on rough, loose terrain such as sand. The increased rolling friction on this terrain causes power inefficiencies.

Continuous tracks

Though they require more torque, continuous tracks (or tank treads) offer significant advantages over wheels on soft surfaces. As they have more contact area, treads exert less ground pressure and will not sink into the sand as much as tires, reducing rolling resistance and increasing efficiency. They also offer higher traction as they fully engage with the large contact area. Treads are also able to cross larger gaps than wheels.

Continuous tracks change their direction by skidding, which increases friction and thus power consumption on hard surfaces.

Energy efficiency

Power consumption of several locomotion mechanisms.

Deformation of the ground surface caused by wheels.

The figure on the right shows the power consumption of several locomotion mechanisms. It is clearly visible that wheels on a hard surface (railway) are orders of magnitude more efficient than tires on soft ground. In order to obtain a useful estimate of the power consumption of wheeled versus continuous track locomotion, we will consider their rolling resistance on sand. Rolling resistance on sand greatly depends on the profile of the contact surface. Wheels will sink into loose sand, significantly lowering their efficiency or even getting the robot stuck. Tracks on the other hand exert much less pressure because of a very large footprint, and will stay on top of the sand for this reason. Overall, treads that spread their weight out over a large area will lose less power and be able to move at a higher efficiency.

In technology of tanks, R.M. Ogorkiewicz expresses rolling resistance in the form of a dimensionless constant [math]\displaystyle{ C_r }[/math] given by:

[math]\displaystyle{ C_r = A + B v\, }[/math]

where [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are constants with typical values of 0.025 and 0.0009 for treads respectively. [math]\displaystyle{ C_r }[/math] is multiplied with the weight to obtain the rolling resistance force [math]\displaystyle{ F_r }[/math] in Newtons:

[math]\displaystyle{ F_r = C_r m g\, }[/math]

where [math]\displaystyle{ m }[/math] is the mass of the robot in kilograms and [math]\displaystyle{ g }[/math] is the gravity of 9.81 N/kg. Assuming that the robot is travelling at a constant velocity, the necessary power to overcome rolling resistance in Watts is given by

[math]\displaystyle{ P_r = F_r \cdot v }[/math]

where [math]\displaystyle{ v }[/math] is once again the velocity. Using the above equations, [math]\displaystyle{ P_r }[/math] can be rewritten as

[math]\displaystyle{ P_r = (A + B v) m g v\, }[/math].

For ordinary tires on loose sand, [math]\displaystyle{ C_r }[/math] is estimated around 0.3. The resulting friction powers for both treads and wheels on sand of a robot that weighs 25 kg are depicted in the following figures:

Friction power of a 25kg robot on treads.	Friction power of a 25kg robot on wheels.

It is clearly visible that wheels on loose sand are an order of magnitude less efficient in this situation compared to continuous treads.

Litter recognition

Before it can be collected, litter should be recognized using certain sensors or robotic vision.

Object recognition

According to Scale Invariant Feature Transform (SIFT) is an algorithm that can recognize more then 78% of the litter, even when the image is severly distorted with contrast and intensity changes, rotations, scaling, stretching and noice. Therefore we can assume that images close enough will have a 78% to be recognized. According to the paper, multiplying the scale of objects by 0.7 will cause the recognition to be 85%, meaning that halving the scale, or doubling the distance, causes a recognition multiplication of 0.739. This gives rise to the equation for the litter chance: 0.78 * (0.739^d). This will however not continue forever. Johnson's criteria states that to recognize an image with more than 50% certainty, there needs to be at least 4 +/- 0.8 line pairs, which equals a minimum of 10 pixels. The distance at which this cutoff happens, depends on both the camera, and the size of the litter.

It is extremely difficult to determine the average two dimensional size of a piece of litter, as it is highly dependent on the orientation of the litter and whether sand is on top of it or not. For this purpose the area of the bottom of an aluminium can was used as approximation, which is approximately 30 cm^2, or a height of 6.5 cm. The distance to the object will be:

distance to object(m) = f(m) * real height(cm) * image height(pixels) / object height(pixels) * sensor height(cm)

to get ten pixels in a circular image, the object height should be four pixels. The real height will be 6.5 cm. All other variables are determined specifically by the camera.

An example of a camera could be the SONY HDR-CX240EB, which has a focal length of 29.8mm, a sensor height of 2,448cm and an image height of 14375 pixels. This will give a cutoff distance of 284 meters, which means that the cutoff of the original formula is much lower than the one because of Johnson's criteria.

Another much cheaper cheaper option would be the MACT-782F, which has a image height of 960 pixels, a focal length of 3.6mm and a sensor height of 6cm. This will give a cutoff distance of 0.9 meter. This will then be the limiting factor

Litter collection algorithms

Bayesian Network

On the right one can see the Bayesian network which models the probabilities. The 'Litter at location' indicates whether there is litter at a specific location. This influences the reading of the sensor which can either give a true positive, a true negative, a false positive or a false negative. Based on the sensor reading, the robot chooses to either move towards the litter or not which in turn influences the utility function.

Bayesian Network modelling the system.

Utility Function

The utility function will be as follows. The decision to not drive will make the utility zero. Negligible energy is used and no litter will be collected. If the robot does decide to drive, the utility will decrease by the energy used. If litter is found, de utility function will increase by the average amount of energy used to find a single piece of litter, to make sure that most of the litter is still found. The average amount of energy for a litter piece will be equal to the energy it will take for the robot to clean the whole beach divided by the number of litter on the beach. It is impossible to know this from the start for a given beach. Therefore this number will be estimated at the start, and will afterwards use the average of all every run it made on the beach. Because the robot will be an intelligent agent, it will always chose the action that maximises the utility function. This means that the robot will not move if the litter is either too uncertain or too far away. This utility function will also be tested with a simulation to see if it picks up enough litter for our purposes but will not run out of energy uselessly.

The function E_avg * litter_chance * amount_of_litter was designed because the robot should be indifferent with walking two times as far for two times the certainty of litter. Also having twice the amount of litter should make the robot twice as likely to go there.

However, using this function and having 100% vision, only half of the litter will be collected. This is not enough for the purposes of the robot. Therefore the gaussian distribution of the distance between two pieces of litter is needed.

Because litter usually collects in groups, the gaussian can be estimated to have a big sigma. According to Galgani et al, the North Atlantic has a litter density of 0.1/m and a variance of 0.2/m. This means that to get more than 90% of the litter, the average energy should be multiplied by 5. This means that with 100% vision, the robot will pick up 97.1% of the litter.

In pseudo-code, the utility function will be:

if (Drive)
	U = 5 * E_avg * litter_chance * amount_of_litter - E_drive;
else
	U = 0;

Initial value for E_avg

To make the robot work initially, without having done any cleaning so that it could update its average Energy to pick up a piece of litter, an initial value of E_avg is needed. To do this the total area of beaches in the Netherlands will be divided by the total amount of litter on beaches in the Netherlands. According to Centraal Bureau voor de Statistiek, the Netherlands consists for 90,016 hectares of beaches and dunes in 2012 , with a coastline of 451 km. The average amount of litter on beaches in 2012 was 1,781,450 . This means that an average of 25.3 cm needs to be surpassed to get to a single piece of litter. This will result according to the selected subsystems into **(NEED MORE INFO)** Joules

Litter spawning

To make the litter spawn realistically, two different distributions were used. Firstly, a guassian distribution was used with a mean on the beach line, to represent that most of the litter stranded on the land by the sea, combined with a guassian distribution with a mean of 25 centimeters and a variance of 10 cm as found in [BRON], to make sure the litter was distributed realistically far away from each other. The other distribution was to simulate the random behaviour of humans. Humans can throw away litter anywhere on the beach and therefore a few pieces of litter were distributed randomly over the map. From every piece of litter, a twenty percent chance was taken that the litter was actually not litter, but for example a toy of a child playing, or a piece of wood.

Robot Algorithm

When the robot would see litter, it would give the litter a percentage of certainty, depending on how far away the robot would be. If the robot saw something from a very large distance, the chance would be 50% that it was litter or not litter, and as it would come closer, the percentage would increase to 100% if it was actually litter, or decrease to 0% if it was not litter. The litter pieces that were under 75% sure, are displayed as blue dots. Litter pieces that are almost certain litter are displayed in red, and pieces that are not litter are displayed in green. When the robot is further away, it would also see multiple litter pieces as one, in order to make the robot more likely to go to a high density area then a low density area of possible litter. The robot would move towards the litter position where the Utility function would be highest at that moment in time. This is not completely optimal yet. Therefore more sophisticated algorithms could be used which are explained in the next section.

Litter collection + Sand filtration

After the litter is recognized, the robot should collect it. There are multiple ways to approach this. There will be a trade off between multiple factors of the litter collection systems, including but not limited to: Cost, how much sand it filter, Power consumption and effectiveness. Since this project focuses on the energy aspect of the robot, this will be the most important factor.

Average litter weight

The weight of the average piece of litter that will be used to calculate power consumption of the litter collection mechanisms. The average between the weight of an aluminum can and a 500 ml water bottle will be used since these are very typical pieces of litter, these are respectively 13.11 and 10.31 gram . Which makes the average trash weight 11.71 gram.

Claw

Claw design

A claw design can be used to collect litter from the ground. Its design is made in the shape of an excavator dumper, a well-known configuration used in dump trucks to collect trash. The claw is made from striped (coating) pieces of metal, this allows the robot to collect litter in an environment composed by sandy or clayey soil, reducing the drag force and granting that not much sand is collected together with the litter. The claw is composed of two different parts: the upper and lower one. These two parts are connected by a Futaba S3003 servomotor, responsible for the claw’s opening and closing movements. The rising and lowering of the claw is granted by a pair of AX-12 servomotors.

Average power consumption

Since the power necessary to lift the entire claw + the piece of trash is much larger than the power necessary to only close the claw, the power consumption of the closing part is not taken into account. So we will only look at the AX-12 servomotor.

specifications AX-12 servomotor

• Max/idle current - 900/50 mA
• Stall torque - 1.5 Nm
• Recommended voltage = 11.1 V

The weight of the claw is not given, so a similar claw has been found . This claw weighs 123 gram, but is a bit smaller, so the weight of the claw is estimated at around 200 gram. The length of the claw is approximately 25 centimeter. The claw makes a circular motion around the servo so the center of mass of the claw is on average 6.25 centimeter from the rotational point. It is assumed that the center of mass of the piece of garbage will be the same distance from the rotational point as the claw. This information about the claw together with the specifications of the AX-12 servomotor make it possible to calculate the power consumption, as can be seen below.

[math]\displaystyle{ T_{pick-up} = r \cdot m \cdot g }[/math]

[math]\displaystyle{ T_{pick-up} = 0.0625 \cdot (0.212 \cdot 9.81) }[/math]

[math]\displaystyle{ T_{pick-up} = 0.130\, }[/math]

With: T = Torque [Nm], r = distance from rotational point to center of mass [m], g = gravitational accelarion [m/s^2] and m = mass [kg] Then using the fact that the current is proportional to the torque, the current can be calculated.

[math]\displaystyle{ I_{pick-up} = \frac{T}{T_{stall}} \cdot (I_{max} - I_{idle}) + 2 \cdot I_{idle} }[/math]

[math]\displaystyle{ I_{pick-up} = \frac{0.130}{1.5}\cdot0.850 + 0.1 }[/math]

[math]\displaystyle{ I_{pick-up} = 0.174 \, }[/math]

With: I = current [A] Now the current and voltage are known so the power needed while picking up litter can be calculated.

[math]\displaystyle{ P_{pick-up} = U \cdot I }[/math]

[math]\displaystyle{ P_{pick-up} = 11.1 \cdot 0.174 }[/math]

[math]\displaystyle{ P_{pick-up} = 1.93\, }[/math]

With: P = power [W] and U = Voltage [V]

Now the amount of power needed to pick something up is known, but we also need to know the amount of power used when idling, this can be calculated using the same formula using the idle current.

[math]\displaystyle{ P_{idle} = U \cdot (2 \cdot I_{idle}) }[/math]

[math]\displaystyle{ P_{idle} = 11.1 \cdot 0.1 }[/math]

[math]\displaystyle{ P_{idle} = 1.11\, }[/math]

The power usage during garbage pick-up and idling are now known. To determine that amount of power the servo’s use on average the relation between pick-up time and idle time needs to be known. For now it is estimated that for every 30 seconds of idling there is 1 second of picking up trash. Which gives us the following average power usage.

[math]\displaystyle{ P_{avg} = P_{idle} \cdot \frac{30}{31} + P_{pick-up} \cdot \frac{1}{31} }[/math]

[math]\displaystyle{ P_{avg} = 1.11 \cdot \frac{30}{31} + 1.93 \cdot \frac{1}{31} }[/math]

[math]\displaystyle{ P_{avg} = 1.14 \, }[/math]

The average power consumption of the litter collection and sand filtration system the claw is 1.14 Watt.

Max power consumption

The peak power consumption occurs when the servo motor will have to deliver the most torque. The most torque has to be delivered when the robot has to collect the heaviest piece of litter, which is assumed to be 1 kilogram and the piece of litter is furthest away from the rotational point, which is 12.5 centimeter.

[math]\displaystyle{ T_{max} = r \cdot m \cdot g }[/math]

[math]\displaystyle{ T_{max} = 0.125 \cdot (1.2 \cdot 9.81) }[/math]

[math]\displaystyle{ T_{max} = 1.47\, }[/math]

With the maximum value of the torque it is possible to calculate the maximum value of the current.

[math]\displaystyle{ I_{max} = \frac{T}{T_{stall}} \cdot (I_{max} - I_{idle}) + 2 \cdot I_{idle} }[/math]

[math]\displaystyle{ I_{max} = \frac{1.47}{1.5}\cdot0.850 + 0.1 }[/math]

[math]\displaystyle{ I_{max} = 0.933 \, }[/math]

With the maximum value of the current the peak power draw can be calculated.

[math]\displaystyle{ P_{max} = U \cdot I_{max} }[/math]

[math]\displaystyle{ P_{max} = 11.1 \cdot 0.933 }[/math]

[math]\displaystyle{ P_{max} = 10.36 \, }[/math]

This makes the peak power draw 10.36 Watt.

Cost

The total cost of the solution:

• 2x AX-12 servomotors – €89,80-
• 2x Futaba S3003 servomotor - €27,10-
• 1x The claw itself - €50,00- (estimation based on the similar claw and the fact that this one is a bit bigger and has striped metal)

This makes the total cost: €166,90-.

Rake

Rake design

A rake design could also be used to collect litter from the beach. Just like the claw design it also already filters the sand from the litter. The rake design uses a 15 kg.cm Tower Pro servomotor. Since this exact servomotor could not be found a similar one will be used to determine the power consumption. This servomotor is the Tower Pro MG958. Specifications Tower Pro MG958 :

• Max/Idle current = 1600/170 mA
• 1,765 Nm
• 4.8 volt

The weight of the rake is not given, but the material is, which is ULTEM. Since it is similar in size to the claw design, but two times less dense the weight is estimated at 100 gram. The rake is about 30 centimeters long, so the center of mass will be 15 centimeter from the rotational point at the maximum load point and on average 7.5 centimeter during pick-up. Given these specifications about the servo motor and the rake, the maximum, idle and average power consumption can be calculated in the same way as for the claw design.

[math]\displaystyle{ P_{idle} = 0.816 }[/math]

[math]\displaystyle{ P_{pickup} = 1.14 }[/math]

[math]\displaystyle{ P_{max} = 7.11 }[/math]

[math]\displaystyle{ P_{avg} = 0.826 }[/math]

Total cost of solution:

• MG958 = €11,95-
• Rake (based on 100g ULTEM filament) = €32,-

This makes the total cost of the solution €43,95-.

Excavator arm

Excavator arm design design

The excavator arm design is also a possible solution to picking up litter from the beach. It also has holes in it, so that sand gets filtered out. The excavator arm has 3 DOF driven by 6 MG995 servomotors.

Specifications MG995 :

• Max/Idle current = 170/1200 mA
• Stall torque = 1.079 Nm
• Voltage = 6 V

Again the weight of the collection mechanism is not given. However the weight of a MG995 servomotor is 55 gram and the main two motors have to lift 4 others and the arm itself. It is therefore estimated that the collection mechanism weight about 400 gram. The excavator arm fully extended is 40 centimeter long. Since when fully extended most of the weight is at the end of the arm, it is assumed that the center of mass is at max load is at 30 cm from the rotational point. Using the parameters given the maximum torque comes out to be 4.12 [Nm] for the two main servomotors this is more than they can handle. So it is impossible for this design to lift 1 kilogram at full arm extension. This means that for the calculation of the maximum power consumption the two servo’s will be maxed out. It is also assumed that only two servomotors will be working at the same time. Given these specifications about the servo motor and the excavator arm, the maximum, idle and average power consumption can be calculated in the same way as for the other designs.

[math]\displaystyle{ P_{idle} = 6.12 }[/math]

[math]\displaystyle{ P_{pickup} = 9.59 }[/math]

[math]\displaystyle{ P_{max} = 14.4 }[/math]

[math]\displaystyle{ P_{avg} = 6.23 }[/math]

Total cost of the solution:

• 6x MG995 = €53,70-
• Excavator arm = €20,00- (estimation)

This makes the total cost of the excavator arm solution €73,70-.

Conclusion

Three different designs have been discussed, the claw, the rake and the excavator arm. All three of them incorporate sand filtration into their design. The main specifications of these litter collection mechanisms that were looked at were the power consumption and cost. These specifications are summarized in the following table.

Collection mechanism	[math]\displaystyle{ P_{idle} }[/math] [W]	[math]\displaystyle{ P_{pick-up} }[/math] [W]	[math]\displaystyle{ P_{max} }[/math] [W]	[math]\displaystyle{ P_{avg} }[/math] [W]	Cost [€]
Claw	1.11	1.93	10.4	1.14	166.90
Rake	0.816	1.14	7.11	0.826	43.95
Excavator arm	6.12	9.59	14.4	6.23	73.70

From these values we can conclude that the Claw solution is the most expensive, the excavator arm uses the most energy, while the rake is the most energy efficient. @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ The first design decision is the way litter is picked up from the ground.

The list of possibilities include:

• Litter picker/Grappling hook
• Shovel
• Vaccuum cleaner
• Litter stick

In the section below, the pros and cons of the above list are explored and a decision is made based on these.

Litter picker/Grappling hook Litter picking seems a logical option because humans use this technique as well to pick up the litter. The pros are that it is relatively silent and energy efficient way to pick up the litter. The cons are that the stick will be long and thin and therefore not too stirdy, and because there might be electronics in the stick because the downside will need to close, it might not be easy to make it water proof. Also, coordination needs to be very accurate to be able to grab the litter with such a small grabbing area.

Shovel A shovel seems like the easiest solution to solve the area problem of the litter picker. A shovel has a big area and will be able to easily pick up the litter. The cons however are that it will cost much energy to move the shovel through the sand and that it will therefore likely make much noise. Also a lot of sand will be picked up, causing the need of a more advanced sand filter.

Vaccuum cleaner A vaccuum cleaner is what is used most on the streets to pick up litter by robots. This is because it also has the high area to pick up litter just like the shovel idea. The cons on the street are that it costs much energy and makes much noise. This will be the same on the beach, but some extra cons are added. Namely that again a lot of sand will be sucked up rather than the litter.

Litter stick A litter stick is much like a litter picker in the sense that it is cheap and energy efficient, but only has a small area on which it can grab the litter. A con however of the litter stick over the litter picker is that the point must penetrate the litter, which is not possible for every type of litter. The pro however is that the litter stick does not need to be closed to pick up the litter. Another con is that it is more difficult to release the litter from the stick after picking it up rather than just opening up the ending. Another pro is that more than one piece of litter can be picked up without putting it in the internal garbage collector.

Rake The company Dronyx has created a robot to do various tasks on the beach. Their view is to use a rake behind the robot to take items bigger than sand with it. This is power efficient and has a lot of area to pick up the litter, but this will not hold itself to the requirement that the robot should only pick up items that are identified as litter. A way to solve this is to have a camera below the robot and only put the rake on the ground if litter is detected.

Conclusion It is clear that the vaccuum cleaner and shovel solution will likely cost too much energy or make too much noise to keep itself to the specifications made. The choise between a litter stick or a litter picker is more difficult, but the choise was made for the litter picker, because of the pro of making it easier to release the litter into the garbage collector. The Rake idea however has the pros of all of the other ideas, with the only difficulty when to lift it up and when to put it down. This however can be easily solved by smart software that would also be necessary when a litter picker was chosen. Therefore the final decision went to the rake.

Litter storage

The litter should be collected somewhere in or on the robot before it can be moved to be deposited.

Energy management

There are several options to provide the energy that the robot requires. The main options that were considered are:

• (On-board) sustainable energy obtainment, e.g.:
  • solar cells
  • small windmill
  • solar heating panel
• Combustion engine
• Electrical power provided via a cable
• (Interchangeable) Rechargeable battery
• Combinations of the options above

The criteria used to assess the different options are:

• Needed space and weight
• Delivered power
• Working time restrictions
• Sustainability
• Inherent restrictions
• Costs

The goal of this project is partly based on the environmental aspects of litter, so designing a robot with a combustion engine would form a sustainability point of view not be a desired option. In general, beaches are places with a lot of wind (and sunlight in the periods that most people are there), making the sustainable energy option even more attractive.

On-board sustainable energy obtainment has the advantage that the robot provides its own energy, and therefore does not have to spend extra time to recharge, to change a battery, to refuel, etcetera. Besides, these options are environmentally friendly. However, the energy obtainment will be dependent on the weather conditions, so that the robot could for example not work properly when there is not enough wind or sunlight, or the robot can never work at night when it runs on solar energy. Another disadvantage is the space needed. The irradiance of sunlight on earth’s surface is of the order 1000 W/m² . The efficiency of affordable solar panels is up to about 20% nowadays , which means that the power supply would be about 200 W/m². For lifting objects, about 20 W could be enough, but for driving up (small) hills, more power will be required. Assuming a 30° slope and a robot mass (including collected litter) of 20 kg, the force needed is 100 N. To reach a speed of 2 m/s, the power required is 200 W, even without taking acceleration forces, friction forces and extra rotation inertia due to rotating parts as the motor, (caterpillar) wheels, etcetera into account.

This means that a solar panel of at least about 1 m² would be needed. The weight of a solar panel is about 15 kg/m² , so the solar panel would add a significant amount of weight, and deliver just enough power to lift itself. Of course, the robot would not always have to drive uphill, so the average amount of power required will be lower. Storing the solar energy in a rechargeable battery inside the robot could then be an option. This will also solve the problem that the robot can would not work if there were less sunlight for a short time. However, the battery would also add extra mass and take up space. An on-board windmill would, besides making the construction very instable, lead to similar problems. Therefore, a better option would be a central point from which the robot(s) can obtain their energy. At this point, solar panels and possibly (small) windmills can be placed to obtain energy. It can be connected to the electricity network, so that extra energy can be obtained when needed, and energy can be returned when there is more than enough. A central point would already be needed to collect all the litter from the robots, and could also be a place from which a human operator could possibly control everything.

From this point, the energy can be distributed to the robots in several ways: (1) via a long cable that can extend, comparable to a vacuum cleaner, (2) by recharging the robots at the central point or (3) by recharging batteries that can be placed into the robots by replacing the used battery, which can be recharged at the central station afterwards. The advantages of using a cable are that the robots are not limited in their working time by a shortage of energy, there is no extra space and mass needed on-board of the robot for a battery and there is no time needed to recharge the robot or replace the battery. The disadvantages are that the cables can stick behind objects, can annoy people and limit the working range of the robots because even if the cables would be very long, at a certain point it will cost too much power to pull them through the sand. In short, it is clear that using cables would be very inconvenient.

The two options left both use rechargeable batteries. The choice to make is whether they should be recharged while the robot is at the central point, or while the robot is working and only replace the battery when the robot is at the central point. The advantage of replacing the battery is that it will take less time, so that the robots can work a larger part of the total time. The advantage of recharging the battery is that no system to replace the battery is required. The decision thus depends on whether the extra working time outweighs the extra costs of a battery replacing system.

Battery type comparison

Assuming that the robot requires an average power of 100 W while operating and the robot should be able to operate for half an hour without recharging/replacing the battery, the energy needed is 50 Wh.

For the use of batteries in our robot, they should be as small and light as possible due to the weight and space constraints. Therefore, a high energy density is preferred. Besides, the costs should not be too high. In the table below, the most relevant properties of the most common rechargeable batteries can be found . Rechargeable alkaline batteries are not included, since their life-time is very short compared to the other types.

Cell chemistry	Nominal Voltage [V]	Energy density [Wh/kg] ([Wh/L])	Cost [$/kWh]
Lead-acid	2.1	30 – 40 (60 – 75)	57 – 148
Nickel-cadmium	1.2	30 (100)	??
Nickel-metal hydride	1.2	100 (401)	303
Lithium-ion / -polymer	3.6 – 3.7	90 – 265 (333 – 730)	364

The main advantages and disadvantages of the different battery types are summarized below .

Battery type	Advantages	Disadvantages
Lead-acid	No memory effect	Low energy density
		Higher discharge rates result in loss of capacity
		Environmental hazard (however, they can be recycled)
Nickel-cadmium (NiCad)	Inexpensive	Low energy density
	Almost no loss of capacity at high discharge rates	Memory effect
		Environmental hazard, recently banned in many applications in Europe
Nickel-metal hydride (NiMH)	High energy density	High self-discharge rate (newer chemistry with low self-discharge rate has a ca. 25% lower energy density)
	Long life-time
Lithium-ion / -polymer (Li-ion / LiPo)	High energy density	Relatively expensive
		Low self-discharge rate

High self-discharge rates would only be a problem if the robot would not be used for a long time. If that would happen, the battery could be recharged or replaced with a small effort. Therefore, the self-discharging properties do not have priority when selecting the battery type. The Nickel-cadmium and Lead-acid batteries will not be chosen because of their relatively low energy densities and environmentally hazardous properties.

Further:

• required battery capacity -> weight and costs http://cleanleap.com/7-electricity-transport/71-battery-cell-and-pack-costs-and-characteristics
• battery replacing system (also part of ‘Central Hub’)

Robot algorithm

Traveling Salesman Problem

To get an optimal path for the robot, the Traveling Salesman Problem will need to be solved every time new information is gathered. The TSP is a well-known problem in both mathematics and computer science. It is stated as follows. “if a traveling salesman wishes to visit exactly once each of a list of m cities (where the cost of traveling from city i to city j is c_{ij}) and then return to the home city, what is the least costly route the traveling salesman can take?” In the case of the litter cleaning robot on the beach, the cities will be the litter (close enough to be energy efficient to check out), and the costs would be the utility function of the Litter Detection section. To get the solution, a tree could be made starting at the robots starting position, expanding nodes to every piece of litter close enough to be energy efficient to check out. Those new nodes would be expanded the same way, except that the utility function would be calculated from as if the robot would be in the position of the previous node, without adding new information, and excluding the litter that are parents of the node. This would however create a tree with N! (the factorial of the amount of litter close enough to be energy efficient to check out) nodes. For N’s as little as 10, this would already require almost 4 million nodes. Therefore this technique is neither memory nor time efficient to be used on a beach full of litter.

TSP with cellular decomposition

As realized in , a difficult problem such as the Traveling Salesman Problem, can be solved (semi-)optimal by cutting the total coverage of the area into smaller pieces, and solving the difficult problem within those pieces. Afterwards, the problem would be solved between the pieces that already have a solution, making the total solution very close to the optimal (or even optimal) while maintaining an easy solution. In the Traveling Salesman Problem discussed in the previous section, this would mean splitting the map, solving the TSP for the different sections and saving the total utility function gained from that, and then solving the TSP between the sections with the information gained from within the sections. This would reduce the total amount of nodes needed from N! to n*m!+n!, where m is the amount of litter in each section, and n is the amount of sections. This means that splitting for example a beach of with 12 pieces of litter (almost 500 million nodes in the original solution) in 4 blocks of 3 litter pieces (48 nodes), will decrease the computational time and memory by a factor of 10 million. The closer m and n are to each other, the higher the gain from this method, but also the further away the solution will be from the optimal one. The solution will however always be better than the greedy solution, as in the worst case it will be equal to the greedy solution.

Planning

Task overview & division

Gantt chart

Coaching Questions

Coaching Questions Group 15