decision_control/slotplanner.cc

   1 /*
   2 This file is part of I am car.
   3
   4 I am car is free software: you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation, either version 3 of the License, or
   7 (at your option) any later version.
   8
   9 I am car is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with I am car. If not, see <http://www.gnu.org/licenses/>.
  16 */
  17
  18 #include <algorithm>
  19 #include <cmath>
  20 #include <list>
  21 #include <queue>
  22 #include "slotplanner.h"
  23
  24 ParallelSlot::ParallelSlot()
  25 {}
  26
  27 // getter
  28 std::vector<std::vector<RRTNode *>> &ParallelSlot::cusp()
  29 {
  30         return this->cusp_;
  31 }
  32
  33 float ParallelSlot::DH() const
  34 {
  35         return this->DH_;
  36 }
  37
  38 PolygonObstacle &ParallelSlot::slot()
  39 {
  40         return this->slot_;
  41 }
  42
  43 float ParallelSlot::slotHeading()
  44 {
  45         float y0 = this->slot().bnodes()[0]->y();
  46         float x0 = this->slot().bnodes()[0]->x();
  47         float y3 = this->slot().bnodes()[3]->y();
  48         float x3 = this->slot().bnodes()[3]->x();
  49         float dy = y0 - y3;
  50         float dx = x0 - x3;
  51         return atan2(dy, dx);
  52 }
  53
  54 SlotSide ParallelSlot::slotSide()
  55 {
  56         if (!this->slotSide_) {
  57                 float y0 = this->slot().bnodes()[0]->y();
  58                 float x0 = this->slot().bnodes()[0]->x();
  59                 float y1 = this->slot().bnodes()[1]->y();
  60                 float x1 = this->slot().bnodes()[1]->x();
  61                 float y3 = this->slot().bnodes()[3]->y();
  62                 float x3 = this->slot().bnodes()[3]->x();
  63                 float h1 = atan2(y0 - y3, x0 - x3);
  64                 float h2 = atan2(y1 - y3, x1 - x3);
  65                 if (h2 - h1 > 0)
  66                         this->slotSide_ = LEFT;
  67                 else
  68                         this->slotSide_ = RIGHT;
  69         }
  70         return this->slotSide_;
  71 }
  72
  73 SlotType ParallelSlot::slotType()
  74 {
  75         if (!this->slotType_) {
  76                 float d1 = EDIST(
  77                         this->slot().bnodes()[0],
  78                         this->slot().bnodes()[1]
  79                 );
  80                 float d2 = EDIST(
  81                         this->slot().bnodes()[1],
  82                         this->slot().bnodes()[2]
  83                 );
  84                 if (d1 > d2)
  85                         this->slotType_ = PERPENDICULAR;
  86                 else
  87                         this->slotType_ = PARALLEL;
  88         }
  89         return this->slotType_;
  90 }
  91
  92 // setter
  93 void ParallelSlot::DH(float dh)
  94 {
  95         this->DH_ = dh;
  96 }
  97
  98 // other
  99 void ParallelSlot::fip()
 100 {
 101         // see https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bfs.html
 102         // RRTNode.s() works as iteration level
 103         std::queue<BicycleCar *, std::list<BicycleCar *>> q;
 104
 105         // TODO add init nodes
 106         // for now just copy fpose()
 107         bool left = false; // right parking slot
 108         float di = -1;
 109         // new pose for parallel parking to right slot
 110         float tnx;
 111         float tny;
 112         float nx;
 113         float ny;
 114         // temporary tnx is angle
 115         tnx = this->slotHeading() + M_PI;
 116         if (this->slotSide() == RIGHT)
 117                 tnx -= M_PI / 4;
 118         else
 119                 tnx += M_PI / 4;
 120         nx = this->fposecenter()->x() + 0.01 * cos(tnx);
 121         ny = this->fposecenter()->y() + 0.01 * sin(tnx);
 122         BicycleCar *CC = new BicycleCar(nx, ny, this->slotHeading());
 123         // move left by car width / 2
 124         tnx = CC->x() + CC->width() / 2 * cos(CC->h() + M_PI / 2);
 125         tny = CC->y() + CC->width() / 2 * sin(CC->h() + M_PI / 2);
 126         // move down
 127         nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 128         ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 129         if (this->slotSide() == LEFT) {
 130                 std::cerr << "left PS" << std::endl;
 131                 left = true;
 132                 di = 1;
 133                 // move right by car width / 2
 134                 tnx = CC->x() + CC->width() / 2 * cos(CC->h() - M_PI / 2);
 135                 tny = CC->y() + CC->width() / 2 * sin(CC->h() - M_PI / 2);
 136                 // move down
 137                 nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 138                 ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 139         }
 140         BicycleCar *B = new BicycleCar(nx, ny, CC->h());
 141         this->DH(di * 0.01 / CC->out_radi());
 142         BicycleCar *c;
 143         int i = 0;
 144         c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 145         while (!this->slot().collide(c->frame())) {
 146                 q.push(c);
 147                 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 148                 i += 1;
 149         }
 150         delete c; // not in q and collide
 151         // BFS
 152         while (!q.empty()) {
 153                 c = q.front();
 154                 q.pop();
 155                 if (this->isInside(c)) {
 156                         goto createcuspandfinish;
 157                 } else if (c->s() < 9) {
 158                         BicycleCar *cc = this->flnc(c);
 159                         cc->s(c->s() + 1);
 160                         cc->bcparent(c);
 161                         q.push(cc);
 162                 } else {
 163                         delete c; // not in q and collide
 164                 }
 165         }
 166 createcuspandfinish:
 167         std::vector<RRTNode *> cusp;
 168         while (c) {
 169                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 170                 c = c->bcparent();
 171         }
 172         std::reverse(cusp.begin(), cusp.end());
 173         this->cusp().push_back(cusp);
 174         std::queue<BicycleCar *, std::list<BicycleCar *>> empty;
 175         std::swap(q, empty);
 176 }
 177
 178 void ParallelSlot::fipr(BicycleCar *B)
 179 {
 180         // TODO for right parallel parking also
 181         // it's only for lpar scenario now
 182
 183         std::vector<RRTNode *> cusp;
 184         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
 185         // just copied from fip()
 186         this->DH(-0.01 / B->out_radi());
 187         BicycleCar *c;
 188         c = this->flncr(B);
 189         while (c->lfx() < 0) {
 190                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 191                 BicycleCar *cc = this->flncr(c);
 192                 cc->s(c->s() + 1);
 193                 delete c;
 194                 c = cc;
 195         }
 196         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 197         std::reverse(cusp.begin(), cusp.end());
 198         this->cusp().push_back(cusp);
 199 }
 200
 201 BicycleCar *ParallelSlot::flnc(BicycleCar *B)
 202 {
 203         // TODO find last not colliding
 204         // for now just copy flast()
 205         RRTNode *cc;
 206         if (int(B->s()) % 2 == 0)
 207                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 208         else
 209                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 210         BicycleCar *p;
 211         int i = 1;
 212         p = B->move(cc, i * this->DH());
 213         while (!this->slot().collide(p->frame())
 214                         && (
 215                                 (this->DH() > 0 && p->x() <= 0)
 216                                 || (this->DH() < 0 && p->x() >= 0)
 217                         )) {
 218                 delete p;
 219                 i += 10;
 220                 p = B->move(cc, i * this->DH());
 221         }
 222         i -= 10;
 223         p = B->move(cc, i * this->DH());
 224         while (!this->slot().collide(p->frame())
 225                         && (
 226                                 (this->DH() > 0 && p->x() <= 0)
 227                                 || (this->DH() < 0 && p->x() >= 0)
 228                         )) {
 229                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 230                         i += 1;
 231                         break;
 232                 }
 233                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 234                         i += 1;
 235                         break;
 236                 }
 237                 delete p;
 238                 i += 1;
 239                 p = B->move(cc, i * this->DH());
 240         }
 241         delete p;
 242         return B->move(cc, (i - 1) * this->DH());
 243 }
 244
 245 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
 246 {
 247         // TODO find last not colliding
 248         // for now just copy flast()
 249         RRTNode *cc;
 250         if (int(B->s()) % 2 == 0)
 251                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 252         else
 253                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 254         BicycleCar *p;
 255         int i = 1;
 256         p = B->move(cc, i * this->DH());
 257         while (!this->slot().collide(p->frame())
 258                         && (
 259                                 (this->DH() > 0 && p->x() >= 0)
 260                                 || (this->DH() < 0 && p->lfx() <= 0)
 261                         )) {
 262                 delete p;
 263                 i += 10;
 264                 p = B->move(cc, i * this->DH());
 265         }
 266         i -= 10;
 267         p = B->move(cc, i * this->DH());
 268         while (!this->slot().collide(p->frame())) {
 269                 if (this->DH() > 0 && p->x() <= 0) {
 270                         i += 1;
 271                         break;
 272                 }
 273                 if (this->DH() < 0 && p->lfx() >= 0) {
 274                         i += 1;
 275                         break;
 276                 }
 277                 delete p;
 278                 i += 1;
 279                 p = B->move(cc, i * this->DH());
 280         }
 281         delete p;
 282         return B->move(cc, (i - 1) * this->DH());
 283 }
 284
 285 RRTNode *ParallelSlot::fposecenter()
 286 {
 287         return this->slot().bnodes().front();
 288 }
 289
 290 bool ParallelSlot::flast(
 291         RRTNode *P,
 292         bool right,
 293         int il,
 294         std::vector<RRTNode *> &cusp
 295 )
 296 {
 297         BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
 298         RRTNode *cc;
 299         if (right)
 300                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 301         else
 302                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 303         BicycleCar *p;
 304         int i = 1;
 305         p = B->move(cc, i * this->DH());
 306         while (!this->slot().collide(p->frame())
 307                         && (
 308                                 (this->DH() > 0 && p->x() <= 0)
 309                                 || (this->DH() < 0 && p->x() >= 0)
 310                         )) {
 311                 delete p;
 312                 i += 10;
 313                 p = B->move(cc, i * this->DH());
 314         }
 315         i -= 10;
 316         p = B->move(cc, i * this->DH());
 317         while (!this->slot().collide(p->frame())
 318                         && (
 319                                 (this->DH() > 0 && p->x() <= 0)
 320                                 || (this->DH() < 0 && p->x() >= 0)
 321                         )) {
 322                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 323                         i += 1;
 324                         break;
 325                 }
 326                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 327                         i += 1;
 328                         break;
 329                 }
 330                 delete p;
 331                 i += 1;
 332                 p = B->move(cc, i * this->DH());
 333         }
 334         delete p;
 335         p = B->move(cc, (i - 1) * this->DH());
 336         if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 337                 cusp.push_back(p);
 338                 return true;
 339         } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 340                 cusp.push_back(p);
 341                 return true;
 342         } else if (il < 8) {
 343                 cusp.push_back(p);
 344                 return this->flast(p, !right, il + 1, cusp);
 345         }
 346         return false;
 347 }
 348
 349 void ParallelSlot::fpose()
 350 {
 351         bool left = false; // right parking slot
 352         float di = -1;
 353         BicycleCar *CC = new BicycleCar(
 354                 this->fposecenter()->x(),
 355                 this->fposecenter()->y() - 0.01,
 356                 this->slotHeading()
 357         );
 358         BicycleCar *B = new BicycleCar(
 359                 CC->x() - CC->width() / 2,
 360                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
 361                 this->slotHeading()
 362         );
 363         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
 364                 left = true;
 365                 di = 1;
 366                 delete B;
 367                 B = new BicycleCar(
 368                         CC->x() + CC->width() / 2,
 369                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
 370                         this->slotHeading()
 371                 );
 372         }
 373         this->DH(di * 0.01 / CC->out_radi());
 374         BicycleCar *p;
 375         int i = 0;
 376         p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 377         while (!this->slot().collide(p->frame())) {
 378                 std::vector<RRTNode *> tmpcusp;
 379                 tmpcusp.push_back(new BicycleCar(p->x(), p->y(), p->h()));
 380                 if (this->flast(p, left, 0, tmpcusp)) {
 381                         this->cusp().push_back(tmpcusp);
 382                         return;
 383                 }
 384                 i += 1;
 385                 delete p;
 386                 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 387         }
 388 }
 389
 390 bool ParallelSlot::isInside(BicycleCar *c)
 391 {
 392         bool inside = true;
 393         RRTNode *tmpn;
 394         tmpn = new RRTNode(c->lfx(), c->lfy(), 0);
 395         if (!this->slot().collide(tmpn))
 396                 inside = false;
 397         delete tmpn;
 398         tmpn = new RRTNode(c->lrx(), c->lry(), 0);
 399         if (!this->slot().collide(tmpn))
 400                 inside = false;
 401         delete tmpn;
 402         tmpn = new RRTNode(c->rrx(), c->rry(), 0);
 403         if (!this->slot().collide(tmpn))
 404                 inside = false;
 405         delete tmpn;
 406         tmpn = new RRTNode(c->rfx(), c->rfy(), 0);
 407         if (!this->slot().collide(tmpn))
 408                 inside = false;
 409         delete tmpn;
 410         return inside;
 411 }
 412
 413 struct SamplingInfo ParallelSlot::getSamplingInfo()
 414 {
 415         struct SamplingInfo si;
 416         BicycleCar *CC = new BicycleCar(
 417                 this->fposecenter()->x(),
 418                 this->fposecenter()->y() - 0.01,
 419                 this->slotHeading()
 420         );
 421         si.x = this->slot().bnodes()[0]->x();
 422         si.y = this->slot().bnodes()[0]->y();
 423         si.r = CC->diag_radi();
 424         si.h = this->slotHeading() - acos(EDIST( // TODO generalize
 425                 this->slot().bnodes()[0],
 426                 this->slot().bnodes()[1]
 427         ) / BCAR_LENGTH);
 428         return si;
 429 }