How our AI Auto-Design uses Genetic Algorithms

At DigitalBridge we’re excited about everything related to making consumers’ lives easier. One of the blockers when renovating a bathroom, is deciding where products should go and what size they should be for the consumer to use them effectively. Do you like free-standing baths but your bathroom is too small? Do you have a downstairs toilet but you’re struggling to fit a basin? We’re here to help!

We’ve previously written about our auto-design tool, which automatically populates an empty bathroom so that the result is aesthetically pleasing and at the same time satisfies regulations. We’ve also summarised a series of rules that our software should take into account when auto-designing a bathroom, but we haven’t said anything about how we actually solve the problem. This blog post is aimed at shedding some light on that.

Let’s first briefly review the problem we are trying to solve. We’re given an empty room of arbitrary shape and size, the position and dimension of the door, and if windows are present, their position and dimension too; the objective is to return a fully populated bathroom that satisfies a set of design rules and regulations. Our basic solution is to use derivative free optimization methods to solve the problem, and more specifically Genetic Algorithms.

WHAT ARE GENETIC ALGORITHMS?

Image courtesy of http://www.vce.bioninja.com.au/aos-4-change-over-time/evolution/evolutionary-theories.html

Genetic Algorithms take inspiration from Darwin’s evolution theory, “Survival of the fittest”, and have been successfully used to solve various problems, from learning to play video games to fighting crime! The algorithm requires the definition of a fitness function that evaluates how good a certain individual of a population is. The lower the fitness score, the better the individual is considered. For example, if you had a population of giraffes, it’d be fair to say that giraffes with longer necks are better than giraffes with very short necks, and should be the ones to survive in order to generate a new population of giraffes with long necks. If we wanted to devise a fitness function that expresses that, a very basic one would be

Where neck𝑔 indicates the neck of giraffe 𝑔. Notice how, the longer the neck of giraffe 𝑔 is, the lower (and thus better) the fitness score is.

A genetic algorithm uses evolution to minimise the fitness function over a sequence of generations. At each generation, each of the individuals in a population is evaluated using the fitness function. The population of individuals in the subsequent generation is then generated based on three operations: selection, mutations and crossover.

Selection: if an individual has a low fitness score, then we know it has some positive characteristics. Logically, similar individuals will share similar characteristics and thus have low fitness scores. This means that individuals with a low fitness score are a good starting point to search for better solutions. Selection makes sure that only the best 𝑥 individuals of generation 𝑛 are used as the parents for the individuals in generation 𝑛+1. To use the giraffe example, selection would probably choose giraffes with the longest neck to generate individuals of generation 𝑛+1.

Mutation: the idea behind mutation is to modify individuals randomly and hope that their mutation will generate better individuals. For example, with our previous giraffe example, a mutation operation could consist in making the new giraffe red rather than yellow. Now obviously, since mutation is random, it’s not necessarily true that individuals of the next generation are going to be better than their parents. I mean, have you ever seen a red giraffe?

Crossover: this operation allows two individuals to merge and create a new individual. This means that some characteristics of the new individual are taken from one of the parents, and others are inherited from the other one. For example, giraffe 𝑔 may end up with her mum’s eyes and her dad’s ears.

There is a probability that governs whether a certain individual will be subjected to mutation or crossover, which means that some of the individuals of generation 𝑛 will simply be “promoted” to generation 𝑛+1 without changing at all. After a maximum number of 𝑁 generations, the best individual over all the generations is chosen as the solution to the problem.

HOW DO WE APPLY GENETIC ALGORITHMS TO BATHROOM LAYOUTS?

Bathroom layouts are clearly a bit more complicated to model as individuals of a population than giraffes (or are they?). However, that’s exactly what we have done. We consider a bathroom layout to represent a single individual, and we build a fitness function over it.

A bathroom layout is composed of:

  • a room structure;
  • windows and doors with a 3D position and orientation;
  • bathroom products (baths, showers etc.) with a 3D position and orientation. We also specify the number of walls they can be attached to, and two types of clearance areas, hard and soft. The hard clearance area defines the area needed to use the product effectively, whilst the soft clearance area defines the area needed to use the product comfortably.

If you remember our last blog post (if you don’t, give it a read!), you’ll know that we distinguish between hard constraints and soft constraints.

Hard constraints define whether a certain layout is valid or not; obviously we want a layout to be valid according to regulations, therefore if those constraints are not satisfied, we simply assign a fitness score of infinite to the layout being considered. Example of hard constraints are: an item is supposed to be wall-mounted, but its position is not against the wall; an item must be within the perimeter of the room; the hard clearance area of an item must not overlap with the bounding box of another item; a shower must not be placed in front of a window; items should not be placed against the door.

Soft constraints give a measure of how good a layout is, and therefore can be transformed into terms of our fitness function. We list here some of the soft constraints we take into account:

  • Dispersion: this constraint ensures that items are not crammed next to each other.
  • Soft clearance area: this constraints model the fact that soft clearance areas should preferably not overlap much with other objects’ bounding boxes.
  • Occupancy: we have learned from data that usually only a certain percentage of the floor of the bathroom is occupied with bathroom products. We make sure that our auto-layout algorithm takes this into consideration.
  • Toilet in front of the door: according to this design rule, it would be better if the toilet wasn’t directly visible from just outside the door of the bathroom.
  • Inclusion penalty: this constraint assigns a penalty if a certain category is not placed in the room, and it’s computed based on the room’s size. For example, if the room is quite small, the penalty for not including a shower will be higher than the penalty for not including a free-standing bath.

The set of soft constraints are linearly combined and summed up to compose the fitness function of the 𝑗-th individual as follows:

where 𝑐 is the number of soft constraints, 𝑤𝑖 represents the weight assigned to the soft constraint 𝑔𝑖. Weights are learned from a set of training data, so that we make sure that the right rules are considered more important than others.

We can now define what kind of evolution procedures we use to make new generations of bathroom layouts. We start from a set of layouts which are generated randomly, and each of them is assigned a fitness score according to the fitness function described above. The best ones are selected to be parents. A new generation is then bred using crossover and mutation.

Crossover: we just randomly take some of the items from each parent to generate a new individual.

Mutation: each item in the layout can be moved around, added or removed.

A simple example of how new generations of bathroom layouts are created using Genetic Algorithms.

At the end of the procedure, we present to the consumer a bathroom layout that satisfies regulations and design rules.

RESULTS

Our auto-design service, patent pending, takes less than two seconds to generate a bathroom layout which is aesthetically pleasing and at the same time satisfies design rules.

We show here a few examples of rooms that have been generated by auto-design:

Very small bathroom. Auto-design understands that only a basin and a toilet can fit here.
Reasonably sized bathroom. Auto-design places a very small shower so that both a shower and a bath fit.
Weirdly shaped bathroom. Auto-design still finds a solution. The shower is pretty big here, and the bath fits quite well in that alcove!

Pretty impressive, right?

CONCLUSION

In this blog post we have illustrated how we use Genetic Algorithms to auto-design a bathroom. Notably, the entire process takes less than two seconds! We mentioned that this is our basic solution, and that’s because we actually do something a bit smarter than just using Genetic Algorithms. In fact, we actually add some Machine Learning magic to the whole thing as well, and make sure that we learn a bunch of information from data. However, that’s all for another time!

Follow us