  Since their discovery around a century ago, the structure and chemistry of
the multi-functional half-Heusler semiconductors have been studied extensively
as three component systems. The elemental groups constituting these ternary
compounds with the nominal formula XYZ are well established. From the very same
set of well-known elements we explore a phase space of quaternary double
($X'X''Y_2Z_2$, $X_2Y'Y''Z_2$, and $X_2Y_2Z'Z''$), triple ($X_2'X''Y_3Z_3$) and
quadruple ($X_3'X''Y_4Z_4$) half-Heusler compositions which 10 times larger in
size. Using a reliable, first-principles thermodynamics methodology on a
selection of 347 novel compositions, we predict 127 new stable quaternary
compounds, already more than the 89 reported almost exhaustively for ternary
systems. Thermoelectric performance of the state-of-the-art ternary
half-Heusler compounds are limited by their intrinsically high lattice thermal
conductivity ($\kappa_{L}$). In comparison to ternary half-Heuslers, thermal
transport in double half-Heuslers is dominated by low frequency phonon modes
with smaller group velocities and limited by disorder scattering. The double
half-Heusler composition Ti$_2$FeNiSb$_2$ was synthesized and confirmed to have
a significantly lower lattice thermal conductivity (factor of 3 at room
temperature) than TiCoSb, thereby providing a better starting point for
thermoelectric efficiency optimization. We demonstrate a dependable strategy to
assist the search for low thermal conductivity half-Heuslers and point towards
a huge composition space for implementing it. Our findings can be extended for
systematic discovery of other large families of multi-component intermetallic
semiconductors.
